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

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

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

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

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

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