個體單位型組裝問題MEC模型的算法研究與比較.pdf

1、分析和識別單體型對復雜疾病致病基因的精確定位有重要作用，但是在當前的實驗技術下直接測定個體單體型所需的時間和金錢上的花費過于昂貴，因此利用計算機技術來確定個體的單體型有其重要的現(xiàn)實意義。單體型組裝問題是利用個體DNA 測序片段數(shù)據(jù)推出該個體一對單體型的計算問題。單體型組裝問題的大部分計算模型都被證明是NP 難的，缺乏實用的算法。
　　 在單體型組裝問題的眾多模型中，MEC(Minimum Error Correction)模型是

2、最符合實際且信息丟失最少的模型?；贛EC 模型，本文在詳細研究了MCMC算法如何使用一條由單體型組成的馬爾科夫鏈來解決該組裝問題的基礎上，借鑒其建立位點結構圖的新穎思想，結合遺傳算法，提出GAMEC 算法，并針對問題設計適應度函數(shù)和啟發(fā)式算子對由單體型構成的種群進行選擇、交叉和變異。研制了計算機程序，使用模擬數(shù)據(jù)和19 號染色體上的真實數(shù)據(jù)對兩種算法分別進行實驗。實驗結果表明，兩種算法均能夠準確進行單體型估計，并且組裝出具有較高精確度