單體型裝配問題的研究現(xiàn)狀

楊英杰

（ 銅仁學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，貴州 銅仁 554300 ）

單體型裝配問題的研究現(xiàn)狀

楊英杰

（ 銅仁學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，貴州 銅仁 554300 ）

單核苷酸多態(tài)性（SNP）是指不同個(gè)體DNA序列上的單個(gè)堿基的差異，是人類基因組中最豐富的遺傳變異。單體型是指位于一條染色體上或某一區(qū)域的一組相關(guān)聯(lián)的SNP等位基因。研究表明在復(fù)雜性疾病研究方面，由多個(gè)變異位點(diǎn)組合構(gòu)成的單體型所攜帶的信息比單個(gè)的SNP數(shù)據(jù)的信息更有價(jià)值，由此衍生了單體型裝配問題。文章論述了SNP，單體型，基因型的定義，綜述了求解單一個(gè)體單體型裝配問題的主要模型及算法，同時(shí)闡述了求解群體單體型裝配問題的5種方法及算法。

單體型； 單體型裝配； SNP； 基因型

1.SNP、單體型與基因型

國際人類基因組測序計(jì)劃的完成，為全世界的科學(xué)家提供了一套精準(zhǔn)的人類基因組序列圖譜，為人類真正了解自身奠定了重要基礎(chǔ)。同時(shí)，我們也驚奇地發(fā)現(xiàn)：任何兩個(gè)不同個(gè)體的基因組序列至少有99.99%的堿基對(duì)是相同的，也就是說剩下的僅僅0.01%的差異包含了遺傳上的差異因素。人們普遍認(rèn)為DNA序列上的差異是不同個(gè)體之間表型差異（如膚 色、發(fā)色，以及對(duì)疾病、藥物的敏感性等）的重要原因。這些序列上單個(gè)堿基的差異稱為單核苷酸多態(tài)性（SNP）。它是人類可遺傳變異中最常見的一種，占已知多態(tài)性的90%以上。

雙倍體生物的基因組由一對(duì)染色體組成，一條來自父方，一條來自母方。單核苷酸多態(tài)性（SNP）是指染色體上的某些核苷酸位置，在這些位置上，不同個(gè)體的DNA 序列有多種取值。在SNP 位置上出現(xiàn)的核苷酸稱為等位基因。一般地，在一個(gè)生物種群當(dāng)中，出現(xiàn)在某個(gè)SNP位置上的核苷酸只有兩種，而不是四種（A、G、C、T）。位于一條染色體上某一區(qū)域的一組等位基因稱作單體型。位于一對(duì)染色體上某一區(qū)域的由成對(duì)的等位基因所組成的序列稱作基因型，基因型是一對(duì)單體型的混合信息，如圖 1所示。如果基因型的某個(gè)位置上的一對(duì)等位基因相同，則稱這個(gè)SNP位置上是純合的，否則稱為雜合的。

圖1 某個(gè)個(gè)體的單體型與基因型

由于單體型包含著多個(gè)SNP的遺傳信息，許多研究表明，在與復(fù)雜性狀的相關(guān)分析中，采用單體型比單個(gè)SNP具有更好的統(tǒng)計(jì)分析效果。由于在現(xiàn)有的實(shí)驗(yàn)條件下獲得單體型數(shù)據(jù)非常困難，也非常昂貴，而獲得基因型數(shù)據(jù)或SNP數(shù)據(jù)卻很容易，因此利用計(jì)算的手段推測單體型數(shù)據(jù)越來越重要，由此衍生了單體型裝配問題。它大致分為兩類，一類是單一個(gè)體單體型裝配問題，一類是群體單體型裝配問題。

2.單一個(gè)體單體型裝配問題

