單體型組裝加權最小字符翻轉問題參數化算法研究.pdf

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

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