(1,2)-范例斷點距離的動態(tài)規(guī)劃算法研究.pdf

1、基因組重組問題是近20多年來計算生物學(xué)領(lǐng)域的研究熱點，該問題在生物演化樹重建、生物醫(yī)藥技術(shù)和發(fā)掘生物之間的親緣關(guān)系等方面有重要的應(yīng)用價值。重組排序計算結(jié)果直接用于度量兩種生命的特征差異，推導(dǎo)兩者的演化關(guān)系?？焖儆行У幕蚪M重組計算方法已經(jīng)成為分子生物學(xué)和醫(yī)學(xué)研究與實踐中探索生命演化規(guī)律的重要工具。
　　本文研究的主要內(nèi)容是(1,2)-范例斷點距離問題。在對范例斷點距離問題的研究中，D.Bryant證明(1,2)-范例斷點距離問題是

2、NP-hard。除非P=NP，(1,2)-范例斷點距離問題沒有多項式時間算法。在一個基因組中，Z.Wei和D.Zhu已經(jīng)得出兩個相同的基因家族出現(xiàn)的位置經(jīng)常是很小的物理距離。在此基礎(chǔ)上，Z.Wei和D. Zhu第一次提出解決無向(1,2)-范例斷點距離問題的固定參數(shù)動態(tài)規(guī)劃算法。其后，Z.Wei和D. Zhu通過詳細(xì)分析得出該算法的時間復(fù)雜度和空間復(fù)雜度分別為O(s4sn2)和O(s4sn)。
　　本文通過引入全局變量Map數(shù)組避

3、免重復(fù)計算基因家族的鄰接關(guān)系，將Z.Wei和D.Zhu的算法時間復(fù)雜度改進(jìn)為O(s24sn)，空間復(fù)雜度保持O(s4sn)不變；當(dāng)給定基因組是有向時，通過適當(dāng)?shù)男拚蛿U(kuò)展，本文證明Z.Wei和D.Zhu的固定參數(shù)動態(tài)規(guī)劃算法適合求解有向(1,2)-范例斷點距離；結(jié)合Map數(shù)組，該算法能在O(s24sn)時間內(nèi)實現(xiàn)；通過引入鄰接表將無向和有向固定參數(shù)動態(tài)規(guī)劃算法的空間復(fù)雜度從O(s4sn)降至O(4sn)。相關(guān)算法已經(jīng)使用C++來實現(xiàn)，仿