單體型組裝加權(quán)最小字符翻轉(zhuǎn)問題參數(shù)化算法研究.pdf

1、單體型檢測在遺傳病基因的定位、藥理反應(yīng)的研究、個體識別等方面有極其廣闊的應(yīng)用前景。但是在當(dāng)前的實驗技術(shù)下直接測定個體的單體型所需的時間和金錢上的花費過于昂貴，因此利用計算機技術(shù)來確定個體的單體型有極其重要的現(xiàn)實意義。單體型檢測可分為兩大類：單體型組裝問題和單體型推斷問題。本文主要對單體型組裝問題相關(guān)模型和算法進行研究。 由于單體型組裝問題計算模型絕大部分是NP-hard，當(dāng)片斷數(shù)和SNP位點數(shù)較大時，基本上沒有可行的精確算法，而

2、諸如啟發(fā)式算法、遺傳算法等近似算法的近似程度很難保證，往往不能獲得最優(yōu)解。因而盡可能提高精確算法的時間和空間效率具有極其重要的現(xiàn)實意義。 本文著重探索了如何利用小參數(shù)技術(shù)顯著降低相關(guān)計算模型的時間和空間復(fù)雜度，并針對單體型組裝加權(quán)最小字符翻轉(zhuǎn)(WMLF)問題提出了一個時間復(fù)雜度為O(nk22k2+mlogm+mk1)的參數(shù)化算法，可以在較短的時間得到WMLF問題的精確解，具有良好的可擴展性和較高的實用價值。 參數(shù)化算法是