單一個(gè)體單體型裝配問題是從給定的某對(duì)染色體上的 SNP片段數(shù)據(jù)來裝配某個(gè)個(gè)體的一對(duì)單體型。給定的數(shù)據(jù)可能是比對(duì)好的帶有SNP信息的基因組片段（由鳥槍測序法得到），也可能是進(jìn)行大規(guī)模單體型推測時(shí)前期工作所得到的。當(dāng)我們只考慮SNP位置時(shí)，這些短的基因組片段實(shí)際上就是比對(duì)好的SNP片段。如果知道一個(gè)個(gè)體的某對(duì)染色體上的全部 DNA 序列，裝配單體型實(shí)際上就是簡單地檢查一些SNP位置上的核苷酸取值。然而，由于DNA 測序方法的限制，我們只能得到一些短的DNA片段，而且這些片段不可避免地含有一些錯(cuò)誤。另外，兩條染色體的同源性也使問題變得復(fù)雜，因?yàn)槲覀儾恢滥膫€(gè)片段屬于哪條染色體。從計(jì)算的角度講，單體型裝配問題就是從給定的數(shù)據(jù)（可能有錯(cuò)誤，有矛盾）中確定出一對(duì)“最好”的單體型。也就是說，如何根據(jù)片段上的SNP信息將給定的比對(duì)好的SNP片段分成兩個(gè)集合，從而每個(gè)集合確定一條單體型。單一個(gè)體單體型裝配問題目前主要有以下幾種組合優(yōu)化計(jì)算模型。

2.1.最少片段去除模型和最少SNP去除模型

二者是由Lancia等在2001年提出的。前者假定造成數(shù)據(jù)不一致的原因是由于污染，即有些SNP片段不是來自目標(biāo)生物體，而是來自其他生物體，因此，強(qiáng)調(diào)去除最少的片段使得剩下的數(shù)據(jù)一致、不再有矛盾。后者假定所有的DNA 片段都來自同一生物體，但測序過程中產(chǎn)生一些錯(cuò)誤，因而要求去掉最少的SNP位置使得片段在余下的SNP位置上不再有沖突。Lancia還討論了這兩個(gè)問題的計(jì)算復(fù)雜性，在給定的片段沒有間隙時(shí)是多項(xiàng)式可解的，片段在有間隙時(shí)是NP-難問題。Rizzi等在2002年給出了求解這兩個(gè)模型的動(dòng)態(tài)規(guī)劃算法。[1]當(dāng)SNP片段上的最多間隙數(shù) k固定時(shí)，這些動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間的算法。

2.2. 最少錯(cuò)誤糾正（MEC）模型

最少錯(cuò)誤糾正（MEC）模型是由 Lippert等在2002年提出的，并證明是一個(gè) NP-難問題。這個(gè)模型假定所有片段來自同一個(gè)生物體，數(shù)據(jù)的不一致是由測序錯(cuò)誤造成的，并且這些錯(cuò)誤可以糾正而不是去除整個(gè)SNP片段或SNP位置（這種情況很實(shí)際）。針對(duì)MEC模型的求解的方法主要有兩類，一類是精確算法，主要指基于分支定界的精確算法，[2]但是在可接受的時(shí)間之內(nèi)僅僅能解決小規(guī)模的問題，另一類是啟發(fā)式算法，這類算法雖然不一定能夠找到準(zhǔn)確最優(yōu)解，但是它可以在短時(shí)間之內(nèi)找到一個(gè)相當(dāng)好的近似解。王瑞省等在 2005年提出了基于遺傳算法的啟發(fā)式算法，[3]錢偉懿，楊英杰等在 2008年提出了基于粒子群算法的啟發(fā)式算法，[4][5]有效地解決了最少錯(cuò)誤糾正模型中大規(guī)模的求解問題。

2.3. 帶基因型信息的最少錯(cuò)誤糾正（MEC/GI）模型

