單體分型和單體型頻率估計(jì)：復(fù)雜性及算法.pdf

1、計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，為分子生物學(xué)研究提供了新的強(qiáng)大手段。單體型信息因其在醫(yī)學(xué)特別是遺傳疾病研究方面具有重要意義，引起生物與醫(yī)學(xué)工作者的極大關(guān)注。但絕大多數(shù)所研究的生物個體，包括人類自身，都是雙倍體結(jié)構(gòu)；目前由于時間和經(jīng)濟(jì)成本上的約束，在實(shí)驗(yàn)室里只能得到雙倍體結(jié)構(gòu)的復(fù)合基因型序列。因此，當(dāng)需要知道物種或者組織的單體型序列信息時，我們必須借助于計(jì)算手段，將每一條基因型序列分解為兩條單體型序列，這就是單體分型問題。本文研究了不同數(shù)據(jù)集

2、及不同模型上單體分型問題的計(jì)算復(fù)雜性，設(shè)計(jì)和實(shí)現(xiàn)了一系列高效的單體分型和單體型頻率估計(jì)算法。其主要內(nèi)容和貢獻(xiàn)包括： (1)群體數(shù)據(jù)集單體分型群體數(shù)據(jù)集不包含任何家系信息，是最常見的一種基因型數(shù)據(jù)集。關(guān)于群體數(shù)據(jù)集單體分型問題，目前常見的計(jì)算手段有Clark算法、PPH算法以及EM和GS等概率統(tǒng)計(jì)算法。本文對一種新近提出的基于最大節(jié)約原則的單體分型(HMP)模型進(jìn)行了研究，證明其是NP-hard的和APX-hard的(即，除非NP

3、=P，否則存在一個常數(shù)e＞0，該問題沒有比1+e好的多項(xiàng)式時間逼近算法)。因此，我們?yōu)槠湓O(shè)計(jì)了一個多項(xiàng)式時間的貪心算法以及一個將貪心策略和分支限界策略集合在統(tǒng)一框架下的復(fù)合算法。實(shí)驗(yàn)結(jié)果表明：貪心算法在保持了較準(zhǔn)確分型結(jié)果的基礎(chǔ)上，運(yùn)行速度相當(dāng)快；而復(fù)合算法雖是完全算法，但其運(yùn)行效率和實(shí)例規(guī)模比原有的分枝限界算法都得到了極大提高。群體數(shù)據(jù)集中特定基因型序列分型(SGH)判定問題與上述Clark算法相關(guān)，它可以幫助我們更好理解單體分型問題

4、。本文證明了SGH問題為NP-complete的。 (2)家系數(shù)據(jù)集單體分型由于家系信息的對單體構(gòu)型的限制，基于家系數(shù)據(jù)集進(jìn)行的單體分型和單體型頻率估計(jì)的結(jié)果會更加可靠。目前對其研究集中于尋找使得家系中發(fā)生最少重組事件的單體構(gòu)型。本文提出了一個k-最少重組單體分型(k-MRH)模型，它在現(xiàn)有的最少重組單體分型(MRH)模型中引入額外限制，使得重組事件在家系中更加合理地平衡分布。同時設(shè)計(jì)了k-MRH模型的一個綜合了尋根策略的優(yōu)化動

5、態(tài)規(guī)劃算法，盡管該模型也是NP-hard的，但我們的限制條件使其解空間大大縮小，從而大大提高了算法的搜索效率，這在模擬和實(shí)際數(shù)據(jù)的實(shí)驗(yàn)中都得到了驗(yàn)證。 零重組單體分型(ZRH)問題是MRH問題一個特例，其目標(biāo)是為給定家系求解不包含任何重組事件的單體構(gòu)型，它在單體分型以及單體型頻率估計(jì)方面具有重要意義。本文給出了ZRH問題的一個最優(yōu)的線性時間算法：HCL-連鎖分析單體分型算法。 (3)家系數(shù)據(jù)集單體型頻率估計(jì)單體型頻率估計(jì)

6、和單體分型問題密切相關(guān)，本文提出了一個兩段式的家系數(shù)據(jù)集單體型頻率估計(jì)方法：i)、單體分型階段：用HCL-連鎖分析單體分型算法找出所有零重組單體構(gòu)型；ii)，頻率估計(jì)階段：發(fā)展了原有針對群體數(shù)據(jù)集的EM算法以在前一階段得到的單體構(gòu)型上進(jìn)行頻率估計(jì)，并且使用分割-合并技術(shù)，將原指數(shù)時間的EM算法改造為近似線性時間算法。 以前的直接估計(jì)法不考慮家系信息，必須對所有可能的單體型序列進(jìn)行估計(jì)。而我們的兩段式方法多了一個分型階段，該階段排

7、除了大量不合理和不重要的單體構(gòu)型。因此，整個頻率估計(jì)時間大為減少，結(jié)果也更加可靠這些都從實(shí)驗(yàn)中得到了驗(yàn)證。 按照研究內(nèi)容分類，本文的創(chuàng)新之處在于：1、群體數(shù)據(jù)集單體分型證明了HMP模型為NP-hard和APX-hard的；SGH問題為NP-complete的；并為HMP模型成功設(shè)計(jì)了一個貪心算法和一個復(fù)合完全算法，它們能夠解決較大規(guī)模的問題實(shí)例。 2、家系數(shù)據(jù)集單體分型在MRH模型基礎(chǔ)上，提出了一個更加合理的k-MRH模