單體型裝配問題的研究現狀

楊英杰

（ 銅仁學院 數學與計算機科學系，貴州 銅仁 554300 ）

單體型裝配問題的研究現狀

楊英杰

（ 銅仁學院 數學與計算機科學系，貴州 銅仁 554300 ）

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

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

1.SNP、單體型與基因型

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

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

圖1 某個個體的單體型與基因型

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

2.單一個體單體型裝配問題

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

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

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

2.2. 最少錯誤糾正（MEC）模型

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

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

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

2.4. 加權最少錯誤糾正模型

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

3.群體單體型裝配問題

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

3.1. 系譜推斷法

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

3.2. Clark算法

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

3.3. 最大似然算法：

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

3.4. 貝葉斯算法

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

3.5. 純節儉模型方法

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

4.展望

隨著人類基因組單體型圖的完成，單體型的研究必將在探究復雜性遺傳疾病的遺傳機理、患病風險與藥物反應不同中扮演重要角色，因此單體型裝配問題的研究顯得尤為重要。然而，目前對單體型的研究還是初步階段，還有很多問題等待著人們去探索。

[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]. 高校應用數學學報（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].計算機工程與應用，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

（責任編輯 毛志）

R394 < class="emphasis_bold">文獻標識碼：A

A

1673-9639 （2011） 02-0135-04

2010-03-03

銅仁學院自然科學基金（編號TS10018）。

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