高速緩存參數(shù)無(wú)關(guān)DNA短序列精確比對(duì)算法.pdf

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

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