單體分型的快速算法及補缺問題研究.pdf

1、單體型問題是分子生物學(xué)的一項重要研究課題，單體型信息在遺傳性疾病、藥物反應(yīng)檢測等方便起著重要作用。由于人類和許多生物實體都是雙倍體結(jié)構(gòu)，實驗手段只能得到基因型序列而非單體型，其中還存在大量的數(shù)據(jù)缺失，而重測序意味著更大的時間與成本消耗。同時，新一代測序技術(shù)(NextGenerationSequencingtechnology，NGS)得到的生物序列更為龐大，迫切需要既快速又高精度的計算方法對基因型進(jìn)行分型和補缺。本文就單體分型和補缺兩個

2、問題的快速算法進(jìn)行了深入研究，主要研究內(nèi)容和貢獻(xiàn)如下：
　　 1．基于均勻分塊的單體分型算法
　　 組合優(yōu)化方法是單體分型的一種重要方法，主要是基于合理的生物學(xué)假設(shè)來尋找精確解，其中最大節(jié)約模型是一種簡單而有效的分型模型。由于分型問題的難解性，當(dāng)數(shù)據(jù)規(guī)模較大時，基于該模型的算法難以在可接受的時間內(nèi)得到最優(yōu)解，于是便產(chǎn)生了基于分塊策略的快速方法研究。此前的分塊方法主要是基于位點之間的連鎖不平衡特性，將較高關(guān)聯(lián)度的位點劃分到

3、同一塊內(nèi)，合理的分塊盡管能夠提高分型的準(zhǔn)確度，但計算位點之間的關(guān)聯(lián)度和塊間合并會有較高的時間開銷。為此，本文提出了一種帶有重疊位點的均勻分塊單體分型快速算法FHBPGL，該算法采用均勻分塊且在塊內(nèi)使用最大節(jié)約模型進(jìn)行分型，均勻分塊減少了分塊時間；利用塊間的重疊位點進(jìn)行貪心合并，提高了結(jié)果的準(zhǔn)確度。真實數(shù)據(jù)與模擬數(shù)據(jù)上的實驗結(jié)果表明，F(xiàn)HBPGL算法運行時間顯著減少，優(yōu)于已有的算法，在結(jié)果準(zhǔn)確度上與這些算法相當(dāng)。
　　 2．基于連

4、鎖不平衡的自參考補缺算法
　　 實驗測得的基因型或推導(dǎo)得到的單體型大多存在缺失位點，而重新測序代價過高，因此需要利用計算手段進(jìn)行補缺。當(dāng)前的補缺算法大多是利用已有數(shù)據(jù)庫作為參考，對缺失序列進(jìn)行補缺；然而，對于新物種以及缺乏足夠參考數(shù)據(jù)的序列，這類算法并不適用。本文提出了一個基于自參考的補缺算法，將缺失數(shù)據(jù)序列進(jìn)行分塊，之后利用塊內(nèi)完整數(shù)據(jù)作為參考進(jìn)行補缺。該補缺算法的設(shè)計思想有如下三點：第一是分塊后塊內(nèi)序列長度變短，塊內(nèi)完整序列