The Mutated Distance between Two Mixture Trees

The evolutionary tree is an important topic in bioinformation. In 2006, Chen and Lindsay proposed a new method to build the mixture tree from DNA sequences. Mixture tree is a new type evolutionary tree, and it has two additional information besides the information of ordinary evolutionary tree. One of the information is time parameter, and the other is the set of mutated sites. In 2008, Lin and Juan proposed an algorithm to compute the distance between two mixture trees. Their algorithm computes the distance with only considering the time parameter between two mixture trees. In this paper, we proposes a method to measure the similarity of two mixture trees with considering the set of mutated sites and develops two algorithm to compute the distance between two mixture trees. The time complexity of these two proposed algorithms are O(n2 × max{h(T1), h(T2)}) and O(n2), respectively

• Wan Chian Li
• Justie Su-Tzu Juan
• Yi-Chun Wang
• Shu-Chuan Chen

• evolutionary tree
• mixture tree
• mutated site
• distance.

[1] N. Saitou and M. Nei, "The neighbor-joining method: a new method for reconstructing phylogenetic trees," Mol Biol Evol, vol. 4, no. 4, pp. 406-425, Jul 1987.
[2] M. L. Lesperance and J. D. Kalbeisch, "An algorithm for computing the
nonparametric mle of a mixing distribution," Journal of the American Statistical Association, vol. 87, no. 417, pp. 120-126, Mar. 1992.
[3] M. A. Steel, "The maximum likelihood point for a phylogenetic tree is
not unique," Systematic Biology, vol. 43, pp. 560-564, 1994.
[4] G. Valiente, "A fast algorithmic technique for comparing large phylogenetic
trees," SPIRE, pp. 370-375, 2005.
[5] M. A. Steel and D. Penny, "Distributions of tree comparison metricssome
new results," Systematic Biology, vol. 42, no. 2, pp. 126-141, 1993.
[6] D. F. Robinson and L. R. Foulds, "Comparison of phylogenetic trees,"
Mathematical Biosciences, vol. 53, no. 1-2, pp. 131-147, February 1981.
[7] C. A. Meacham, G. F. Estabrook, and F. R. McMorris, "Comparison
of undirected phylogenetic trees based on subtrees of four evolutionary
units," Systematic Zoology, vol. 34, no. 2, pp. 193-200, 1985.
[8] B. Dasgupta, X. He, T. Jiang, M. Li, J. Tromp, and L. Zhang, "Proceedings
of the dimacs workshop on discrete problems with medical applications, dimacs series in discrete mathematics and theoretical
computer science," American Mathematical Society, vol. 55, pp. 125-
143, 2000.
[9] J. Bluis, D. Shin, and J. Bluis, "Nodal distance algorithm: calculating a
phylogenetic tree comparison metric," Proc. Third IEEE Symposium on
Bioinformatics and Bioengineering (D. Shin, ed.), pp. 87-94, 2003.
[10] S.-C. Chen and B. G. Lindsay, "Building mixture trees from binary
sequence data," Biometrika, vol. 93, no. 4, pp. 843-860, 2006.
[11] C.-H. Lin and J. S.-Z. Juan, "Computing the mixture distance between
mixture tree," Proceedings of the 2008 international conference on
bioinformatice & computational biology, vol. I, pp. 98-103, 2008.
[12] G. S. Brodal, R. Fagerberg, and C. N. S. Pedersen, "Computing
the quartet distance between evolutionary trees in time o(nlogn),"
Algorithmica, vol. 38, no. 2, pp. 377-395, 2003.
[13] W. T. Williams and H. T. Clifford, "On the comparison of two classifications
of the same set of elements," Taxon, vol. 20, no. 4, pp. 519-522, Aug. 1971.
[14] J. L. Kelley, General Topology I: Basic Concepts and Constructions
Dimension Theory. Encyclopaedia of Mathematical Sciences, 1990.
[15] M. J. Fortin, M. R. T. Dale, and J. V. Hoef, “Encyclopedia of environmetrics,”
vol. 4, ch. Spatial analysis in ecology, pp. 2051–2058, John
Wiley & Sons, Ltd, 2002.
[16] C.-H. Lin, “A study on measuring distance between two mixture trees,”
In Partial Fulfillment of the Requirements for the Degree of Master of
Science, Department of Computer Science and Information Engineering
National Chi Nan University, Puli, Nantou Hsien, Taiwan, Republice of
China, Juan 2008.