{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:24:44Z","timestamp":1760239484076,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,11,28]],"date-time":"2020-11-28T00:00:00Z","timestamp":1606521600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The ancestral mixture model, an important model building a hierarchical tree from high dimensional binary sequences, was proposed by Chen and Lindsay in 2006. As a phylogenetic tree (or evolutionary tree), a mixture tree created from ancestral mixture models, involves the inferred evolutionary relationships among various biological species. Moreover, it contains the information of time when the species mutates. The tree comparison metric, an essential issue in bioinformatics, is used to measure the similarity between trees. To our knowledge, however, the approach to the comparison between two mixture trees is still unknown. In this paper, we propose a new metric named the mixture distance metric, to measure the similarity of two mixture trees. It uniquely considers the factor of evolutionary times between trees. If we convert the mixture tree that contains the information of mutation time of each internal node into a weighted tree, the mixture distance metric is very close to the weighted path difference distance metric. Since the converted mixture tree forms a special weighted tree, we were able to design a more efficient algorithm to calculate this new metric. Therefore, we developed two algorithms to compute the mixture distance between two mixture trees. One requires O(n2) and the other requires O(nh1h2) computational time with O(n) preprocessing time, where n denotes the number of leaves in the two mixture trees, and h1 and h2 denote the heights of these two trees.<\/jats:p>","DOI":"10.3390\/a13120314","type":"journal-article","created":{"date-parts":[[2020,11,28]],"date-time":"2020-11-28T03:51:16Z","timestamp":1606535476000},"page":"314","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Approaches to the Mixture Distance Problem"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3654-2560","authenticated-orcid":false,"given":"Justie Su-Tzu","family":"Juan","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chi Nan University, Puli, Nantou 54561, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi-Ching","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei 10617, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen-Hui","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chi Nan University, Puli, Nantou 54561, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shu-Chuan","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Idaho State University, Pocatello, ID 83209, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,28]]},"reference":[{"key":"ref_1","first-page":"406","article-title":"The neighbor-joining method: A new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1080\/01621459.1992.10475182","article-title":"An algorithm for computing the nonparametric MLE of a mixing distribution","volume":"87","author":"Lesperance","year":"1992","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1093\/biomet\/93.4.843","article-title":"Building mixture trees from binary sequence data","volume":"93","author":"Chen","year":"2006","journal-title":"Biometrika"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1186\/1471-2105-12-111","article-title":"MixtureTree: A program for constructing phylogeny","volume":"12","author":"Chen","year":"2011","journal-title":"BMC Bioinform."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1214\/ss\/1177010378","article-title":"Ancestral inference in population genetics","volume":"9","author":"Griffiths","year":"1994","journal-title":"Statist. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"6720","DOI":"10.1073\/pnas.88.19.8720","article-title":"Extensive mitochondrial diversity within a single amerindian tribe","volume":"88","author":"Ward","year":"1991","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1093\/sysbio\/43.4.560","article-title":"The maximum likelihood point for a phylogenetic tree is not unique","volume":"43","author":"Steel","year":"1994","journal-title":"Syst. Biol."},{"key":"ref_8","first-page":"131","article-title":"Comparison of phylogenetic trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Biosciences"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"193","DOI":"10.2307\/2413326","article-title":"Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units","volume":"34","author":"Estabrook","year":"1985","journal-title":"Syst. Zool."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1090\/dimacs\/055\/09","article-title":"On computing the nearest neighbor interchange distance","volume":"Volume 55","author":"Dasgupta","year":"2000","journal-title":"Proceedings of the Discrete Mathematical Problems with Medical Applications: DIMACS Workshop on Discrete Problems with Medical Applications"},{"key":"ref_11","unstructured":"Bluis, J., and Shin, D. (2003, January 12). Nodal distance algorithm: Calculating a phylogenetic tree comparison metric. Proceedings of the Third IEEE Symposium on BioInformatics and BioEngineering, Bethesda, MD, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Robinson, D.F., and Foulds, L.R. (1979). Comparison of weighted labelled trees. Combinatorial Mathematics VI, Springer.","DOI":"10.1007\/BFb0102690"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1006\/aama.2001.0759","article-title":"Geometry of the space of phylogenetic trees","volume":"27","author":"Billera","year":"2001","journal-title":"Adv. Appl. Math."},{"key":"ref_14","first-page":"126","article-title":"Distributions of tree comparison metrics\u2014Some new results","volume":"42","author":"Steel","year":"1993","journal-title":"Syst. Biol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01908061","article-title":"Optimal algorithms for comparing trees with labeled leaves","volume":"2","author":"Day","year":"1985","journal-title":"J. Classif."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1089\/cmb.2007.R012","article-title":"Efficiently computing the Robinson-Foulds metric","volume":"14","author":"Pattengale","year":"2007","journal-title":"J. Comput. Biol."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1196","DOI":"10.1109\/TCBB.2010.121","article-title":"An efficient algorithm for approximating geodesic distances in tree space","volume":"8","author":"Battagliero","year":"2010","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.ipl.2007.02.008","article-title":"Approximating geodesic tree distance","volume":"103","author":"Amenta","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TCBB.2010.3","article-title":"A fast algorithm for computing geodesic distances in tree space","volume":"8","author":"Owen","year":"2010","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_20","unstructured":"Felsenstein, J. (2004). Inferring Phylogenies, Sinauer Associates."},{"key":"ref_21","first-page":"88","article-title":"The LCA problem revisited","volume":"1776","author":"Bender","year":"2000","journal-title":"Lat. Am. Theor. Inform."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/s00453-003-1065-y","article-title":"Computing the quartet distance between evolutionary trees in time O(nlogn)","volume":"38","author":"Brodal","year":"2003","journal-title":"Algorithmica"},{"key":"ref_23","unstructured":"Lee, R.C.T., Chang, R.C., Tseng, S.S., and Tsai, Y.T. (2005). Introduction to the Design and Analysis of Algorithms, McGraw-Hill Education."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/314\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:38:46Z","timestamp":1760179126000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,28]]},"references-count":23,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["a13120314"],"URL":"https:\/\/doi.org\/10.3390\/a13120314","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,11,28]]}}}