如何计算文本字符串的多序列比对

Question

我正在写一个程序，需要对一组字符串进行多序列比对。我原本打算用Python来实现，但如果有其他更实用的软件或语言，我也可以考虑。数据量不大，我对性能要求不高，也能接受一些近似结果（也就是说，我只需要找到一个足够好的比对）。唯一的问题是，这些字符串是普通字符串（也就是UTF-8编码的字符串，可能包含换行符，但换行符应该当作普通字符处理）；它们不是DNA序列或蛋白质序列。

我能找到很多关于生物信息学的工具和信息，通常是针对特定复杂文件格式的，里面有很多我不需要的功能，但意外的是，找到适合普通字符串的简单情况的软件、库或示例代码却很困难。我可能可以重新实现许多现有的算法，或者把我的字符串编码成DNA，但肯定有更好的方法。你知道有什么解决方案吗？

谢谢！

Answer 1

MAFFT 版本 7.120+ 支持多文本对齐。输入格式类似于FASTA格式，不过这里用的是LATIN1文本，而不是序列，输出则是对齐后的FASTA格式。一旦安装好，运行起来非常简单：

mafft --text input_text.fa > output_alignment.fa

虽然MAFFT是一个成熟的生物序列对齐工具，但它的文本对齐模式还在开发中，未来计划包括允许用户自定义评分矩阵。你可以在文档中查看更详细的信息。

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()

Answer 3

• 对多个序列进行对齐，最简单的方法就是先进行一对一的对齐。

首先，计算每一对序列之间的相似度分数，并把这些分数存起来。这一步是整个过程最耗时的。接下来，选择相似度分数最高的一对序列进行对齐。然后，从已经对齐的序列中，找出与其中一个序列对齐效果最好的序列，再把它对齐到已经对齐的序列中，依照刚才的那一对对齐。这个过程重复进行，直到所有的序列都对齐完成。

当你把一个序列对齐到已经对齐的序列时（根据一对一的对齐），如果你在已经对齐的序列中插入了一个空缺（gap），那么在所有已经对齐的序列中也要在同样的位置插入空缺。

Lafrasu 提出了一个叫做 SequneceMatcher() 的算法，可以用来对 UTF-8 字符串进行一对一的对齐。我刚才描述的方法提供了一种相对简单、效果不错的方式，可以扩展到多个序列的对齐。

如果你感兴趣的话，这个方法其实就是逐步建立小的对齐序列集，然后在它们之间进行最佳对齐。这样做的结果是完全一样的，但实现起来更简单。