基于加權粒子群算法的單體型裝配問題

楊英杰

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

基于加權粒子群算法的單體型裝配問題

楊英杰

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

針對單體型裝配問題的特點，提出一種求解該問題的加權粒子群算法。通過對DALY數據庫ID13進行測試，表明算法有效性。同時，與基礎粒子群算法和遺傳算法進行比較，表明我們所設計的算法在單體型重構率上優于兩者。

粒子群算法；單體型裝配；遺傳算法

0 引言

單體型是指位于一條染色體上或某一區域的一組相關聯的SNP等位基因。由于實驗條件下獲得單體型數據非常困難，也非常昂貴，由此衍生了單體型裝配問題。目前單體型裝配問題的主要方法有clark算法，分支定界算法，動態聚類算法，遺傳算法等。

粒子群算法最早是由心理學研究學者Kennedy博士和Eberhart博士提出來的一種智能算法。本文是粒子群算法在單體型裝配問題上的一個很好的應用。

1 求單體型裝配問題的加權粒子群算法

1.1 相關定義

定義1 假設由測序試驗得到了一對同源染色體DNA上含有n個SNP位點的區域上的m個排列好的SNP片段。為了計算方便，我們用1來表示正常型等位基因；用-1來表示變異型等位基因；0表示信息丟失或沒測出的基因，稱為間隙。那么，排列好的片段就可以構成上的一個階SNP矩陣。

定義4 粒子編碼：m個SNP片段的一個分類就是一個粒子，每個粒子實際上就是一個m維二進制串。

1.2 適應度函數

我們采用最少錯誤糾正模型，需定義誤差函數：對m個片段的一個劃分，確定兩條單體，從而有。最優劃分的錯誤糾正次數最少，最多的錯誤糾正次數為mn，故適應度函數為

1.3 算法流程

3）更新粒子的速度和位置

4）若迭代次數大于G，終止，否則，轉向2。

2 實驗結果與分析

2.1 ID13的重構率

給ID13單體型產生12個例子，每個例子的SNP片段分別根據以下參數隨機產生：片段個數m=40，即將每對單體型拷貝20份;片段間隙率g：0.25,0.5,0.75; 錯誤率e:0.1,0.2,0.3,0.4。對每個例子執行10次，10次執行結果的平均值列在圖1中。

圖1 加權粒子群算法在ID13上的重構率

圖2 加權粒子群算法，基礎粒子群算法，遺傳算法在ID13上的重構率

由圖1可以看出，當片段的錯誤率和片段間隙率較低時，ID13重構出的單體型重構率在百分之九十以上，與真實的單體型幾乎一致。當片段錯誤率和片段間隙率較高時，錯誤率較高。但是，實驗表明，一般情況下，我們獲取的基因組數據信息的錯誤率和間隙率都不太大（一般情況下g<0.5,e<0.2）。因此，我們設計的加權粒子群算法具有實際意義。

2.2 加權粒子群算法(MPSO)，基礎粒子群算法(PSO)，遺傳算法(GA)的比較

為了檢驗本文算法的優越性，與基礎粒子群算法，遺傳算法進行了比較，檢驗實例選擇ID13，實驗實驗數據按照3.1方式獲取，實驗結果如下。

由圖2可以看出，加權粒子群算法的重構率優于遺傳算法和基礎粒子群算法，特別是對于遺傳算法（種群數400，迭代次數150次），算法優越性體現的更好，值得推廣。

3 結束語

本文根據單體型裝配問題的特點，提出來一種適合求解單體型裝配問題的加權粒子群算法。通過對真實數據ID13進行測驗，說明了該算法的有效性，同時與遺傳算法，基礎粒子群算法進行比較，發現本文設計的加權粒子群算法重構率更高，算法性能更優。

[1] Daly M,Rioux J,Hudson T et al.High-resolution haplotype structure in human genome[J].Nature Genetics,2001,29(2): 229-232.

[2] Weiyi Qian et al ,Particle swarm optimization for SNP haplotype reconstruction problem,[J],Applied Mathematics and Computation,2008,196:266-272.

[3] Rui-Sheng Wang et al.Haplotype construction from SNP fragments by minimum error correction[J]. Oxford University Press,2005,21(10):2456-2462.

Weighed Particle Swarm Optimization for Haplotype Reconstruction Problem

Yang Yingjie
(Department of mathematics and computer,tongren university,tongren,554300,China)

A weighed swarm optimization is proposed based on haplotype reconstruction problem’s characteristics.The algorithm presented is implemented on both ID13 and is compared with basic swarm optimization and the genetic algorithm.The comparative results indicate that the proposed optimization has much higher accuracy.

particle swarm optimization;haplotype reconstruction;genetic algorithm

TP311

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

貴州省科技廳項目（黔科合J字LKT[2012]24號），銅仁學院自然科學基金(TS10018)