The Mutated Distance between Two Mixture Trees

Authors: Wan Chian Li, Justie Su-Tzu Juan, Yi-Chun Wang, Shu-Chuan Chen

Abstract:

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

Keywords: evolutionary tree, mixture tree, mutated site, distance.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335050

References:

[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.