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

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

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

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