(3.236.228.250) 您好!臺灣時間:2021/04/13 12:08
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:董佲昌
研究生(外文):Ming-Chang Doung
論文名稱:由有根三葉樹建立最大公共樹的演算法
論文名稱(外文):An Exact Algorithm for Constructing a Maximum Consensus tree from Rooted Triples
指導教授:張貿翔張貿翔引用關係
指導教授(外文):Maw-Shang Chang
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:34
中文關鍵詞:公共樹三葉樹
外文關鍵詞:consensus treetriplesexact
相關次數:
  • 被引用被引用: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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