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

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

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

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