多序列比对是生物信息学中最基本的信息处理方法,而寻求更快更敏感的多序列比对算法一直是生物信息学研究的热点。本文对此进行了深入研究和探讨。本文深入地研究了当今国际上的各种序列比对算法,系统地阐述了最具代表性双序列比对算法Needleman-Wunsch、Smith-Waterman、FASTA和BLAST;以及多序列比对算法中的渐进比对算法CLUSTALW、T-Coffee、DiAlign、迭代比对算法MultAlin、Prrp、Muscle、和基于图论的算法POA、ABA,并具体分析了各算法的优缺点。模拟退火算法是一种解NP完全组合优化问题的有效近似算法。本文通过对模拟退火SA-MSA算法的理论分析和实验测试,证明了目前的模拟退火在多序列比对问题上的应用模型具有不敏感和效率低的缺点。为了寻求更敏感的多序列比对算法,根据对模拟退火算法和星比对算法的研究,提出了一种新的基于模拟退火和星比对分工合作的多序列比对算法(MSA-CONSENSUS-STAR),将求解复杂的多序列比对问题分解为求解调和序列的问题和简单比对问题。并用多序列比对库BAliBASE中的用例对算法进行了测试,证明MSA-CONSENSUS-STAR算法是有效的。与SA-MSA和HMMT算法相比,精度有了大幅度的提高;与已有的ClustalW、SAGA和MultAlin算法相比,该算法对于含有“孤儿”序列和具有N/ C末端延伸的序列比对问题的求解能力更强。