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

Question

我正在写一个程序，它必须计算一组字符串的multiple sequence alignment。我想用Python来实现，但如果更实用的话，我可以使用一个外部软件或其他语言。数据不是特别大，我没有很强的性能要求，我可以容忍近似值（即，我只需要找到一个足够好的对齐方式）。唯一的问题是字符串是规则字符串（即UTF-8字符串可能有新行，应该将其视为规则字符）；它们不是DNA序列或蛋白质序列。

在生物信息学中，我可以找到大量的工具和信息，这些工具和信息具有特定的复杂文件格式和许多我不需要的特性，但要找到简单字符串的软件、库或示例代码却出人意料地困难。我也许可以重新实现这个问题的任何一个算法，或者将我的字符串编码为DNA，但必须有更好的方法。你知道有什么解决办法吗？

谢谢！

Answer 1

你在找一些又快又脏的东西吗，如下所示？

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 2

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

首先获取每对的成对相似性分数并存储这些分数。这是这个过程中最昂贵的部分。选择相似度得分最高的一对，然后进行比对。现在选择与对齐序列集中的一个序列最匹配的序列，并基于成对对齐将其与对齐的序列集对齐。重复直到所有序列都进入。

When you are aligning a sequence to the aligned sequences, (based on a pairwise alignment), when you insert a gap in the sequence that is already in the set, you insert gaps in the same place in all sequences in the aligned set.

Lafrasu建议使用sequnecmatcher（）算法对UTF-8字符串进行成对对齐。我所描述的给了你一个相当痛苦，相当体面的方法来扩展到多个序列。

如果你感兴趣的话，这相当于建立一个小的对齐序列集，并在它们的最佳对上对齐它们。它给出了完全相同的结果，但它是一个更简单的实现。

Answer 3

我最近编写了一个python脚本，运行了Smith-Waterman算法（这是用来为DNA或蛋白质序列生成有间隙的局部序列比对）。这几乎肯定不是最快的实现，因为我根本没有优化它的速度（目前不是我的瓶颈），但它工作，不关心字符串中每个字符的身份。我可以把它贴在这里，或者把文件发到你的邮箱里，如果这是你要找的东西的话。