基于de Bruijn图的基因组索引结构设计

摘要

随着高通量测序技术的快速发展和测序成本的逐渐降低,个体基因组测序已成为研究不同物种的基因型、变异情况和相关疾病的重要手段.然而,由于基因组上的大量重复序列和高变异区域,日益增大的测序数据量以及测序技术的局限等因素,如何准确且快速地将大量测序数据比对到参考基因组面临巨大挑战.阐述基于哈希思想的基因组数据的存储和索引方法.本文说明基于seed-and-extension思想的基本比对思路.本文提出一个基于de Bruijn图模型的索引结构DBG-index以及该索引的3层结构数据存储方式.分析该索引结构的特性并提出种子的基本操作方法.该索引结构利用图模型特性可以有效组织基因组上的重复序列,从而在整体上减少了候选种子数量并极大提高了比对速度.