帶基因型信息的最少錯(cuò)誤糾正（MEC/GI）模型是對(duì)上一個(gè)模型——MEC模型的改進(jìn)，這個(gè)模型是由章祥蓀，王瑞省等人在2004年提出的。他們將這一問題表述成一個(gè)整數(shù)線性規(guī)劃模型，并證明是NP-難的，并且給出了一類特殊的 MEC/GI 模型動(dòng)態(tài)規(guī)劃算法，然后又設(shè)計(jì)了求解一般問題和大規(guī)模（SNP片段較多）問題的前饋神經(jīng)網(wǎng)絡(luò)算法。[6]該模型假定數(shù)據(jù)的不一致來自現(xiàn)實(shí)的DNA 測序錯(cuò)誤，這些錯(cuò)誤應(yīng)該得到糾正，在現(xiàn)有實(shí)驗(yàn)條件下，獲得個(gè)體基因型信息較為容易，那么在糾正過程中利用了基因型的信息，裝配出的單體型準(zhǔn)確率會(huì)更高。

2.4. 加權(quán)最少錯(cuò)誤糾正模型

加權(quán)最少錯(cuò)誤糾正模型也是對(duì) MEC模型的改進(jìn)。在DNA測序過程中，測得的每一個(gè)堿基除了本身的信息外，還附加了所測堿基的檢測質(zhì)量值，也就是該堿基被正確測定的概率。在最少錯(cuò)誤糾正模型中考慮每個(gè)堿基被正確測定的概率信息，Greenberg等提出了加權(quán)最少錯(cuò)誤糾正模型，趙玉英等證明了加權(quán)的最少錯(cuò)誤糾正模型是NP-難的，并且給出了基于動(dòng)態(tài)聚類算法的啟發(fā)式算法來求解這個(gè)模型。[7]

3.群體單體型裝配問題

群體單體型裝配問題：根據(jù)群體的基因型信息推斷群體的每個(gè)個(gè)體的單體型。從基因型數(shù)據(jù)推斷單體型就是消去基因型的雜合子位置，即確定雜合子位置上的兩個(gè)等位基因到底屬于哪條染色體。也就是說，對(duì)給定的一組基因型，尋找一個(gè)單體型集合，使得對(duì)每個(gè)基因型在這個(gè)集合中都有一對(duì)單體型對(duì)應(yīng)這個(gè)基因型。目前，應(yīng)用群體基因組數(shù)據(jù)推斷單體型的方法主要有五類。

3.1. 系譜推斷法

系譜推斷法是通過家系中相關(guān)個(gè)體的基因型，即追溯染色體片段的傳遞來推斷單體型狀態(tài)。盡管家系內(nèi)推斷單體型并不比在連鎖作圖中構(gòu)建單體型的眾多方法更簡單，但這樣的推斷可以為緊密連鎖的SNP提供真實(shí)的連鎖信息?；谧V系數(shù)據(jù)的單體型裝配方法大致分為兩類。一類是Lin等提出的統(tǒng)計(jì)方法，[8]這種方法裝配出來的每個(gè)單體型具有一個(gè)頻率值，但是算法很浪費(fèi)時(shí)間。另一類是 Tapadar等提出的基于規(guī)則的方法，[9]這種方法裝配出來的單體型沒有一個(gè)數(shù)值評(píng)價(jià)，但算法很快。然而，當(dāng)某些家系成員資料無法獲得或數(shù)據(jù)缺失都可能使SNP間的關(guān)系狀態(tài)模糊不清。

3.2. Clark算法

Clark第一個(gè)提出了在無相關(guān)個(gè)體間利用基因分型數(shù)據(jù)推斷單體型的算法。[10]如果有二倍體生物的一組序列，并具有多個(gè)變異位點(diǎn)，該算法首先找出樣本中所有純合子與僅有單變異位點(diǎn)的雜合子，將這些個(gè)體的單體型作為已識(shí)別的單體型。然后再判斷每一個(gè)已識(shí)別的單體型是否為那些尚未確定單體型并有變異位點(diǎn)的序列的等位基因，如果是，就將這種 SNP 的組合確定為新單體型。Clark方法存在的問題是，樣本需要數(shù)量較多，否則會(huì)出現(xiàn)沒有純合子或單個(gè)變異的雜合子的情況，從而導(dǎo)致單體型的推斷無法開始。

