摘要：隨著高通量測序技術(shù)的快速發(fā)展和測序成本的逐漸降低,個體基因組測序已成為研究不同物種的基因型、變異情況和相關(guān)疾病的重要手段。然而,由于基因組上的大量重復(fù)序列和高變異區(qū)域,日益增大的測序數(shù)據(jù)量以及測序技術(shù)的局限等因素,如何準確且快速地將大量測序數(shù)據(jù)比對到參考基因組面臨巨大挑戰(zhàn)。闡述基于哈希思想的基因組數(shù)據(jù)的存儲和索引方法。本文說明基于seed-and-extension思想的基本比對思路。本文提出一個基于de Bruijn圖模型的索引結(jié)構(gòu)DBG-index以及該索引的3層結(jié)構(gòu)數(shù)據(jù)存儲方式。分析該索引結(jié)構(gòu)的特性并提出種子的基本操作方法。該索引結(jié)構(gòu)利用圖模型特性可以有效組織基因組上的重復(fù)序列,從而在整體上減少了候選種子數(shù)量并極大提高了比對速度。