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

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

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

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

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