基于概率模型的基因組從頭測(cè)序算法研究.pdf

1、基因組測(cè)序是生物信息學(xué)的核心,有著極其重要的應(yīng)用價(jià)值。近些年來(lái),新的測(cè)序技術(shù)大量涌現(xiàn),與傳統(tǒng)的Sanger方法相比,這些方法產(chǎn)生的read(由測(cè)序儀直接測(cè)得的DNA片段)長(zhǎng)度更短,數(shù)量更多,覆蓋率更大。然而,傳統(tǒng)的拼接算法并不適用于利用短 read進(jìn)行拼接,新的拼接算法在拼接效果上仍有待提高,因此本文提出了一種全新的DNA拼接算法,即基于概率模型的基因組從頭測(cè)序算法。
　　本文首先分析三種通用的糾錯(cuò)方法,因?yàn)閞ead中存在大量測(cè)序

2、錯(cuò)誤的堿基,這勢(shì)必會(huì)降低拼接結(jié)果的準(zhǔn)確性,所以有必要在拼接前利用糾錯(cuò)方法修正測(cè)序錯(cuò)誤的堿基。本文研究的基于概率模型的基因組從頭測(cè)序算法克服了原有拼接算法過(guò)度依賴堿基片段之間重疊信息的缺陷,創(chuàng)造性地將 DNA拼接過(guò)程抽象為二階離散馬爾可夫過(guò)程,與此同時(shí),每一條堿基片段被抽象為系統(tǒng)中的一個(gè)狀態(tài)。算法首先構(gòu)建概率模型存儲(chǔ)系統(tǒng)的狀態(tài)序列和全部轉(zhuǎn)移概率,然后給定系統(tǒng)中的兩個(gè)前驅(qū)狀態(tài),結(jié)合最大轉(zhuǎn)移概率原則便可確定下一個(gè)最佳狀態(tài),最后用最佳狀態(tài)更新前

3、驅(qū)狀態(tài),重復(fù)上述過(guò)程,當(dāng)前狀態(tài)序列的長(zhǎng)度便得到不斷地?cái)U(kuò)展,當(dāng)不存在最大轉(zhuǎn)移概率時(shí),便生成了一條滿足一定長(zhǎng)度要求的狀態(tài)序列,即一條 contig(拼接所得的一定長(zhǎng)度的DNA片段)。重復(fù)上述過(guò)程,算法最終便可拼接出一定數(shù)量的contig。然而,在實(shí)際拼接過(guò)程中會(huì)出現(xiàn)無(wú)后綴、repeat以及錯(cuò)誤高發(fā)區(qū)問(wèn)題,這大大增加了DNA拼接的難度。本文采用一系列啟發(fā)式規(guī)則對(duì)算法進(jìn)行優(yōu)化,從而解決了上述拼接難題。
　　將基于概率模型的基因組從頭測(cè)序算