多序列比对（最长公共子序列）？

获得超过两个字符串和“对齐”他们（无DNA/RNA序列或与他们每个人不喜欢1000级的物品等等，只是普通的字符串）

我已经做了一些成对比对的工作（对齐两个字符串），但是“间隙”在尝试对齐多对时会给我造成一些问题。

例（一个我目前正在测试）：

ABCDEF 
ABGHCEEF 
AJKLBCDYEOF 

AB--CDEF 
ABGHCEEF 
======================= 
AB--C-EF 

A-B--C--E-F 
AJKLBCDYEOF 
======================= 
A----C--E-F

而另一（多个解说）例如：

http://nest.drkameleon.com 
http://www.google.com 
http://www.yahoo.com 

http://nest.drkameleon.com 
http://-www.--google--.com 

======================= 
http://----.------le--.com 

http://----.------le--.com 
http://-www.-----yahoo.com 

======================= 
http://----.----------.com

我目前在做什么：

排序的字符串（长字符串来第一次在列表中）
对准第一对：AB和得到的结果（假设R1）
然后对齐第二对：R1和C（结果R2）
然后对齐第三对：R2和D
等等...

那么什么是在你的心中？我怎么能这样做？有没有更好的办法？（当然，必须有...）

我宁愿在Perl/Python或这些行上做这些事情，但是任何类型的代码/引用都会受到欢迎！ :-)

来源

2012-04-09 Dr.Kameleon

你可能会张贴一些输入和输出的例子吗？我不是100％的你想要做什么。 – 2012-04-09 13:03:15

也看看这篇文章，详细解释了Python中的LCS问题。 http://wordaligned.org/articles/longest-common-subsequence#toc21 – luke14free 2012-04-09 13:05:48

@ Li-aungYip下面是我的意思：http://stackoverflow.com/questions/10065293/how-to-align-2-strings – 2012-04-09 13:10:37

我想你也许可以投这个问题是一个更一般的字符串差异问题，而不是字符串对准的。考虑如何使用GNU diff来查找两个文件之间的差异，并使用与用于执行N路diff相同的算法。

我不确定这种方法的时间/内存复杂性是否适合您的需求，但您至少可以这样思考问题。

来源

2012-04-09 13:18:19

我并不确定在这种情况下'diff'有多大帮助...... – 2012-04-09 15:48:08

有一种基于Levenshtein算法计算最长公共序列的算法，可选空间。不知道这是否有帮助。

来源

2012-04-09 15:46:38 Alberto

呃，显然我在Levenshtein算法上玩了很多，然后试了一下Hirschberg的算法，但是可能会更接近我案例是** Needleman-Wunsch算法**（http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm） – 2012-04-09 15:50:10

多序列比对（最长公共子序列）？

回答

相关问题