單體型組裝問題參數(shù)化建模及算法研究.pdf

1、分析和識別單體型對復(fù)雜疾病致病基因的精確定位有重要作用。單體型組裝問題是利用個體DNA測序片段數(shù)據(jù)推出該個體一對單體型的計算問題。根據(jù)不同的優(yōu)化準則，單體型組裝問題有MSR、MFR、MEC和MEC/GI等計算模型。單體型組裝問題的絕大部分計算模型都被證明是NP-難的，缺乏實用的精確算法。 在實際DNA片段數(shù)據(jù)中，一個片段所覆蓋的最大SNP位點數(shù)k1通常小于10，覆蓋一個SNP位點的最大片段數(shù)k2通常不大于19?；谝陨鲜聦?，本文

2、對MSR和MFR進行參數(shù)化建模。在此基礎(chǔ)上，為求解無空隙的MSR和MFR，本文設(shè)計了時間復(fù)雜度分別為O(nk1k2+mlogm+mk1)和O(mk22+mk1k2+mlogm+nk2)的精確算法P_MSR和P_MFR，其中m為片段數(shù)，n為單體型的SNP位點數(shù)；為求解有空隙的MSR和MFR，本文設(shè)計了時間復(fù)雜度分別為O(2knk1k2+mlogm+nk2+mk1)和O(2kmk1k2+23kmk22+mlogm+nk2+mk1)的精確算法

3、PG_MSR和PG_MFR，其中k為片段中最大洞數(shù)。大量實驗結(jié)果表明，在Bafna等的對應(yīng)算法基礎(chǔ)上，上述參數(shù)化算法的效率顯著提高，適用于全基因組規(guī)模上的單體型組裝。 針對長的mate-pair中洞的個數(shù)較多的情況，本文提出了求解MSR和MFR時間復(fù)雜度分別為O(nk1k222h+k12h+nk2+mk1)和O(nk23k2+mlogm+nk2+mk1)的參數(shù)化精確算法PM_MSR和PM_MFR，其中h為覆蓋同一SNP位點且在該

4、位點取空值的片段的最大數(shù)。在實際的DNA測序數(shù)據(jù)中，k2通常不大于19，而辦不大于17，理論分析和實驗結(jié)果均表明PM_MSR和PM_MFR算法所需的時間與片段中洞的個數(shù)的最大值k沒有直接的關(guān)系，在片段數(shù)據(jù)中存在長mate-pair的情況下仍然能有效計算。 根據(jù)實際DNA測序片段數(shù)據(jù)的特點，本文對MEC和MEC/GI進行參數(shù)化建模，進而設(shè)計出求解這兩個模型時間復(fù)雜度均為O(nk22k2+mlogm+mk1)的精確算法P_MEC和P

5、_MEC/GI。實驗結(jié)果表明，在片段數(shù)達到100，Wang等提出的分支限界算法已無法運行的情況下，P_MEC、P_MEC/GI和Wang等提出的遺傳算法一樣，仍然能快速運行。而作為精確算法，P_MEC和P_MEC/GI在單體型重構(gòu)精度上比Wang等對應(yīng)的遺傳算法有明顯優(yōu)勢。 為了提高單體型的重構(gòu)精度，本文提出了一個基于加權(quán)片段數(shù)據(jù)和有誤差基因型的單體型組裝問題計算模型WMEC/GS，然后證明了即使片段中無空隙其也是NP-難的。進