基于圖論的單體型重建算法設(shè)計(jì)和可視化實(shí)驗(yàn)平臺(tái)的構(gòu)建.pdf

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

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