(3.236.228.250) 您好！臺灣時間：2021/04/13 12:08

### 詳目顯示:::

:

• 被引用:0
• 點閱:226
• 評分:
• 下載:0
• 書目收藏:0
 在生物學上，有一個相當重要的問題：如何建構一棵演化樹，其演化關係包含所有輸入的演化樹群，此問題被稱為公共樹問題(a consensus tree problem)，但是一般而言，輸入的演化樹群很少具有一致性(consistent)的特性，所以就產生了最佳化方面的研究：建立一棵演化樹，符合最多輸入的演化樹，此問題稱為最大公共樹問題(a maximum consensus tree problem)，而在本篇論文中，所探討的就是最大公共樹問題，且其輸入的演化樹為有根三葉樹(triple)，我們所採用的解決方法是分支與限制演算法。我們實作我們的演算法並且測試它，證明在某些情況下我們的演算法比其他演算法有更好的效率。
 In this thesis, we study the important problem that combines the evolutionary trees on overlapping leaf sets into one tree in computational biology. But the input trees are hard to consistent. So there is an optimization problem about consensus tree. Then we give a branch-and-bound algorithm to find a maximum consensus tree from rooted triple. We implement the algorithm and test it to prove our algorithm better than the other algorithms in some situation.
 1 Introduction 5 2 Preliminaries 8 3 A Branch-and-Bound Algorithm for the MCTT Problem 14 3.1 The Branch Method . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 An Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 A lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 The branch-and-bound algorithm . . . . . . . . . . . . . . . . 27 4 Experimental Results 29 4.1 The Environment of the Experiments . . . . . . . . . . . . . . 29 4.2 The Results of Running Time . . . . . . . . . . . . . . . . . . 29 5 Concluding Remarks 32
 [1] T. G. Szymanski A. V. Aho, Y. Sagiv and J. D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. COMPUT, 10(3):405-421, 1981.[2] Dan Gusfield. Effecient algorithms for inferring evolutionary trees. Networks, 21:19-28, 1991.[3] A. M. Hamel and M. A. Steel. Finding a maximum compatible tree is NP-hard for sequences and trees. Appl. Math. Lett., 9:55-59, 1996.[4] A. Lingas L. Gasieniec, L. Jansson and A. Ostlin. On the complexity of computing evolutionary trees. In Proceedings of 3rd Annual International Computing and Combinatorics Conference, pages 134-145, 1997.[5] Meei Pyng Ng and Nicholas C. Wormald. Reconsruction of rooted trees from subtrees. Discrete Applied Mathematics, 69:19-31, 1996.[6] M. Steel S. BÄocker, A.W.M. Dress. Simple but fundamental limitations on supertree and consensus tree methods. Systematic Biol., 49(2):363-368, 2000.[7] Charles Semple and Mike Steel. A supertree method for rooted trees.Discrete Applied Mathematics, 105:147-158, 2000.[8] Michael Steel. The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification, 9:91-116, 1992.[9] Bang Ye Wu. Constructing evolutionary trees from rooted triples. Journal of Information Science and Engineering, 20:181-190, 2004.[10] Bang Ye Wu. Constructing the maximum consensus tree from rooted triples. Journal of Combinatorial Optimization, 8(1):29-39, March 2004.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 李存修，民80，股票股利及現金增資之除權與股價行為：理論與實證，臺大管理論叢，第二期，1-40頁。

 1 改進一個由有根三葉樹建構最大公共樹的演算法 2 求最大2-plex問題最佳解演算法 3 以動態規劃法為基礎的旅行推銷員啟發式演算法 4 利用Google搜尋引擎實作英文文法改錯工具 5 改良有連續一特性的兩個紅/藍命中集合問題之演算法 6 權重度的生成樹研究 7 參數估計問題的軟體工具 8 兩個由四葉樹建立最大公共樹的啟發式演算法 9 探針已知探測嚴格區段圖辨識 10 動力模擬系統生物學軟體之設計與實作 11 跟據OLScriterion建造演化樹 12 弦雙分圖上最小填充問題的演算法 13 對於RMP問題，一個有效率的分支與限制演算法 14 標記支配及其相關問題 15 建構確切最小權重演化樹演算法

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室