{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:08:46Z","timestamp":1773274126708,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T00:00:00Z","timestamp":1466121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The Hakubi Project at Kyoto University and KAKENHI","award":["26330014"],"award-info":[{"award-number":["26330014"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>\n            A\n            <jats:italic>consensus tree<\/jats:italic>\n            is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most well-known and widely used ones are\n            <jats:italic>the majority rule consensus tree<\/jats:italic>\n            ,\n            <jats:italic>the loose consensus tree<\/jats:italic>\n            , and\n            <jats:italic>the greedy consensus tree<\/jats:italic>\n            . This article presents new deterministic algorithms for constructing them that are faster than all the previously known ones. Given\n            <jats:italic>k<\/jats:italic>\n            phylogenetic trees with\n            <jats:italic>n<\/jats:italic>\n            leaves each and with identical leaf label sets, our algorithms run in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nk<\/jats:italic>\n            ) time (majority rule consensus tree),\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nk<\/jats:italic>\n            ) time (loose consensus tree), and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            ) time (greedy consensus tree). Our algorithms for the majority rule consensus and the loose consensus trees are optimal since the input size is \u03a9(\n            <jats:italic>nk<\/jats:italic>\n            ). Experimental results show that the algorithms are fast in practice.\n          <\/jats:p>","DOI":"10.1145\/2925985","type":"journal-article","created":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T19:43:40Z","timestamp":1466192620000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Improved Algorithms for Constructing Consensus Trees"],"prefix":"10.1145","volume":"63","author":[{"given":"Jesper","family":"Jansson","sequence":"first","affiliation":[{"name":"Kyoto University, Kyoto, Japan"}]},{"given":"Chuanqi","family":"Shen","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[{"name":"National University of Singapore, Genome, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2016,6,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2412432"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39763-2_17"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.08.027"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 4th&thinsp; Latin American Symposium on Theoretical Informatics (LATIN","volume":"1776","author":"Bender M. A.","year":"2000","unstructured":"M. A. Bender and M. Farach-Colton . 2000. The LCA problem revisited . In Proceedings of the 4th&thinsp; Latin American Symposium on Theoretical Informatics (LATIN 2000 ). Lecture Notes in Computer Science , Vol. 1776 . Springer-Verlag, Berlin, 88--94. M. A. Bender and M. Farach-Colton. 2000. The LCA problem revisited. In Proceedings of the 4th&thinsp; Latin American Symposium on Theoretical Informatics (LATIN 2000). Lecture Notes in Computer Science, Vol. 1776. Springer-Verlag, Berlin, 88--94."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"R. S. Boyer and J. S. Moore. 1991. MJRTY -- a fast majority vote algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe R. S. Boyer (Ed.). Kluwer Academic Publishers Amsterdam 105--117.  R. S. Boyer and J. S. Moore. 1991. MJRTY -- a fast majority vote algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe R. S. Boyer (Ed.). Kluwer Academic Publishers Amsterdam 105--117.","DOI":"10.1007\/978-94-011-3488-0_5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1096-0031.1990.tb00551.x"},{"key":"e_1_2_1_7_1","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume":"61","author":"Bryant D.","year":"2003","unstructured":"D. Bryant . 2003 . A classification of consensus methods for phylogenetics. In Bioconsensus, M. F. Janowitz, F.-J. Lapointe, F. R. McMorris, B. Mirkin, and F. S. Roberts (Eds.) . DIMACS Series in Discrete Mathematics and Theoretical Computer Science , Vol. 61 . American Mathematical Society, Washington, DC, 163--184. D. Bryant. 2003. A classification of consensus methods for phylogenetics. In Bioconsensus, M. F. Janowitz, F.-J. Lapointe, F. R. McMorris, B. Mirkin, and F. S. Roberts (Eds.). DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 61. American Mathematical Society, Washington, DC, 163--184."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/10635150701416682"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2012.0008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908061"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syp008"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2010.08.002"},{"key":"e_1_2_1_13_1","unstructured":"J. Felsenstein. 2004. Inferring Phylogenies. Sinauer Associates Inc. Sunderland MA.  J. Felsenstein. 2004. Inferring Phylogenies. Sinauer Associates Inc. Sunderland MA."},{"key":"e_1_2_1_14_1","volume-title":"Department of Genome Sciences","author":"Felsenstein J.","year":"2005","unstructured":"J. Felsenstein . 2005. PHYLIP , version 3.6. Software package , Department of Genome Sciences , University of Washington , Seattle, U.S.A. ( 2005 ). J. Felsenstein. 2005. PHYLIP, version 3.6. Software package, Department of Genome Sciences, University of Washington, Seattle, U.S.A. (2005)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1096-0031.2003.tb00376.x"},{"key":"e_1_2_1_16_1","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"Gusfield D.","unstructured":"D. Gusfield . 1997. Algorithms on Strings, Trees, and Sequences . Cambridge University Press , New York . D. Gusfield. 1997. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, New York."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/10635150802422308"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 14th&thinsp; Workshop on Algorithm Engineering and Experiments (ALENEX","author":"Huber K. T.","year":"2012","unstructured":"K. T. Huber , V. Moulton , A. Spillner , S. Storandt , and R. Suchecki . 2012. Computing a consensus of multilabeled trees . In Proceedings of the 14th&thinsp; Workshop on Algorithm Engineering and Experiments (ALENEX 2012 ). SIAM, Philadelpia, PA, 84--92. K. T. Huber, V. Moulton, A. Spillner, S. Storandt, and R. Suchecki. 2012. Computing a consensus of multilabeled trees. In Proceedings of the 14th&thinsp; Workshop on Algorithm Engineering and Experiments (ALENEX 2012). SIAM, Philadelpia, PA, 84--92."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627946"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9639-1"},{"key":"e_1_2_1_22_1","first-page":"83","article-title":"Report on sixteenth international numerical taxonomy conference","volume":"32","author":"Jensen R. J.","year":"1983","unstructured":"R. J. Jensen . 1983 . Report on sixteenth international numerical taxonomy conference . Syst. Zool. 32 , 1 (1983), 83 -- 89 . R. J. Jensen. 1983. Report on sixteenth international numerical taxonomy conference. Syst. Zool. 32, 1 (1983), 83--89.","journal-title":"Syst. Zool."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795287642"},{"key":"e_1_2_1_24_1","first-page":"459","article-title":"A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates","volume":"11","author":"Kuhner M. K.","year":"1994","unstructured":"M. K. Kuhner and J. Felsenstein . 1994 . A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates . Molec. Biol. Evol. 11 , 3 (1994), 459 -- 468 . M. K. Kuhner and J. Felsenstein. 1994. A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Molec. Biol. Evol. 11, 3 (1994), 459--468.","journal-title":"Molec. Biol. Evol."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2148-9-216"},{"key":"e_1_2_1_26_1","first-page":"239","article-title":"Consensus n-trees","volume":"43","author":"Margush T.","year":"1981","unstructured":"T. Margush and F. R. McMorris . 1981 . Consensus n-trees . Bull. Math. Biol. 43 , 2 (1981), 239 -- 244 . T. Margush and F. R. McMorris. 1981. Consensus n-trees. Bull. Math. Biol. 43, 2 (1981), 239--244.","journal-title":"Bull. Math. Biol."},{"key":"e_1_2_1_27_1","volume-title":"Numerical Taxonomy: Proceedings of the NATO Advanced Study Institute on Numerical Taxonomy, J. Felsenstein (Ed.). NATO ASI Series","volume":"1","author":"McMorris F. R.","unstructured":"F. R. McMorris , D. B. Meronk , and D. A. Neumann . 1983. A view of some consensus methods for trees . In Numerical Taxonomy: Proceedings of the NATO Advanced Study Institute on Numerical Taxonomy, J. Felsenstein (Ed.). NATO ASI Series , Vol. G 1 . Springer-Verlag, Berlin, 122--126. F. R. McMorris, D. B. Meronk, and D. A. Neumann. 1983. A view of some consensus methods for trees. In Numerical Taxonomy: Proceedings of the NATO Advanced Study Institute on Numerical Taxonomy, J. Felsenstein (Ed.). NATO ASI Series, Vol. G1. Springer-Verlag, Berlin, 122--126."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syq091"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-968X.2005.00149.x"},{"key":"e_1_2_1_30_1","volume-title":"COMPONENT, version 2.0. Software package","author":"Page R.","year":"1993","unstructured":"R. Page . 1993. COMPONENT, version 2.0. Software package , University of Glasgow , U.K. ( 1993 ). R. Page. 1993. COMPONENT, version 2.0. Software package, University of Glasgow, U.K. (1993)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg180"},{"key":"e_1_2_1_32_1","volume-title":"Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications","volume":"24","author":"Semple C.","unstructured":"C. Semple and M. Steel . 2003 . Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications , Vol. 24 . Oxford University Press, Oxford. C. Semple and M. Steel. 2003. Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications, Vol. 24. Oxford University Press, Oxford."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/2413252"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq228"},{"key":"e_1_2_1_35_1","volume-title":"Algorithms in Bioinformatics: A Practical Introduction","author":"Sung W.-K.","unstructured":"W.-K. Sung . 2010. Algorithms in Bioinformatics: A Practical Introduction . Chapman & Hall\/CRC, Boca Raton , FL. W.-K. Sung. 2010. Algorithms in Bioinformatics: A Practical Introduction. Chapman & Hall\/CRC, Boca Raton, FL."},{"key":"e_1_2_1_36_1","volume-title":"version 4.0. Software package","author":"Swofford D. L.","year":"2003","unstructured":"D. L. Swofford . 2003. PAUP&ast; , version 4.0. Software package , Sinauer Associates, Inc. , Sunderland, MA ( 2003 ). D. L. Swofford. 2003. PAUP&ast;, version 4.0. Software package, Sinauer Associates, Inc., Sunderland, MA (2003)."},{"key":"e_1_2_1_37_1","volume-title":"An efficient algorithm for computing Ml consensus trees. B.Sc. Honours thesis","author":"Wareham H. T.","year":"1985","unstructured":"H. T. Wareham . 1985. An efficient algorithm for computing Ml consensus trees. B.Sc. Honours thesis , Memorial University of Newfoundland , Canada . ( 1985 ). H. T. Wareham. 1985. An efficient algorithm for computing Ml consensus trees. B.Sc. Honours thesis, Memorial University of Newfoundland, Canada. (1985)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1018"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2925985","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2925985","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:26Z","timestamp":1750273466000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2925985"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,17]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1145\/2925985"],"URL":"https:\/\/doi.org\/10.1145\/2925985","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,17]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}