面向配對測序數(shù)據(jù)的拼接擴展算法研究與實現(xiàn).pdf

1、新一代測序技術(shù)正在引領生命科學研究進入一個嶄新階段。以個性化醫(yī)療為主的生物醫(yī)學信息時代已經(jīng)到來，這對DNA測序技術(shù)提出了新的更高的要求。新一代測序(NGS)技術(shù)經(jīng)過10多年的發(fā)展，目前的新一代測序儀器產(chǎn)生的數(shù)據(jù)在測序長度、質(zhì)量和數(shù)據(jù)種類（單端測序、配對測序、多種長距離跨越配對測序等）、每次測序規(guī)模、測序時間以及測序費用等方面都有很大的改進。
　　本文利用近幾年產(chǎn)生的NGS數(shù)據(jù)，對主流軟件在比對精度、比對速度和空間開銷等方面進行了功

2、能和性能測試，并對主流軟件存在的問題和問題產(chǎn)生的原因進行了分析，在此基礎上提出了針對新測序數(shù)據(jù)特點的改進方法，主要工作如下。第一，為了提高種子比對速度，提出了基于哈希索引的種子比對定位算法，該方法先對測序數(shù)據(jù)中的種子段進行排序（基數(shù)排序和計數(shù)排序），之后生成有序的測序數(shù)據(jù)種子序列集合文件；在種子數(shù)據(jù)與參考基因組的比對過程中，順序讀取種子序列文件，極大提升了種子比對速度。第二，為了提高擴展比對速度，提出了基于分段比對擴展的快速算法，該算法

3、先計算段內(nèi)與段之間的評分函數(shù)，依據(jù)得分進行最優(yōu)比對位置的篩選。第三，為了提高比對精度，提出測序數(shù)據(jù)的配對信息矯正算法，給出了整合配對距離與比對精度信息的評價函數(shù)，并利用該函數(shù)的值來淘汰不合適的比對位置。上述三個算法構(gòu)成本文設計的拼接擴展算法。
　　本文采用GenBank數(shù)據(jù)庫中下載的人類基因組參考序列和測序數(shù)據(jù)（測序數(shù)據(jù)覆蓋度為40倍，數(shù)據(jù)量是117G堿基，序列長度為101堿基，配對距離是200到400堿基）進行了測序?qū)嶒?，并與B