随着高通量测序技术的快速发展和测序成本的逐渐降低,个体基因组测序已成为研究不同物种的基因型,变异情况和相关疾病的重要手段。生物信息学为人类探索生命体活动规律,疾病产生机制与治疗提供了新思路,极大推动了分子生物学,基因组学,遗传学和医学的发展。基因组序列映射(Mapping)作为基因组数据分析的基础对变异识别(Variant Calling),基因表达量分析,选择性剪切分析和生物网络计算等研究方向有重要意义。还原测序数据在基因组上的真实位置是下游的生物信息计算的基础。然而,由于基因组上的大量重复序列和高变异区域,日益增大的测序数据量以及测序技术的局限等因素,如何准确且快速地将大量测序数据比对到参考基因组面临巨大挑战。本文围绕着基因组序列映射与序列比对为重点展开研究。本文的研究目的是通过分析现有比对方法的特性和不足之处,提出了基因组非线性的图模型组织表示方法。本文设计了基于de Bruijn图模型的基因组索引模型来有效组织和表达基因组上的大量重复片段。同时,为提高图模型的应用价值,提出针对大规模数据集的de Bruijn图模型构建算法。另外,本文实现了基于图模型的序列比对算法,达到了更高准确性,敏感性和更快的速度。并且,提出结合变异信息的序列比对算法进一步改进复杂变异区域的比对结果。本文的主要研究内容如下:(1)阐述基于哈希表模型思想的基因组序列数据的存储和索引方法。说明基于seed-and-extension思想的基本比对思路。提出一个基于de Bruijn图模型的索引模型(RdBG)以及该索引的三层结构数据存储方式。分析该索引模型的特性并提出两种种子合并的基本操作。该索引模型利用图模型特性可以有效组织基因组上的重复序列,从而极大地减少候选种子数量。(2)针对如宏基因组等多物种基因组数据和不断增加的测序数据,提出一个基于外部排序思想的de Bruijn图模型索引构建算法deGSM。deGSM解决了传统方法由于内存消耗大而限制图模型的数据量的问题,实现在任意内存占用下对任意大小数据完成图构建。同时,利用后缀树和de Bruijn图之间的关系,提出unitigs序列向BWT(Burrows-Wheeler变换)序列的转换方法。deGSM对基于de Bruijn图模型的大规模数据分析和数据压缩方法研究有重要意义。(3)根据de Bruijn图模型提出基于seed-and-extension思想的序列比对算法并实现序列比对软件deBGA。首先,介绍deBGA的整体算法流程和基于启发式的循环过程。然后,提出Uni-MEM种子的概念以及不同情况下种子合并和筛选的计算模型。同时,完成deBGA在相同物种和不同物种的多基因组数据集上,以及人类基因组的模拟和真实数据集上的测试。比较分析deBGA和其他比对软件在不同数据集上和不同参数下的比对结果。其次,比较分析deBGA对下游的变异识别计算的作用。结果显示基于RdBG索引的比对算法表现出更好的准确度,敏感度和更快的速度。deBGA可以作为基因组序列比对的候选工具。(4)提出结合变异信息的序列比对算法。首先,设计包含不同类型的变异信息的基因组索引模型实现变异信息的快速查找。其次,设计一个由所有局部序列和相关变异数据组成的伪树结构支持extension步骤计算。然后,利用Landau-Vishkin比对算法的思想提出一个基于此树结构的局部序列比对算法VAVA。相对于传统的内存消耗极大的变异图(Variant Graph)模型方法,该算法提供了一个轻量级的比对思路和解决方案。将VARA整合进deBGA实现全新的结合变异信息的序列映射系统deBGA-VARA。实验表明deBGA-VARA相比其他方法速度更快,并实现更高的准确度和敏感度。本文全面总结了基因组序列比对的基本方法,提出了de Bruijn图模型的索引模型来组织基因组重复序列。为解决对大数据构建图模型的内存瓶颈问题,本文提出基于外部排序思想的de Bruijn图模型构建算法,对索引模型和拼接算法的研究具有重要意义。同时,提出基于图模型的序列比对算法并通过大量实验证明该算法在不同数据集上都有很好效果,具有很高的实际意义;提出结合变异信息的局部序列比对算法,进一步提高了比对结果的准确性和敏感性,对基因组变异图模型和比对算法的研究具有理论和使用价值。