單體型裝配問題的啟發式算法研究

摘要：單體型裝配問題是生物信息學的一個研究重點，針對的是染色體上的大量SNP數據，通過適當的方法，將其裝配成一對單體型。文章介紹了求解單體型裝配問題的三種主要的啟發式算法，分別是基于遺傳算法的啟發式算法，基于粒子群算法的啟發式算法和基于前饋神經網絡算法的啟發式算法。

關鍵詞：單體型；單體型裝配；SNP

中圖分類號：R394 文獻標識碼：A 文章編號：1007-9416（2017）01-0124-01

生物信息學是一個新興學科。它以計算機為工具對生物信息進行存儲，檢索和分析，探究生命的奧秘。我們知道，每個人都是獨立的個體。沒有完全相同的兩個人。但是從基因序列的角度來看，不同的個體有很高的相似度，因為堿基對有99%是相同的。換句話說，僅有1%的堿基對的不同決定了遺傳上的人與人的不同。例如，不同個體之間頭發，鼻子，眼睛的不同等等。

每個生物都具有基因組，絕大部分的基因組都是由DNA組成，當然個別基因組也可由RNA組成。DNA和RNA是有核苷酸組成的多聚分子。每個核苷酸包含一個單糖，一個磷酸基團，和一個堿基。堿基共四總，A，G，C，T，堿基配對原則A與T配對，G與C配對。一個基因是位于某條染色體的某個位置上的核苷酸序列，其中蘊含著某種特定的功能產物（如蛋白質）的編碼。基因不僅可以通過復制把遺傳信息傳遞給下一代，還可以使遺傳信息得到表達。染色體中基因組序列中單個堿基的差異稱為單核苷酸多態性（SNP），單核苷酸多態性是人類基因突變中最常見的一種。雙倍體生物的兩條同源染色體幾乎完全相同，每一條染色體上或染色體的某一區域上的所有SNP位點對應的等位基因構成的堿基序列構成一條單體型。那么裝配單體型，對于分析SNP在人群中的分布和規律，發現與疾病相關的基因與多態位點就顯得尤為重要了。

1 單體型裝配問題[1]

單體型裝配問題針對的是染色體上的大量SNP數據，通過適當的方法，將其裝配成一對單體型。由于染色體都的成對出現的。那么，如何將SNP片段分成適當的兩個集合，并且從每個集合按照一定的原則裝配出一條單體型就是一個難點。另外，我們通過實驗得到的小的SNP片段存在一些瑕疵，例如某些點數據的缺失，某些點通過實驗得到的數據是錯誤的等等。因此，這些未知的因素使得我們裝配單體型的難度變大了。單體型裝配問題目前主要有三類：最少錯誤糾正（MEC）模型，最少片段去除模型，最少SNP去除模型。針對以上三種模型求解的主要方法，目前研究比較多的是啟發式算法，這類算法優點是運用時間少，可以較快的找到問題的最優解。缺點就是找到的是最優解，不一定是準確解。由于得到的數據本身就有一定的瑕疵，因此由數據求解出的準確解也不一定是最初問題的準確解。因此，我們一般認為在求解大規模計算中求出問題的最優解就是可以接受的了，事實證明，最優解和準確解誤差不大，可以接受。

2 啟發式算法研究

2.1 基于遺傳算法的啟發式算法[2]

遺傳算法是Goldberg在1989年提出的，是一個非常有用的啟發式算法，已經在很多領域包括計算生物學如蛋白質結構預測，啟動子序列識別，多序列比對等問題中成功應用。2005年王瑞省博士將遺傳算法引入單體型重構問題，針對的是最少錯誤模型（MEC模型）。通過構造個體空間，設計適應度函數，選擇算子，設計基于遺傳算法的啟發式算法，為了驗證算法的有效性，通過ACE（血管緊縮轉移酶）基因數據集，DALY數據集進行驗證，結果顯示，設計的遺傳算法適合解決規格較大的問題。但是針對SNP錯誤率較高的時候，重構率效果不是很好。

2.2 基于粒子群算法的啟發式算法[3]

粒子群算法（PSO）最早是由心理學研究學者Kennedy博士和從事計算智能研究的Eberhart博士于1995年提出來的一種智能算法。兩位學者通過觀察鳥類捕食的過程，從中受到啟發，進而提出的一種算法。后來逐漸應用到優化問題當中，像車間調度，路由選擇，以及整數規劃問題，并且取得較好的效果。2006年錢偉懿將粒子群算法引入單體型重構問題。針對MEC模型，提出了基于改進粒子群算法的啟發式算法。它在原始粒子群算法中增加了記憶功能，提高了搜索速度。并將其應用到ACE基因數據集進行驗證算法的有效性。同時與王瑞省的遺傳算法進行了比較，表明算法的優越性，尤其是在SNP錯誤率較高的時候，基于粒子群算法的啟發式算法重構率更高。

2.3 基于前饋神經網絡的啟發式算法[4]

前饋神經網絡，簡稱前饋網絡，是人工神經網絡的一種。1986年，Rumelhart，Hinton和Williams等完整而簡明提出來的。在此種神經網絡中，各神經元從輸入層開始，接收前一級輸入，并輸入到下一級，直至輸出層。整個網絡中無反饋，可用一個有向無環圖表示。前饋神經網絡是最早被提出的人工神經網絡，也是最簡單的人工神經網絡類型。2008年章祥蓀等將前饋神經網絡引入到單體型重構問題。針對帶基因型信息的最少錯誤糾正（MEC/GI）模型，提出了基于前饋神經網絡的啟發式算法。對于MEC/GI問題由三層神經元組成。對于m個SNP片段，n個SNP位點的例子，網絡有m個輸入神經元，兩個隱含神經元和一個輸出神經元。為了驗證算法的有效性，對ACE基因數據和DALY數據集進行了測試，結果顯示算法非常有效，重構率比前面2種算法又有了提高。

3 展望

本文針對單體型裝配問題的求解方法，給出了3種主要的啟發式算法。分別是基于遺傳算法的啟發式算法，基于粒子群算法的啟發式算法，基于前饋神經網絡算法的啟發式算法。生物信息的奧秘是永無止境的，單體型在揭示人類奧秘中扮演著重要的角色。然而，人們對單體型的研究還處于起步階段，它激勵著科研工作者努力去探索未知的秘密。

參考文獻

[1]楊英杰.單體型裝配問題研究現狀[J].銅仁學院學報，2011（2）：135-138.

[2]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.

[3]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.

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