序列比对是生物信息学中基本的信息处理方法,随着人类基因组计划的推进得到了广泛的重视和深入的研究,但是目前还没有一个最佳的多序列比对算法。近年来,遗传算法的卓越性能引起了人们的关注,并成功地被应用到各种领域的优化问题中。如何改善遗传算法的搜索能力和提高算法的收敛速度,使其更好地应用于实际问题的解决中,是各国学者一直探索的一个主要课题。免疫算法作为一种新近受到重视和发展的计算智能,与其他理论的融合还有很多潜力期待挖掘。免疫算法和遗传算法结合时,遗传算法的全局搜索能力及免疫算法的局部优化相配合,可大大提高搜索效率。本文通过对多序列比对算法的研究以及对遗传算法和免疫算法特点的分析,提出了基于自适应免疫遗传算法的多序列比对算法MSAAIGA(Multiple Sequence Alignment Based On Adaptive Immune Genetic Algorithm)。该算法将自适应遗传算法与免疫算法相结合,运用遗传算法实现多序列比对问题的遗传操作,该算法中生成初始群体时采用了星比对算法,这样可以充分利用序列自身的信息,要优于盲目的在序列中插入空位生成的初始群体,虽然在比对初期会增加时间开销,但是会大大提高比对后期的搜索效率。遗传算法是全局收敛的,但是遗传算法的交叉算子和变异算子却相对固定,在求解问题时,可变的灵活程度较小,这样易使遗传算法产生早熟现象,陷入局部极值。因此本文采用自适应遗传算法,在进化过程中根据种群的实际情况,动态调整交叉概率和变异概率。自适应遗传算法在保持群体多样性的同时,保证了遗传算法的收敛性,提高了算法的寻优能力。另外将免疫算法中的免疫算子应用于自适应遗传算法,在保留原算法优良特性的前提下,更加有效地抑制了优化过程中出现的退化现象。本文给出了算法的具体步骤,并结合实例证明了其全局收敛性,理论分析及实验结果证明了这种融合的有效性。