從k棵演化樹中，找出以leaf-agree為基礎的同構子樹的問題定義如下：有k棵演化樹，其中，每一棵演化樹的葉子的數量相同（n個葉子）而且葉子的標示符號（labels）亦相同，每個標示符號為唯一，可被視為一個物種；不同樹中，相同的標示符號代表同一物種，在這k棵樹裏面，找出對應的內部節點組合（k-tuples），組合內的第一個元素表示第一棵樹的某一內部節點、組合內的第二個元素表示第二棵樹的某一內部節點，以此類推，組合內的k個元素正好對應到k棵樹，滿足在以這些組合元素為樹根（root）的子樹以下，所有的子樹的葉子標號均相同，且所有子樹結構亦相同。本篇論文更進一步地將上述定義條件更改成每棵樹的葉子標示符號可以不儘相同，而且葉子數目亦可以不相等。對於這個新問題，我們提出了一個時間複雜度為O(kn)的演算法來處理之，並且實作了一個web介面的系統來供實驗使用，此系統可以透過網際網路在http://140.116.82.162/~project/index-e.html中直接使用瀏覽器操作。

The leaf-agree isomorphic(or just isomorphic) subtree problem is the following. Given k rooted trees whose leaves are drawn from the same set of items(e.g., species), find all subset of these items so that portions of the trees restricted to the subset are leaf-agree isomorphic. Moreover, we redefine this problem by drawing leaves of k trees from different sets. In this paper, we present an O(kn) time solution for this new problem. Finally, We also implement a web-based system, the web server can be accessed through the website http://140.116.82.162/~project/index-e.html.

[1] Y.L. Lin, T.S. Hsu: Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome. ISAAC 339-351, 2003.

[2] A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing, 10(3):405-421, 1981.

[3] B. L. Allen and M. Steel. Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics, 5:1-13, 2001.

[4] A. Amir and D. Keselman. Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. SIAM Journal on Computing, 26(6):1656-1669, 1997

[5] V. Berry and O. Gascuel. Inferring evolutionary trees with strong combinatorial evidence. Theoretical Computer Science, 240(2):271-298, 2000.

[6] P. Bonizzoni, G. Della Vedova, and G. Mauri. Approximating the maximum isomorphic agreement subtree is hard. In R. Giancarlo and D. Sankoff editors, Proceedings of the11th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science 1848, pages 119-128, Montreal, Canada, 2000.

[7] G.S. Brodal, R. Fagerberg, and C.N. Pedersen. Computing the quartet distance between evolutionary trees in time O(nlog^2n). ISAAC, Lecture Notes in Computer Science, 2223:731-742, 2001.

[8] D. Bryant. Building Trees, Hunting for Trees, and Comparing Trees. PhD thesis, University of Canterbury, Christchurch, New Zealand, 1997.

[9] R. Cole, M. Farach, R. Hariharan, T. Przytycka, and M. Thorup. An O(nlogn) algorithm for the maximum agreement subtree problem for binary trees. SIAM Journal on Computing, 30(5):1385-1404, 2002.

[10] DasGupta, He, Jiang, Li, Tromp, and Zhang. On distances between phylogenetic trees. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 427-436, 1997.

[11] W.H.E. Day. Optimal algorithms for comparing trees with labelled leaves. Journal of Classification, 2:7-28, 1985.

[12] G. Estabrook, F. McMorris, and C. Meacham. Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units. Systematic Zoology, 34(2):193-200, 1985.

[13] M. Farach, T.M. Przytycka, and M. Thorup. On the agreement of many trees. Information Processing Letters, 55(6):297-301, 1995.

[14] M. Farach and M. Thorup. Sparse dynamic programming for evolutionary-tree comparison. SIAM Journal on Computing, 26(1):210-230, 1997.

[15] J. Felsenstein. Numerical methods for inferring evolutionary trees. Quarterly Review on Biology, 57(4):379-404, 1982.

[16] W. M. Fitch. Toward defining the course of evolution: Minimal change for a specific tree topology. Systematic Zoology, 20:406-441, 1971.

[17] D. Gilbert, D. Westhead, N. Nagano, and J. Thornton. Motif-based searching in tops protein topology databases, 1999.

[18] D. Gusfield. Efficient algorithms for inferring evolutionary trees. Networks, 21:19-28, 1991.

[19] D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984.

[20] J. Hein, T. Jiang, L. Wang, and K. Zhang. On the complexity of comparing evolutionary trees. Discrete Applied Mathematics, 71:153-169, 1996.

[21] J.A. Hoch and T.J. Silhavy. Two-Component Signal Transduction. ASM Press, 1995.

[22] Y.L. Lin. Two component systems sequence characteristics identifiation in bacterial genome. In Sixth Proceedings World Multiconference on Systemics,Cybernetics and Informatics (SCI'2002), pages 445-449, Orlando, Florida, 2002.

[23] J.S. Parkinson and E.C. Kofoid. Communication modules in bacterial signalling proteins. Annu. Rev. Genet., 26:71-112, 1992.

[24] D. F. Robinson and L. R. Foulds. Comparison of weighted labelled trees. In Combinatorial mathematics, VI (Proc. Sixth Austral. Conf., Univ. New England, Armidale), Lecture Notes in Mathematics 748, pages 119-126. Springer-Verlag, Berlin, 1979.

[25] D. F. Robinson and L. R. Foulds. Comparison of phylogenetic trees. Math. Biosci, 53(1-2):131-147, 1981.

[26] A. Rodrigue, Y. Quentin, A. Lazdunski, V. Mejean, and M. Foglino. Two-component systems in pseudomonas aeruginosa: why so many? Trends Microbiol., 8:498-504, 2000.

[27] N. Saitou and M. Nei. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology Evolution, 4:406-425, 1987.

[28] K. Strimmer and A. von Haeseler. Quartet puzzling: a quartet maximum-likelihood method for reconstructing tree topologies. Molecular Biology and Evolution, 13(7):964-969, 1996.

[29] P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6:80-82, 1977.

[30] M. S.Waterman and T. F. Smith. On the similarity of dendrograms. Journal of Theoretical Biology, 73:789-800, 1978.

[31] M. Steel, T. Warnow. Kaikoura tree theorems: computing the maximum agreement subtree. Infomation Processing Letters, 48,pp. 77-82, 1993.