如何计算文本字符串的多序列对齐方式

Question

我正在编写一个程序,它必须计算一组字符串的多序列对齐.我想在Python中这样做,但如果更实用,我可以使用外部软件或其他语言.数据不是特别大,我没有强大的性能要求,我可以容忍近似值(即我只需要找到足够好的对齐).唯一的问题是字符串是常规字符串(即UTF-8字符串可能带有应该被视为常规字符的换行符); 它们不是DNA序列或蛋白质序列.

我可以在生物信息学中找到大量的工具和信息,具有特定的复杂文件格式和一系列我不需要的功能,但是对于简单的字符串情况,很难找到软件,库或示例代码.我可以重新实现这个问题的许多算法中的任何一个,或者将我的字符串编码为DNA,但必须有更好的方法.你知道任何解决方案吗？

谢谢!

Answer 1

• 对齐多个序列的最简单方法是进行多次成对比对.

首先得到每对的成对相似度得分并存储这些得分.这是该过程中最昂贵的部分.选择具有最佳相似性得分的对并进行对齐.现在选择与对齐序列集中的一个序列最佳对齐的序列,并基于该成对比对将其与对齐集对齐.重复,直到所有序列都在.

当您将序列与对齐序列对齐时(基于成对比对),当您在序列中插入间隙时,您可以在对齐集中的所有序列中的相同位置插入间隙.

Lafrasu建议将SequneceMatcher()算法用于UTF-8字符串的成对对齐.我所描述的内容为您提供了一种相当轻松,合理的方式将其扩展到多个序列.

如果您感兴趣,它相当于构建一小组对齐序列并将它们对齐在最佳对上.它给出了完全相同的结果,但它是一个更简单的实现.

Answer 2

您是否正在寻找快速而肮脏的东西，如下所示？

from difflib import SequenceMatcher

a = "dsa jld lal"
b = "dsajld kll"
c = "dsc jle kal"
d = "dsd jlekal"

ss = [a,b,c,d]

s = SequenceMatcher()

for i in range(len(ss)):
    x = ss[i]
    s.set_seq1(x)
    for j in range(i+1,len(ss)):

        y = ss[j]
        s.set_seq2(y)

        print
        print s.ratio()
        print s.get_matching_blocks()