基因组计划的实施,使序列数据激增,序列分析成为生物信息学的首要任务。序列比对与序列模体(motif)识别是进行生物序列分析的两个主要方法。本论文主要针对多序列比对问题和模体识别问题进行了方法上的研究。本文的主要工作和创新点如下:1、针对生物序列分析中的多序列比对问题,设计了求解多序列比对问题的混合遗传算法。首先采用SP记分函数作为个体的适应度函数,设计了4种遗传算子,对BAliBASE中Ref.1进行了测试,其结果表明该算法对等距蛋白质序列比对是有效的,其中部分比对结果优于ClustalX。2、为了进一步提高算法求解问题的范围及求解的精度,算法改用COFFEE函数作为个体的适应度函数,与之相应的软件称为PHGA-COFFEE,构造了6种遗传算子,特别是设计了2种新颖的变异算子,其中一种变异算子基于COFFEE的一致性信息设计,以改善算法的整体搜索能力;另一种变异算子基于动态规划方法设计,以增强其局部搜索能力。最后,通过对BAliBASE中144个测试例的测试,证明PHGA-COFFEE是有效的,与已有的算法相比,该算法对处于朦胧区和具有N/C末端延伸的序列比对问题有更强的问题求解能力。同时通过对算法并行化,其运行时间显著缩短。3、针对多序列比对中的Profile HMM的参数优化问题,提出了遗传算法与Baum-Welch(BW)算法相结合的混合遗传算法。通过实验分析,证明经过混合遗传算法的训练而得到的Profile HMM能更好地描述多序列比对,从而得到更加准确的比对结果。4、针对生物序列模体的识别问题,提出了一个新的混合Gibbs抽样识别算法。算法基于混合模体模型学习,采用贪心策略,通过似然度最大化,逐次将新的模体加入到混合模型中。算法中设计了位点抽样和模体抽样两种抽样方法,这两种抽样方法交替进行。为了加速搜索过程,对输入数据集采用了基于kd-trees的分层划分策略。实验结果表明,该算法对序列家族大量模体特征的识别具有显著优势,并且可建立更具统计特征的模体模型,从而提高序列分类的准确性。