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

Question

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

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

谢谢!

Answer 1

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

首先获取每对的成对相似度分数并存储这些分数。这是该过程中最昂贵的部分。选择具有最佳相似性分数的对并进行对齐。现在选择与对齐序列集中的一个序列对齐最好的序列，并根据该成对对齐将其对齐到对齐集。重复直到所有序列都在。

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 建议使用 SequneceMatcher() 算法对 UTF-8 字符串进行成对对齐。我所描述的内容为您提供了一种相当轻松、相当不错的方式来将其扩展到多个序列。

如果您有兴趣，这相当于建立一小组对齐的序列并将它们对齐到最佳配对。它给出了完全相同的结果，但它是一个更简单的实现。