系統(tǒng)發(fā)生樹(shù)重建的resolved triple方法.pdf

1、系統(tǒng)發(fā)生學(xué)是進(jìn)化生物學(xué)的一個(gè)重要研究領(lǐng)域，而系統(tǒng)發(fā)生分析早在達(dá)爾文時(shí)期就已經(jīng)開(kāi)始了．系統(tǒng)發(fā)生是指生物形成或進(jìn)化的歷史，系統(tǒng)發(fā)生學(xué)研究物種之問(wèn)的進(jìn)化關(guān)系，其基本思想是比較物種的特征，井認(rèn)為特征相似的物種在遺傳學(xué)上接近．系統(tǒng)發(fā)生研究的結(jié)果往往以系統(tǒng)發(fā)生樹(shù)表示，用它描述物種之間的進(jìn)化關(guān)系．通過(guò)對(duì)生物學(xué)數(shù)據(jù)的建模提取特征，進(jìn)而比較這些特征，研究生物形成或進(jìn)化的歷史． 近些年來(lái)，重建系統(tǒng)發(fā)生樹(shù)的resolved quaret方法越來(lái)越手到

2、分子生物界的關(guān)注．給定系統(tǒng)發(fā)生樹(shù)T，{n，b，c，d}足其葉子節(jié)點(diǎn)子集ab｜c(diǎn)d表示樹(shù)T中ab-路與cd-路不交，稱為resolvrd quartet．對(duì)于系統(tǒng)發(fā)生樹(shù)T，其resolced quarted集Q(T)是唯一確定的，這正式resoIred quartet方法的基本依據(jù)，但是resolved quartet集的兼容性問(wèn)題NP-hard的，不存在多項(xiàng)式時(shí)間算法． 本文提出了resolred triple．方法，不僅可以在

3、多項(xiàng)式時(shí)間內(nèi)重建系統(tǒng)發(fā)生樹(shù)，還可以檢驗(yàn)resolved triple集的兼容性．給定系統(tǒng)發(fā)生樹(shù)T，{a，b，c}是其葉子節(jié)點(diǎn)子集，符號(hào)ab｜c(diǎn)表示T中存在內(nèi)部節(jié)點(diǎn)ν.ν.使得a，b，c∈des(u)a、b ∈des(ν)，c ∈，des(ν)．稱為有resolvedtripl．我們首先通過(guò)特定規(guī)則建立resoled triple集R相對(duì)應(yīng)的有向圖G<,R>，對(duì)G<,R>中點(diǎn)不交有向路{pκ}兩兩進(jìn)行一系列規(guī)的化簡(jiǎn)，最終得到R的基．在第4

4、部分中，我們利用resoIved quartet集對(duì)此方法做出證呱并給出resolved quartet集兼容的必要條件． 本文由四部分組成： 第一章：引言，敘述問(wèn)題的由來(lái)． 第二章：經(jīng)典結(jié)論及基本定義，主要敘述前人的一些經(jīng)典方法并定義本文所涉及的基本符號(hào)． 第三章:resolvel triple集的兼容性及多項(xiàng)式時(shí)間算法，這是本文最霞要的一章，也是最核心的一章．在這一章中，通過(guò)對(duì)有向圖G<,R>的分析提