3.3. 最大似然算法：

在運(yùn)用Clark算法時(shí)，如果樣本中沒有純合子或單變異的雜合子就無法開始單體型的推斷。此外，當(dāng)推斷過程中出現(xiàn)多種可能的單體型時(shí)，依據(jù)已有的單體型來確定其中一種為新單體型的結(jié)果將受到抽樣中個(gè)體排列順序的影響。為了克服上述問題，Excoffier等提出了最大似然算法。[11]該方法以群體處于哈代-溫伯格平衡狀態(tài)為假設(shè)前提，對(duì)樣本單體型頻率采用 EM 算法進(jìn)行最大似然估計(jì)。該方法首先建立關(guān)于各單體型頻率的合理的似然函數(shù)。然后對(duì)單體型的頻率或其對(duì)數(shù)求偏導(dǎo)數(shù)，得出其最大似然估計(jì)。但當(dāng)單體型非常多時(shí)，運(yùn)算量也非常大，如果采用 EM 算法進(jìn)行迭代求解將大大提高運(yùn)算速度。

3.4. 貝葉斯算法

隨著公共數(shù)據(jù)庫中SNP位點(diǎn)的增多，需要考慮的單體型將呈指數(shù)增加，這會(huì)使 EM 算法的統(tǒng)計(jì)效力降低。為了克服EM算法的上述缺點(diǎn)，2001年貝葉斯理論被Stephens，Smith等引入單體型的推斷問題中。[12]他們采用蒙特卡羅-馬爾卡夫鏈方法進(jìn)行推斷，他們的算法也被稱為SSD算法。該算法又包含了兩個(gè)算式，一個(gè)是偽Gibbs抽樣法，另一個(gè)是結(jié)合群體遺傳的溯祖理論，采用了近似溯祖的先驗(yàn)分布。隨后，Niu等采用Dirichlet先驗(yàn)分布提出另兩種貝葉斯算法。[13]

3.5. 純節(jié)儉模型方法

純節(jié)儉模型方法是由Gusfield等在2003年首先提出來的，目的是要尋找唯一單體型數(shù)目最少的單體型集作為解。這個(gè)方法是基于這樣一個(gè)事實(shí)：在一個(gè)自然種群中，觀察到的不同單體型的數(shù)目遠(yuǎn)遠(yuǎn)小于理論上所應(yīng)有的數(shù)目（SNP位置數(shù)的指數(shù)個(gè)），這一點(diǎn)符合群體遺傳學(xué)。王瑞省等對(duì)這個(gè)模型給出了基于分支定界的精確算法，[14]這個(gè)算法有一個(gè)預(yù)處理過程，從而減少了可能解的個(gè)數(shù)，對(duì)中小規(guī)模很有效。后來，王瑞省，吳凌云等又提出了利用遺傳算法來求解較大規(guī)模（具有較多的SNP位置或較多基因型）的純節(jié)儉模型方法，并在其中引入局部優(yōu)化思想，即在進(jìn)行了選擇、交叉、變異之后，根據(jù)種群中個(gè)體適應(yīng)度的標(biāo)準(zhǔn)差采用自適應(yīng)局部優(yōu)化策略。引用局部優(yōu)化策略以后，可以在遺傳算法迭代時(shí)使用比較小的種群規(guī)模。

4.展望

隨著人類基因組單體型圖的完成，單體型的研究必將在探究復(fù)雜性遺傳疾病的遺傳機(jī)理、患病風(fēng)險(xiǎn)與藥物反應(yīng)不同中扮演重要角色，因此單體型裝配問題的研究顯得尤為重要。然而，目前對(duì)單體型的研究還是初步階段，還有很多問題等待著人們?nèi)ヌ剿鳌?/p>

