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

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

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

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