{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:31:29Z","timestamp":1760243489867,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T00:00:00Z","timestamp":1373500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Rooted triplets are becoming one of the most important types of input for reconstructing rooted phylogenies. A rooted triplet is a phylogenetic tree on three leaves and shows the evolutionary relationship of the corresponding three species. In this paper, we investigate the problem of inferring the maximum consensus evolutionary tree from a set of rooted triplets. This problem is known to be APX-hard. We present two new heuristic algorithms. For a given set of m triplets on n species, the FastTree algorithm runs in O(m + \u03b1(n)n2) time, where \u03b1(n) is the functional inverse of Ackermann\u2019s function. This is faster than any other previously known algorithms, although the outcome is less satisfactory. The Best Pair Merge with Total Reconstruction (BPMTR) algorithm runs in O(mn3) time and, on average, performs better than any other previously known algorithms for this problem.<\/jats:p>","DOI":"10.3390\/a6030396","type":"journal-article","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T11:50:38Z","timestamp":1373543438000},"page":"396-406","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["New Heuristics for Rooted Triplet Consistency"],"prefix":"10.3390","volume":"6","author":[{"suffix":"Tazehkand","given":"Soheil","family":"Jahangiri","sequence":"first","affiliation":[{"name":"Amirkabir University of Technology (Tehran Polytechnic), 424 Hafez Ave, Tehran, Iran"},{"name":"Bioinformatics Group, School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Niavaran, Tehran, Iran"}]},{"given":"Seyed","family":"Hashemi","sequence":"additional","affiliation":[{"name":"Amirkabir University of Technology (Tehran Polytechnic), 424 Hafez Ave, Tehran, Iran"}]},{"given":"Hadi","family":"Poormohammadi","sequence":"additional","affiliation":[{"name":"Shahid Beheshti University, Evin, Tehran 19839-63113, Iran"}]}],"member":"1968","published-online":{"date-parts":[[2013,7,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1126\/science.1219669","article-title":"Mapping the origins and expansion of the Indo-European language family","volume":"337","author":"Bouckaert","year":"2012","journal-title":"Science"},{"key":"ref_2","unstructured":"Felsenstein, J. (2004). Inferring Phylogenies, Sinauer Associates."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gascuel, O., and Moret, B. (2001). Algorithms in Bioinformatics, Springer. Lecture Notes in Computer Science, Volume 2149, pp. 204\u2013213.","DOI":"10.1007\/3-540-44696-6"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/jagm.1996.0035","article-title":"Determining the evolutionary tree using experiments","volume":"21","author":"Kannan","year":"1996","journal-title":"J. Algorithms"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.jda.2009.01.004","article-title":"Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks","volume":"8","author":"Byrka","year":"2010","journal-title":"J. Discret. Algorithms"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/S1571-0653(04)00222-7","article-title":"On the complexity of inferring rooted evolutionary trees","volume":"7","author":"Jansson","year":"2001","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","article-title":"Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions","volume":"10","author":"Aho","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009268","article-title":"Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology","volume":"24","author":"Henzinger","year":"1999","journal-title":"Algorithmica"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00453-004-1147-5","article-title":"Rooted Maximum Agreement Supertrees","volume":"43","author":"Jansson","year":"2005","journal-title":"Algorithmica"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/502090.502095","article-title":"Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity","volume":"48","author":"Holm","year":"2001","journal-title":"J. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1023\/B:JOCO.0000021936.04215.68","article-title":"Constructing the maximum consensus tree from rooted triples","volume":"8","author":"Wu","year":"2004","journal-title":"J. Comb. Optim."},{"key":"ref_12","unstructured":"Bryant, D. (1997). Building Trees, Hunting for Trees, and Comparing Trees\u2014Theory and Methods in Phylogenetic Analysis. [PhD thesis, University of Canterbury]."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Hong, S.H., Nagamochi, H., and Fukunaga, T. (2008). Algorithms and Computation, Springer. Lecture Notes in Computer Science, Volume 5369, pp. 484\u2013495.","DOI":"10.1007\/978-3-540-92182-0"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1142\/S0219720009004308","article-title":"Uniqueness, intractability and exact algorithms: Reflections on level-k phylogenetic networks","volume":"7","author":"Kelk","year":"2009","journal-title":"J. Bioinform. Comput. Biol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1023\/A:1009833626004","article-title":"On the complexity of constructing evolutionary trees","volume":"3","author":"Gasieniec","year":"1999","journal-title":"J. Comb. Optim."},{"key":"ref_16","unstructured":"Maemura, K., Jansson, J., Ono, H., Sadakane, K., and Yamashita, M. (2007, January 9\u201310). Approximation Algorithms for Constructing Evolutionary Trees from Rooted Triplets. Proceedings of 10th Korea-Japan Joint Workshop on Algorithms and Computation, Gwangju, Korea."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2006.06.022","article-title":"Inferring a level-1 phylogenetic network from a dense set of rooted triplets","volume":"363","author":"Jansson","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","unstructured":"Cormen, T.T., Leiserson, C.E., and Rivest, R.L. (1990). Introduction to Algorithms, MIT Press."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Vingron, M., and Wong, L. (2008). Research in Computational Molecular Biology, Springer. Lecture Notes in Computer Science, Volume 4955, pp. 450\u2013462.","DOI":"10.1007\/978-3-540-78839-3"},{"key":"ref_20","unstructured":"Kelk, S. (2008). LEVEL2: A fast algorithm for constructing level-2 phylogenetic networks from dense sets of rooted triplets."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Gonnet, G., and Viola, A. (2000). LATIN 2000: Theoretical Informatics, Springer. Lecture Notes in Computer Science, Volume 1776, pp. 88\u201394.","DOI":"10.1007\/10719839"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/396\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:47:52Z","timestamp":1760219272000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/3\/396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,11]]},"references-count":21,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2013,9]]}},"alternative-id":["a6030396"],"URL":"https:\/\/doi.org\/10.3390\/a6030396","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,7,11]]}}}