[1] Rizzi R, et al. Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem [C]. In Proceedings of Second International Workshop on Algorithms in Bioinformatics （WABI）, Lecture Notes in Computer Science, Springer, 2002, 2452： 29-43.

[2] Rui-Sheng Wang, Ling-Yun Wu, Ji-Hong Zhang, et al.Algorithms for SNP haplotype assembly problem [J]. 高校應(yīng)用數(shù)學(xué)學(xué)報(bào)（A）. 2004, 19 （z1）： 515-528.

[3] Rui-Sheng Wang, Ling-Yun Wu, Zhen-Ping Li, et al.Haplotype construction from SNP fragments by minimum error correction [J]. Bioinformatics, 2005, 21（10）：2456-2462.

[4] Weiyi Qian, Yingjie Yang, et al Particle swarm optimization for SNP haplotype reconstruction problem. Applied mathematics and Computation 2008 Volume 196, issue 1, Pages 266-272.

[5] 錢偉懿，楊英杰.改進(jìn)粒子群算法在單體型重構(gòu)問題的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（5）：64-66.

[6] Xiang-sun Zhang, et al. Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype ,Evolutionary Bioinformatics, 2006, 2271-280.

[7] Yu-ying Zhao, Ling-Yun, Ji-Hong, et al. Haplotype assembly from aligned weighted SNP fragments. Computational Biology and Chemistry, 2005,29, 281-287.

[8] Lin S, Cutler D J, Zwick M E, et al. Haplotype inference in random population samples. Am J Hum Genet, 2002, 71（5）：1129-1137.

[9] Tapadar P S et al. Haplotyping in pedigrees via a genetic algorithm. Human heredity, 2000, 50（1）： 43-56.

[10] Clark A G.Inference of haplotypes from PCR-amplified samples o diploid populations. Mol Biol Evol, 1990, 7：111-122.

[11] Excoffier L, Slatkin M. Maximization likelihood estimation of molecular haplotype frequencies in a diploid population.Mol Biol Evol, 1995, 12： 921-927.

[12] Stephens M, Smith N J, Donnelly P. A new statistical method for haplotype reconstruction from population data.Am J Hum Gent, 2001, 68： 978-989.

[13] Niu T, Qin Z S, Xu X, et al. Bayesian haplotype inference for multiple kinked single nucleotide polymorphism s. Am J Hum Gent, 2002, 70： 157-169.

[14] Rui-Sheng Wang, et al. Haplotype inference by maximum parsimony [J]. Bioinformatics, 2003, 19（14）：1773-1780.

Research situation of Haplotype Assembly Problem

YANG Ying-jie
（ Department of Mathematic and Computer Science, Tongren University, Tongren, Guizhou 554300, China ）

Single nucleotide polymorphism （SNP）--- a single base difference varying from DNA sequences of different individuals, is the most common type of genetic variant in human genome. Haplotype is a set of associated SNP alleles observed on a single chromosome or a part of a chromosome. Some studies demonstrated that the analyses of haplotype defined by the grouping and interaction of several variants rather than any individual SNP correlate with complex phenotypes form to address genetic differences and bring haplotype assembly problem. Here,we describe the definitions of SNP, haplotype and genotype, summarize several models and algorithms of single individual haplotype assembly problem, as well as five methods and algorithms of group haplotypes assembly problem in the paper.

haplotype;haplotype assembly;SNP;genotype

（責(zé)任編輯 毛志）

R394 < class="emphasis_bold">文獻(xiàn)標(biāo)識(shí)碼：A

A

1673-9639 （2011） 02-0135-04

2010-03-03

銅仁學(xué)院自然科學(xué)基金（編號(hào)TS10018）。

楊英杰（1982-），女，碩士，講師，主要研究方向：最優(yōu)化方法、生物信息學(xué)。