文章阅读目录大纲
MSA（多序列比对）在生物信息学中的核心目标是：通过把多条同源序列“对齐”，来突出它们之间的相似与差异，从而帮助我们：识别保守区/功能位点、推断进化关系（系统发生）、预测或解释蛋白质/核酸结构、发现共进化与功能模块，以及为后续分析（如模体搜索、结构建模、从头设计等）提供基础。基于多序列比对分析，我们可以通过这种算法，把一堆表面看上去“乱糟糟”的序列，整理成一个可以“逐位点比较”的框架。基于我们所得到的这个框架基础，我们可以进行下游的后续分析，例如：
- 识别哪些部分是“不能动”的（功能/结构核心）；
- 推断它们是如何“进化而来”的（系统发生）；
- 推测它们在空间中“长什么样”（结构预测与建模）；
- 找出哪些部分“一起变化”（共进化与功能耦合）；
- 并把这些信息封装成模型（HMM、profile）用于大规模搜索与注释。
算法的发展历史
基于综述论文“The Historical Evolution and Significance of Multiple Sequence Alignment in Molecular Structure and Function Prediction”(https://www.mdpi.com/2218-273X/14/12/1531)的回顾，于1970年提出来的Needleman–Wunsch 双序列全局最优动态规划算法是整个生物序列比对领域内的鼻祖。
Needleman–Wunsch 算法可以实现对“两条序列”做全局最优比对，通过动态规划得到一个最优得分和比对结果。理论上，我们可以把 Needleman–Wunsch 这种算法推广到多条序列（多维 DP）作比较，但是代价是在时间、空间复杂度上的指数级增加。Needleman–Wunsch算法应用于多序列比对，一般只适用于极短、极少的序列，实际不用于真正的大规模 MSA 。
虽然Needleman–Wunsch算法仅提供了两条序列之间的全局比对结果，但是这个算法为我们今天所讨论的MSA多序列比对算法提供了对应的数学基础。基于最初的序列比对算法的研究，在后面的1987年，提出了Feng–Doolittle 渐进式多序列比对算法 (progressive multiple sequence alignment，https://pmc.ncbi.nlm.nih.gov/articles/PMC287279/），这个算法可以被看做为真正意义上的多序列比对的发展起点的经典算法。
在1990年的时候，Gusfield 等人从算法理论（近似算法、图模型）的角度提出的一条“近似多项式时间”的多序列比对路线(https://www.cambridge.org/core/books/algorithms-on-strings-trees-and-sequences/F0B095049C7E6EF5356F0A26686C20D3)，即center star算法。center star算法于Feng–Doolittle 算法同属于平行发展的两条不同启发式计算算法路线。这两种算法在算法的大框架之上，都是基于利用两两比对结果来构造多序列比对，进行启发式的分布构造多序列比对结果。
多序列比对原理
我们今天在这里主要进行学习的是center star算法，在center star算法的实现中，
算法测试：多序列比对+SequenceLogo可视化
- CenterStar多序列比对算法 - 2026年1月8日
- 建立KEGG的KO序列数据库 - 2026年1月4日
- 环境微生物群落GEMs建模综述 - 2025年12月29日
No responses yet