侯 錕

（吉林師范大學 計算機學院，長春 136000）

0 引言

如今，隨著時代的發(fā)展，科技的進步，生物工程建模已成為計算機理論及應(yīng)用領(lǐng)域內(nèi)最具吸引力、最具挑戰(zhàn)性的一個方向之一。隨著人類基因組圖譜的基本完成[1]，人們對遺傳的差異性、由基因突變引起的疾病復雜性有了更精確的闡釋[2]。現(xiàn)在人們普遍認為，DNA序列中少數(shù)的差異是導致遺傳疾病的主要原因。單核苷酸多態(tài)性(SNPs)，DNA某一位置堿基的變化[3]，被認為是一個物種不同個體表型的主要遺傳來源[4]。研究SNPs對基因的研究、遺傳疾病的診斷和藥物研制有著重要作用。

現(xiàn)存研究成果主要集中與相關(guān)理論研究。依賴于不同的數(shù)據(jù)錯誤類型，主要有幾種不同的解決模型。其中主要有最少片段刪除模型、最少SNP去除模型和另外一種被普遍應(yīng)用的模型、最少錯誤糾正模型。其中MER模型首先被Lippert等人證明是NP-hard問題[5]。實際上單體型重建問題可以被看作是一個聚類問題，這便是本文的落腳點。

本文首先將分析并給出單體型重建問題的形式化描述，設(shè)計一些必要的字符、公式定義。參考現(xiàn)存相關(guān)研究成果，提出另外一種基于k最近鄰算法和粒子群優(yōu)化算法的具有較好結(jié)果和效率的啟發(fā)式的聚類方法。進行針對性的數(shù)據(jù)模擬實驗，驗證所提出算法的科學性與高效性。

1 單體型建模過程分析

SNP位點是一個物種的基因組DNA序列中不同個體可能出現(xiàn)不同堿基的位置。位于一個SNP位點的堿基稱為等位基因。對于任意一個SNP位點來說，若兩條同源染色體上的堿基相同，則稱為純和位點；若不相同，則稱為雜合位點。幾乎所有的SNP位點上的堿基都只有兩種取值，為方便起見，我們用字符集{0,1,-}上的字符序列來表示單體型，而不必用真正的堿基字符，其中“-”表示該位點的取值未知，被稱為空。因此單體型可看作是一個字符串序列。

人類的DNA序列是按染色體成對出現(xiàn)的，每一條染色體上SNP位點上的堿基序列叫做單體型，所以人類等二倍體生物都有一對單體型。在醫(yī)學研究中，單體型數(shù)據(jù)通常比單個SNP攜帶更多的信息。基于單體型在遺傳分析上的重要性，現(xiàn)在人們較為關(guān)注的是單體型的檢測問題。

2 基于k最近鄰和粒子群優(yōu)化的聚類算法

2.1 單體型模型構(gòu)建

定義P=(C1,C2)，集合C1和集合C2描述了片段劃分到的兩個集合。定義h1=(h11,h12,…,h1n)和h2=(h21,h22,…,h2n)為一對原始的單體型，用h'=(,)表示通過算法構(gòu)造的單體型。用算法對片段進行分類后，可以通過疊加同一集合中的片段構(gòu)造h1'。

其中：i∈ (1,2)，j=1,2,…,n。

最后，用重建率(RR)來衡量單體型重建的正確度。重建率說明了重新構(gòu)建的單體型h'=(,)與原始單體型h=(h1,)之間的相似程度。定義如下：

其中：rij=D(hi,)，i=1,2；j=1,2， 并且有：

2.2 改進算法分析

本文所提出的算法思路是基于粒子群算法與k最近鄰分類算法的。其中，粒子群優(yōu)化算法是近年來發(fā)展起來的一種新的進化算法。PSO算法和遺傳算法相似，也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解；也是通過適應(yīng)度來評價解的品質(zhì)，但比遺傳算法規(guī)則更為簡單，本算法沒有遺傳算法的“交叉”和“變異”操作，本算法通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。與遺傳算法相比較，粒子群算法在大多數(shù)情況下，能較快的得到最優(yōu)化的解。

k最近鄰分類算法，是較成熟和較簡單的聚類分析算法之一。該方法的思路是：選取一個待分類樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本，如果這k個中的大多數(shù)樣本屬于某一個類別，則該待分類樣本也屬于這個類別。

2.3 改進算法描述

將粒子群算法和部分的k最近鄰算法結(jié)合起來達到優(yōu)化結(jié)果的目的。

首先，計算出任意兩條SNP片段之間的距離，找出距離最大者，并將相對應(yīng)的兩條片段分別放到集合C1和C2中，作為集合劃分的初始值。接下來，在每次分配過程中，通過粒子群算法為未劃分的每一條片段分別從集合C1和C2中選取k'條片段。其中k'的取值可由以下公式?jīng)Q定：

