随着测序技术的发展，越来越多的动植物、微生物的全基因组序列得以测定完成，基因组数据和规模正在以前所未有的速度迅速增长。基因组在进化过程中常常会有基因复制，基因缺失，易位，倒置等大规模突变发生。基因复制会产生旁系同源基因；基因缺失会导致物种的直系同源性模糊；而易位或者倒置通常会引起遗传物质的重排。长基因组的序列比对可以查找基因组突变，是基因组数据的比较分析，物种的进化分析和基因功能研究的基础。 传统的动态规划算法[1][2]的计算复杂度为O(n<2>)，其中n是输入序列的平均长度．动态规划只能处理长度在500K以内的氨基酸序列或者基因组序列。基于统计推断的SPA算法[3]的计算复杂度为O(n)，可以准确的比较长度在2M之内的基因组序列，但是随着长度的增加和输入序列同源性的降低，比对误差越来越大。 要比对长度规模更大的基因组序列，需要新的高效精确的算法。本文的结果就是开发适合大规模基因组序列比对的算法。具体结果如下： 1．首次将数据压缩的思想用于序列比对，对SPA算法做了改进，拓展了SPA算法的应用范围，开发出GSPA-I算法，该算法可用于大规模的微生物基因组和真核生物基因组的序列比对，测试结果表明GSPA-I算法比传统的序列比对算法速度大大提高，作长度大于2M的序列的比对结果的精确度高比SPA算法有明显提高。 2．首次将基于语法的编码 Yang-Kieffer算法[4]用于序列比对，开发出基于语法的比对算法GSPA-Ⅱ．GSPA-Ⅱ算法利用Yang-Kieffer码首先对输入序列进行编码处理，找到序列之间的语法匹配模块GMB，在GMB的基础上再完成比对，该算法比对规模大，克服了以往基因组序列比对算法受输入序列规模限制的弱点，用编码方法大大降低了算法的复杂度的同时，方便了对比对结果的分析。GSPA-Ⅱ算法能够很快处理长度在200M以上的基因组染色体序列，另外GSPA-Ⅱ算法能找到倒置，换位等大规模基因组突变。实验结果表明，GSPA-Ⅱ算法与最流行的 BLASTZ算法相比，比对速度平均高100倍左右，但是比对结果的相似度和基因覆盖率大致相当。 3．开发了大规模基因组多重比对算法SMGA．该算法结合了“模结构”理论和GSPA-Ⅰ算法，比对的速度和其他的各项指标与SMlA算法基本持平，但是SMGA能够处理像细菌古细菌等长基因组序列的多重比对。SMGA是基因组序列同源保守区的估计，基因预测和物种进化研究的有效工具。