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

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

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

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