基于圖論的單體型重建算法設(shè)計和可視化實驗平臺的構(gòu)建.pdf

1、分析和識別單體型對基因的精確定位、了解基因功能、復(fù)雜疾病診斷和藥物研究等有著重要作用。不幸的是，由于當(dāng)前實驗條件的限制，通過生物學(xué)方法直接測定個體單體型所需的時間和金錢花費十分昂貴，利用計算機(jī)技術(shù)來確定個體單體型具有極其重要的現(xiàn)實意義。單體型組裝問題是利用個體DNA片段測序結(jié)果獲取一對完整單體型的問題，目前大部分單體型組裝問題的計算模型都被證明是NP難的，因此設(shè)計快速準(zhǔn)確的單體型重建算法來解決單體型組裝問題成為生物信息學(xué)的一個重要研究方

2、向。
　　我們首先對單體型組裝問題已有的計算模型和重建算法進(jìn)行了研究，進(jìn)而通過對重建過程的分析，提出了一種新的算法。該算法根據(jù)SNP位點之間相同或相異的關(guān)系把SNP矩陣轉(zhuǎn)化為位點關(guān)聯(lián)圖，通過尋找位點關(guān)聯(lián)圖的無沖突著色序列來完成重建過程。實驗表明，我們提出的這個算法擁有良好的性能表現(xiàn)，能夠準(zhǔn)確的進(jìn)行單體型重建。與目前性能優(yōu)秀的另外兩種算法相比，在同等情況下該算法所需的運行時間更短，具有較高的實用價值。
　　一個算法性能的優(yōu)劣要