3 實驗設(shè)計與結(jié)果分析

試驗中采用真實數(shù)據(jù)和模擬數(shù)據(jù)來檢驗算法的準確性。并在四核中央處理器、內(nèi)存最低為2GB的微機系統(tǒng)上用Java語言運行。

3.1 模擬數(shù)據(jù)實驗

首先，用模擬數(shù)據(jù)來測試本文提出的改進算法。首先，隨機生成10條不同的單體型，每條單體型長度為60，并通過相似度參數(shù)s來生成對應(yīng)的10條單體型，其中：

s表示一對單體型中兩條單體型之間的相似度。然后采用著名的shotgut測序模擬數(shù)據(jù)生成器Celsim來生成實驗所需片段。通過設(shè)置參數(shù)片段數(shù)m=100；s=0.5；SNP缺失率g分別為0.25；0.5和0.75；錯誤率e分別為0.1，0.2，0.3，0.4來產(chǎn)生每對單體型的12個實例。然后用以上相同的參數(shù)設(shè)置，除了s設(shè)置為0以外，產(chǎn)生另外120個實例。改進算法運行模擬數(shù)據(jù)的結(jié)果顯示在圖1中，縱坐標代表重建率(RR)，橫坐標代表錯誤率(e)。

圖1 不同參數(shù)下改進算法的重建率

圖1中的(a)、(b)圖分別是針對相似度參數(shù)S=0.5和S=0時，該算法在不同的錯誤率，不同缺失率下相對應(yīng)的結(jié)果。圖1表明單體型之間的相似度越高，重建率越高。同時也表明隨著片段錯誤率、SNP缺失率的增大，算法的重建率逐漸降低。

3.2 真實數(shù)據(jù)實驗

實驗中用到的真實數(shù)據(jù)采用來自公開數(shù)據(jù)庫的真實的單體型，該數(shù)據(jù)來自于國際人類基因組單體型圖計劃2006年7月發(fā)布的數(shù)據(jù)文件件中包含了CEPH樣本(祖籍是北歐或西歐的美國猶他州人)中60個個體的單體型，每個單體型有SNP位點193,333個，本文實驗隨機選擇一個個體指定長度的一對單體型。

本文采用著名的shotgun測序模擬數(shù)據(jù)生成器Celsim來生成實驗所需片段。其中所需設(shè)置的參數(shù) m：40，160，300；g：0.25，0.5和 0.75；e：0.1，0.2，0.3，0.4。表1是利用真實數(shù)據(jù)，在相同的條件下，把本文提出的算法與現(xiàn)存聚類算法進行比較的實驗結(jié)果。

從表1中可以看出，在相同的缺失率、錯誤率的情況下，本文提出的算法能得到更好的實驗結(jié)果。尤其是在錯誤率很大的情況下，該算法較現(xiàn)存算法依然能取得較好的實驗結(jié)果。

表1 現(xiàn)存算法與本文提出改進算法的結(jié)果比較

4 結(jié)束語

本文設(shè)計了一種啟發(fā)式的數(shù)據(jù)聚類算法，從兩個集合中同時選擇k1條片段作為片段劃分的依據(jù)是對現(xiàn)存相關(guān)聚類算法的改進，通過采用模擬數(shù)據(jù)和真實數(shù)據(jù)檢驗了改進算法的有效性。實驗結(jié)果表明，該改進算法能取得更好更精確的結(jié)果，同時也提高了執(zhí)行效率。

[1] The International HapMap Consortium. A haplotype map of the human genome. Nature, 2005, 437: 1299-1320.

[2] Z. Li, W. Zhou, X. Zhang and L. Chen. A parsimonious tree-grow method for haplotype inference. Bioinformatics,2005, 21(17): 3475-3481.

[3] R. S. Wang, L. Y. Wu, Z. P. Li and X. S. Zhang. Haplotype re-construction from SNP fragments by minimum error correction. Bioinformatics, 2005, 21(10): 2456-2462.

[4] X. S. Zhang, R. S. Wang. Models and algorithms for haplotyping problem. Current Bioinformatic, 2006, 1(1):105-114.

[5] 楊廣文, 鄭緯民, 王鼎興, 等. 一種有效的啟發(fā)式聚類算法[J]. 電子學報, 1999,27(2): 90-91.

[6] 金萍, 宗瑜, 李明楚,等. 共有信息引導的啟發(fā)式聚類算法[J]. 計算機工程與應(yīng)用, 2010, 46(31):50-53, 71. DOI:10.3778/j.issn.1002-8331.2010.31.014.

[7] 徐選華, 范永峰. 改進的蟻群聚類算法及在多屬性大群體決策中的應(yīng)用[J].系統(tǒng)工程與電子技術(shù), 2011, 33(2):346-349.