在生物學上，有一個相當重要的問題：如何建構一棵演化樹，其演化關係包含所有輸入的演化樹群，此問題被稱為公共樹問題(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.