随着人类基因组计划的实施,新的分子生物信息数据大量涌现。如何从中得到有价值的知识是一项非常艰巨的任务。生物信息学就是利用现代计算技术来处理和研究生物数据的一门新型交叉学科。在生物信息学中,序列比对(sequence alignment)是生物序列分析中最基本的方法,通过序列比对可以得到序列间的相似性,它对于发现生物序列中的功能、结构和进化的信息具有非常重要的意义。目前双序列比对已有有效精确算法,而多序列比对的计算是一个比较困难的问题,因而寻求更快更敏感的多序列比对算法一直是生物信息学研究的热点。
　　本文首先介绍了生物信息学和DNA序列比对的相关概念,在第二章详细介绍了多序列比对,并对多序列比对主要的几类算法中的典型算法进行了简单的介绍,包括动态规划法中的Needleman-Wunsch算法和Carrillo-Lipman算法;启发式算法中主要介绍了渐进法中的ClustalW算法和Feng-Doolittle算法;迭代优化法中的HMM和迭代细化算法等等,并讨论了各算法的优缺点。
　　论文着重介绍了基于遗传算法的多序列比对算法和免疫粒子群优化的多序列比对算法,综合比较总结了两种算法的优缺点,并对算法进行了改进。最后,论文提出了免疫粒子群遗传算法,一定程度提高了序列比对的敏感性,使得算法在原有两种算法的基础上收敛速度加快。实验结果表明,对于多序列比对问题,算法是合理有效的。