基於優化解集合的個體單體型重建方法

2023-12-09 08:51:46

專利名稱：：基於優化解集合的個體單體型重建方法
技術領域：
：本發明涉及生物信息學，特別涉及個體單體型的重建。技術背景人類基因組測序工作完成之後，遺傳差異性研究己成為基因組的熱點研究之一。眾所周知，人類幾乎有99.9%的基因是相同的，因此我們所呈現出的外部差異性僅僅是由於0.1%的基因差異引起的。在各種遺傳變異之中，單核苷酸多態性(singlenucleotidepolymorphisms,SNPs)是最顯著的一種形式，它是人類染色體某個位點上的鹼基變化。研究SNP在闡明疾病易感性機制、設計個體化治療方案和藥物研製等方面都具有重要意義和實際應用價值。然而，檢測人類染色體上所有一千萬個常見SNPs的費用極其昂貴，所幸的是，由於連鎖不平衡現象以及缺乏重組事件，一些相鄰的多態位點趨於在一起共同遺傳，這些變異連鎖的區域即為單體型(haplotype)，它定義為一條染色單體上某一區域的一組相關聯的SNP位點。最近的研究表明，在與疾病相關的研究中，單體型數據通常比單個SNP攜帶更多的信息，但在當前的實驗技術下，直接通過生物學實驗手段來測定單體型既費錢又費時間，因此利用計算機技術來確定個體的單體型有極其重要的現實意義。個體單體型重建問題可描述如下給定一組來自某對同源染色體的由DNA測序方法得到的DNA片斷，若只關注SNP位點，這些DNA片斷即為SNP片斷。單體型重建問題是要根據片斷上SNP位點的狀態信息將這些片斷分成兩個集合，每個集合中的片斷組裝成一條單體型。由於在DNA測序過程中會產生測序錯誤，而且當片斷中存在錯誤時，無法準確地對片斷進行分組。因此，在2002年，Lippert等提出了最少錯誤更正(theminimumerrorcorrection,MEC)模型，它要求通過更正最少的片斷錯誤來重建單體型，目前求解該模型的方法主要有(1)王瑞省等提出的基於分支定界思想的方法，但由於MEC模型是NP難的，該方法無法求解大規模問題。(2)王瑞省等提出兩種動態聚類方法(文中稱為DC1和DC2)以及一種基於遺傳算法的啟發式方法(文中稱為GA)。一對重建率最高的單體型數據。但是由於MEC模型及方法本身的原因，最優結果會在問題求解過程中被遺失，從而使結果單體型重建率並不高。
發明內容為了解決上述基於MEC模型的個體單體型重建方法存在的技術問題，本發明提供了一種基於優化解集合求解MEC模型的重建方法。該方法能夠生成一個小規模的優化解集合，且基於該優化解集，能夠獲得較以往方法更高重建率的單體型。本發明基於MEC模型解決個體單體型重建問題，包括以下步驟預處理SNP矩陣，得到只含雜合位點的SNP矩陣。通過粒子群優化策略得到一個小規模的優化解集合，即只具有雜合位點的單體型對集合。最後的擴展階段將預處理階段刪掉的SNPs重新加上，得到最終的單體型對集合。上述的基於優化解集合的個體單體型重建方法，粒子群優化策略採用二進位串X(x^2，…入)(;c,e(0,U)和r(v!，V2，…,v")(v,E(o,l))來分別表示一個粒子的位置和速度，粒子位置代表一條只含雜合位點的單體型。上述的基於優化解集合的個體單體型重建方法，某個粒子位置X對應的錯誤更正數E(X)的計算方式如下ml=Zmin(s(y;,^o,DC/;，;n)上式中ml表示預處理後SNP矩陣的行數，,表示SNP矩陣中的行(SNP片斷)，S(/;，^)表示力和X對應位取值相同(同為1或同為0)的位數，D(/;，X)表示力和義對應位取值相異(一個為1則另一個為0)的位數。本發明的技術效果在於本發明提出一種生成小規模優化解集合以降低最優解遺失概率的新研究思路。基於這種研究思路，針對SNP位點雜合率較低的特點，設計了一種短的粒子編碼，給出求解MEC模型的粒子群優化方法。這種短粒子編碼一方面能夠有效控制解空間的大小，使本發明更容易獲得最優解；另一方面它使粒子群優化策略能夠使用小的群體規模，繼而可以生成一個小規模的優化解集合，解集合中的解均與粒子群中的&有相同的適應值，但它們的重建率不一定相同。優化解集合的研究思路與短粒子編碼方式的結合使用，使得本發明能夠獲得比以往相關方法更高的單體型重建率。另外，由於群體規模得到控制，本發明即使在求解大規模問題時，仍具有較高的執行效率，因此具有很高的實用價值。圖l:本發明的流程圖。具體實施方式下面結合附圖對本發明的具體實施作進一步說明。參見圖l，圖l為本發明的流程圖，虛線框部分表示粒子群優化方法。本發明中預處理SNP矩陣^4^，去掉對重建工作沒有幫助的冗餘信息，即刪除M中所有滿足條件/o^或/!2的列(在矩陣M43，令為某一列中值為:c的元素個數，且/^"乂(",+"k))，這裡f設置為0.2，若被刪除的列中大部分非空元素值為O，則稱其為0-列，否則稱為l-列。將所有滿足上述條件的列刪除之後，某些行將變成空行(元素值全為-)，它們對於重建工作沒有任何幫助，因此也將其刪除。預處理後得到只含雜合位點的SNP矩陣Ml^w。實施粒子群優化策略，將與屍g適應值相同的A:個解均保留下來，並將&個解轉換成只含雜合位點的單體型對///=(/2,「，//12)(/=1,..."，以得到一個規模為^:的優化解集合//={//1'，...)/4'}。最後的擴展階段將預處理階段刪掉的SNPs重新加上，對於優化解集//中只含雜合位點的單體型對///=(/2,「,如果某個已被刪除的同合位點為O-列(l-列)，則將O(1)插回到單體型對(&'，/2,2)的相應位置，以此得到擴展後的單體型對i/屍(&，擴展結束後得到最終的單體型對集合i^(/Zh…凡)。基於這種生成小規模優化解集的研究思路，本發明設計了一種短的粒子編碼，從而提出求解MEC模型的粒子群優化方法。這種短的粒子編碼採用二進位串1(>1力，...^1)(^￡{0，1})來表示一個粒子的位置，它代表一條只含雜合位點的單體型。如前所述，新矩陣M1中的片斷只保留了雜合位點，則由它們構建的單體型必定也只具有雜合位點。由於一對單體型在其雜合位點上的值是相異的(一個值為O(l)，另一個值則為l(O))，因此對於這樣一對只具有雜合位點的單體型，可以通過其中一條推導出另一條。所以，由一個粒子的位置可以推導出一對只含雜合位點的單體型。將粒子群優化方法運用於離散問題時，需要對粒子的速度表示及粒子間的運算操作進行定義(a)粒子的速度r定義為其兩次位置《和Z2之間的距離。F』畫X2,，…，0，formulaseeoriginaldocumentpage7(b)速度^和^間的加法操作定義為其相應位的邏輯加，結果為速度formulaseeoriginaldocumentpage7(c)粒子速度R與概率C的乘積，結果為速度F。formulaseeoriginaldocumentpage7否則.formulaseeoriginaldocumentpage7(d)速度K和位置《間的加法操作定義為其相應位的邏輯異或，結果為位置丄formulaseeoriginaldocumentpage7適應度函數用於評價粒子的搜索性能，指導粒子群的搜索過程。給定某個粒子位置X及矩陣m1中的所有片斷乂"=7,...，/771,X的適應度函數H^MfX」定義為formulaseeoriginaldocumentpage7其中，粒子位SY表示一對僅含雜合位點的單體型(/2/,^')中的一條，例如/n'。於是s(/;"表示片斷力與單體型/i/間等位基因相同的位點個數，即片斷乂與單體型/z2'間等位基因相異的位點個數；d(/;,"表示片斷力與單體型/zr間等位基因相異的位點個數；五CY)表示對應於單體型對(^'，/72)的最少錯誤更正數。綜上所述，優化解集合的研究思路與短粒子編碼方式的結合使用可以有效降低最優解的遺失概率，從而獲得具有更高重建率的單體型。利用計算機模擬真實生物數據的特徵生成測試數據集進行實驗測試。實驗在一臺安裝了WindowsXPProfessional作業系統的IBM工作站(IntelPentiumIV2.0GHz，內存為512MB)上進行，程序編譯器為MicrosoftVisualC++6.0。本發明中用"重建率"和"運行時間"來測試本發明方法的性能。在本發明的優化解集合/7中選取重建率最大的單體型對作為結果，即該方法結果單體型對的重建率為1113乂{^(//1),...，朋(/4)}(//1,...^^//)。表1到表5中的每個計算結果均為100次重複測試的平均值。在下面的實驗中，本發明的參數設置如下w=0.8，C產C產0.7，群體規模7V為20，迭代次數肘-/7^7為100。表1至表3的實驗結果顯示本發明能夠獲得較現有方法更高重建率的單體型對，這說明優化解集的研究思路能有效避免最優解的遺失。表中&表示優化解集合//中平均單體型的對數，其平均值均不超過4對，滿足了解集合規模不宜太大的要求。本發明引入的粒子編碼較短，使得本發明能夠採用小規模種群，這為生成小規模的優化解集合奠定了基礎。表l重建率的比較(c-5，"-100)tableseeoriginaldocumentpage8表2重建率的比較("=100，屍,=0.05)及及tableseeoriginaldocumentpage8表3重建率的比較(e5，屍5=0.05)"tableseeoriginaldocumentpage8表4運行時間比較("=100,屍,=0.05)tableseeoriginaldocumentpage9表5運行時間比較(c-5，屍,=0.05)tableseeoriginaldocumentpage9表4和表5的結果顯示，GA方法的運行時間最長，方法DC1和DC2運行速度較快，最長時間不超過0.1秒，雖然本發明比這兩種動態聚類方法運行得慢，但最多也只需花費幾秒鐘，因此具有很高的實用價值。從以上實驗數據看來，應用本發明方法的得到的重建率和花費的運行時間均比較理想，這是因為本發明成功地將優化解集合的研究思路與粒子群優化方法相結合，通過引入短的粒子編碼方式，使粒子群優化策略能夠使用小的群體規模，這使得通過生成優化解集合來降低最優解的地遺失概率成為可能，且由於群體規模得到控制，本發明即使在求解大規模問題時，仍具有較高的執行效率，因此具有很高的實用價值。另外短粒子編碼還能夠有效控制解空間的大小，使本發明更容易獲得最優解。權利要求1.一種基於優化解集合的個體單體型重建方法，包括以下步驟(1)預處理SNP矩陣Mm×n，去掉對重建工作沒有幫助的冗餘信息，即刪除M中所有滿足條件f0≤t或f1≤t的列，在矩陣M中，令nx為某一列中值為x的元素個數，且fx＝nx/(nx+n1-x)，t設置為0.2，若被刪除的列中大部分非空元素值為0，則稱其為0-列，否則稱為1-列，將所有滿足上述條件的列刪除之後，得到只含雜合位點的SNP矩陣M1m1×n1；(2)通過粒子群優化策略得到一個小規模的優化解集合，即只具有雜合位點的單體型對集合，將與Pg適應值相同的k個解均保留下來，並將k個解轉換成只含雜合位點的單體型對Hi』＝(hi1』，hi2』)(i＝1，...，k)，以得到一個規模為k的優化解集合H』＝{H1』，...，Hk』}；採用二進位串X(x1，x2，...，xn)(xi∈{0，1})和V(v1，v2，...，vn)(vi∈{0，1})來分別表示一個粒子的位置和速度，粒子的速度表示及粒子間的運算操作定義如下(a)粒子的速度V定義為其兩次位置X1和X2之間的距離；V＝X1-X2＝(v1，...，vn)，全文摘要本發明公開了一種基於優化解集合的個體單體型重建方法，包括以下步驟預處理單核苷酸多態性(singlenucleotidepolymorphism，SNP)矩陣，去掉對重建工作沒有幫助的冗餘信息，得到只含雜合位點的SNP矩陣。通過粒子群優化策略得到一個小規模的優化解集合，即只帶有雜合位點的單體型對集合。最後的擴展階段將預處理階段刪掉的SNPs重新加上，得到最終的單體型對集合。本發明提出基於小規模優化解集合求解MEC模型的個體單體型重建方法，該方法可以獲得比以往相關方法更高的單體型重建率，並且在求解大規模問題時仍具有較高的執行效率。文檔編號G06F19/00GK101256602SQ20081003083公開日2008年9月3日申請日期2008年3月18日優先權日2008年3月18日發明者吳璟莉,王建新申請人:中南大學