MSA(多序列比对)算法 | Larry’s Space

type

status

date

slug

summary

📝 基于动态规划的算法

和之前进行Pairwise Sequence Alignment类似，构建三维的dp表并回溯求解。

可以预见，当序列数不断增多，时间复杂度

这个时间复杂度意味着，当n>3时，算法虽然理论上可行，但是实践上几乎不可用。

🤗 构建MSA的启发式方法

启发式算法 (Heuristic Algorithms) 是相对于最优算法提出的。一个问题的最优算法是指求得该问题每个实例的最优解. 启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费 (指计算时间、占用空间等) 下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。

逐步比对法（Progressive Alignment）

原理：逐步比对法首先进行序列的两两比对，构建一棵引导树（Guide Tree），然后按照树的拓扑结构逐步将序列或已有的比对结果进行合并。

步骤：

计算序列间的相似性：通常使用距离矩阵或得分矩阵，通过全局或局部比对算法（如Needleman-Wunsch或Smith-Waterman）计算每对序列的相似性。

构建引导树：基于序列间的相似性，使用聚类算法（如UPGMA或邻接法）构建一棵引导树，反映序列之间的进化关系。

逐步比对：按照引导树的拓扑，从相似性最高的序列或已有比对结果开始，逐步将序列或比对结果合并，最终得到所有序列的多序列比对。

代表工具：Clustal系列（如ClustalW、Clustal Omega）。

一致性法（Consistency-Based Methods）

原理：一致性方法不仅考虑直接的序列间比对，还利用间接的序列比对信息，以提高比对的准确性。

步骤：

计算所有可能的两两比对，不仅限于最优比对。

建立一致性矩阵，评估不同序列位置之间的一致性。

构建比对，基于一致性矩阵进行多序列比对，确保所有比对的位置尽可能一致。

代表工具：T-Coffee、MUSCLE。

迭代优化法（Iterative Methods）

原理：通过反复调整已有的比对结果，以逐步优化比对质量。通常结合局部调整和全局优化策略。

步骤：

初始比对：使用逐步比对法或其他方法得到初始MSA。

优化步骤：通过局部调整（如交换序列顺序、重新比对部分序列）或全局优化（如重新构建引导树）改进比对结果。

迭代：重复优化步骤，直到达到预设的收敛条件（如比对质量不再显著提升）。

代表工具：MAFFT。

不同MSA工具的对比

🤗 MSA的评分

匹配数（Multiple Longest Common Subsequence Score）

定义与原理：

匹配数通常指的是多序列比对中的保守位点数量，或者更具体地，指的是多个序列中最长公共子序列（Multiple Longest Common Subsequence, MLCS）的得分。MLCS是指在所有序列中按顺序出现的最长子序列，不要求子序列在每个序列中是连续的。

熵评分（Entropy Score）

定义与原理：

熵评分用于衡量MSA中每个位置（列）的信息熵，反映了该位置的保守性和变异性。信息熵来源于信息论，越高的熵表示位置上的变异性越大，保守性越低；反之，熵越低，表示位置较为保守，变异性较小。

计算方法：

单个位置的熵计算：

对于MSA中的每一个比对列，计算各个氨基酸或核苷酸出现的频率。设有n种可能的符号（例如20种氨基酸），第i个符号的频率为，则该位置的熵为：

整体熵评分：

可以对所有位置的熵取平均值，或者根据研究需要进行加权和总结。

应用与意义：

熵评分帮助识别MSA中保守和变异的区域。保守区域通常具有功能或结构的重要性，而高熵区域可能对应于功能中可变的部分。熵评分也可用于优化比对参数，以提高比对的生物学相关性。

对偶配对得分（Sum of Pairs, SP-Score）

定义与原理：

对偶配对得分是评估MSA质量的一种常用方法，基于所有成对序列之间的得分之和。具体来说，对于MSA中的每一对序列，计算它们的配对得分，然后将所有配对得分相加，得到整体的SP-Score。该得分反映了整个比对的保守性和一致性。

计算方法：

•成对得分计算：

对于MSA中的每一对序列，使用特定的得分矩阵（如BLOSUM、PAM）计算它们的配对得分。配对得分通常基于匹配、错配和缺口（gap）的惩罚。

•总和计算：

将所有成对序列的配对得分相加，得到SP-Score：

其中，表示第i和第j序列的配对得分，N为序列总数。

应用与意义：

SP-Score综合考虑了所有序列对之间的相似性，因此能够提供比单一序列对更全面的比对质量评估。然而，随着序列数量的增加，计算复杂度也显著增加。因此，在序列数量较大时，可能需要采用近似或分组策略。