高速緩存參數(shù)無關DNA短序列精確比對算法.pdf

1、隨著新一代測序技術的廣泛應用,產(chǎn)生海量測序數(shù)據(jù),為后續(xù)的序列分析帶來了巨大的挑戰(zhàn)。序列比對作為序列分析的前期處理步驟,它的性能直接影響著整個序列分析效率。對于序列比對可以分成以下三種形式:精確比對;固定錯誤范圍內(nèi)的模糊比對;插入刪除比對。本文主要研究基于海量數(shù)據(jù)的精確比對,研究的重點在于如何在減少比對次數(shù),提高序列的比對速度。
　　本文中我們對參考基因和測序數(shù)據(jù)建立哈希索引。建立索引主要是將所有前k個堿基相同的序列片段存儲到一起,

2、從而達到快速定位比對數(shù)據(jù)的目的。
　　在海量數(shù)據(jù)的序列比對中,在前k個堿基相同的情況下,參考基因和測序序列還是會含有大量需要比對的序列。這將導致大量比對次數(shù)的產(chǎn)生,為了減少比對次數(shù)本文對比對數(shù)據(jù)進行排序。本文根據(jù)比對數(shù)據(jù)的特點提出了高速緩存參數(shù)的比對算法,從而提高比對速度。同時為了更加充分利用現(xiàn)代普通計算機的資源,我們開發(fā)了多線程的并行比對程序提高程序速度。
　　最后為了充分利用各種排序算法的優(yōu)勢,本文對不同的比對方法在不同