python - 多序列比对(最长公共(public)子序列)？

Question

好的，这就是我想要做的:

获取两个以上的字符串并“对齐”它们(没有 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

我目前在做什么:

• 对字符串进行排序(较长的字符串在列表中排在第一位)
• 对齐第一对:A-B 并得到结果(比方说 R1)
• 然后对齐第二对:R1 和 C(结果为 R2)
• 然后对齐第三对:R2 和 D
• 等等...

那么你的想法是什么？我怎么能这样做呢？有没有更好的办法？ (当然，必须有...)

我宁愿用 Perl/Python 或类似的东西来做，但是任何类型的代码/引用都非常受欢迎! :-)

Answer 1

我认为您可以将此问题转换为更一般的字符串差异 问题，而不是字符串对齐 问题。考虑 GNU diff 如何用于查找两个文件之间的差异，并使用与用于执行 N-way diff 相同的算法。

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