{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:30Z","timestamp":1750307610864,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>\n            Given a set of leaf-labeled trees with identical leaf sets, the well-known Maximum Agreement SubTree (MAST) problem consists in finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its variant called Maximum Compatible Tree (MCT) are of particular interest in computational biology. This article presents a linear-time approximation algorithm to solve the complement version of MAST, namely identifying the smallest set of leaves to remove from input trees to obtain isomorphic trees. We also present an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            +\n            <jats:italic>kn<\/jats:italic>\n            ) algorithm to solve the complement version of MCT. For both problems, we thus achieve significantly lower running times than previously known algorithms. Fast running times are especially important in phylogenetics where large collections of trees are routinely produced by resampling procedures, such as the nonparametric bootstrap or Bayesian MCMC methods.\n          <\/jats:p>","DOI":"10.1145\/1497290.1497299","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:22Z","timestamp":1239035662000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Linear time 3-approximation for the MAST problem"],"prefix":"10.1145","volume":"5","author":[{"given":"Vincent","family":"Berry","sequence":"first","affiliation":[{"name":"Universit\u00e9 Montpellier II, France"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Montpellier II, France"}]},{"given":"Sylvain","family":"Guillemot","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Montpellier II, France"}]},{"given":"Fran\u00e7ois","family":"Nicolas","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Montpellier II, France"}]}],"member":"320","published-online":{"date-parts":[[2009,3,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794269461"},{"key":"e_1_2_1_2_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 4th Workshop on Algorithms in Bioinformatics (WABI)","author":"Berger-Wolf T.","unstructured":"Berger-Wolf , T. 2004. Consensus and agreement of phylogenetic trees . In Proceedings of the 4th Workshop on Algorithms in Bioinformatics (WABI) . Lecture Notes in Computer Science . Springer , 350--361. Berger-Wolf, T. 2004. Consensus and agreement of phylogenetic trees. In Proceedings of the 4th Workshop on Algorithms in Bioinformatics (WABI). Lecture Notes in Computer Science. Springer, 350--361."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM'04)","volume":"3109","author":"Berry V.","unstructured":"Berry , V. , and Nicolas , F . 2004. Maximum agreement and compatible supertrees . In Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM'04) , S. C. Sahinalp et al., Eds. Lecture Notes in Computer Science , vol. 3109 . Springer, 205--219. Berry, V., and Nicolas, F. 2004. Maximum agreement and compatible supertrees. In Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM'04), S. C. Sahinalp et al., Eds. Lecture Notes in Computer Science, vol. 3109. Springer, 205--219."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.39"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Bryant D. Steel M. and MacKenzie A. 1983. The size of a maximum agreement subtree for random binary trees. In BioConsensus M. Janowitz et al. Eds. DIMACS AMS 55--66.  Bryant D. Steel M. and MacKenzie A. 1983. The size of a maximum agreement subtree for random binary trees. In BioConsensus M. Janowitz et al. Eds. DIMACS AMS 55--66.","DOI":"10.1090\/dimacs\/061\/04"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796313477"},{"key":"e_1_2_1_8_1","first-page":"73","article-title":"Computational tractability: The view from","volume":"69","author":"Downey R. G.","year":"1999","unstructured":"Downey , R. G. , Fellows , M. R. , and Stege , U. 1999 . Computational tractability: The view from Mars. Bull. Eur. Assoc. Theor. Comput. Sci. 69 , 73 -- 97 . Downey, R. G., Fellows, M. R., and Stege, U. 1999. Computational tractability: The view from Mars. Bull. Eur. Assoc. Theor. Comput. Sci. 69, 73--97.","journal-title":"Mars. Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00110-X"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'02)","volume":"2462","author":"Ganapathy G.","unstructured":"Ganapathy , G. , and Warnow , T. J . 2002. Approximating the complement of the maximum compatible subset of leaves of k trees . In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'02) . Lecture Notes in Computer Science , vol. 2462 . Springer, 122--134. Ganapathy, G., and Warnow, T. J. 2002. Approximating the complement of the maximum compatible subset of leaves of k trees. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'02). Lecture Notes in Computer Science, vol. 2462. Springer, 122--134."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 1st International Workshop on Algorithms in Bioinformatics (WABI'01)","volume":"2149","author":"Ganapathysaravanabavan G.","unstructured":"Ganapathysaravanabavan , G. , and Warnow , T. J . 2001. Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time . In Proceedings of the 1st International Workshop on Algorithms in Bioinformatics (WABI'01) , O. Gascuel and B. M. E. Moret, Eds. Lecture Notes in Computer Science , vol. 2149 . Springer, 156--163. Ganapathysaravanabavan, G., and Warnow, T. J. 2001. Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. In Proceedings of the 1st International Workshop on Algorithms in Bioinformatics (WABI'01), O. Gascuel and B. M. E. Moret, Eds. Lecture Notes in Computer Science, vol. 2149. Springer, 156--163."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/10635150390235520"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009212"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(96)00012-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00062-5"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 7th Annual European Symposium on Algorithms (ESA'99)","volume":"1643","author":"Kao M.-Y.","unstructured":"Kao , M.-Y. , Lam , T. W. , Sung , W.-K. , and Ting , H . -F. 1999. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees . In Proceedings of the 7th Annual European Symposium on Algorithms (ESA'99) . Lecture Notes in Computer Science , vol. 1643 . Springer, 438--449. Kao, M.-Y., Lam, T. W., Sung, W.-K., and Ting, H.-F. 1999. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In Proceedings of the 7th Annual European Symposium on Algorithms (ESA'99). Lecture Notes in Computer Science, vol. 1643. Springer, 438--449."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1163"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"McMorris F. Meronik D. and Neumann D. 1983. A view of some consensus methods for trees. In Numerical Taxonomy J. Felsenstein Ed. Springer 122--125.  McMorris F. Meronik D. and Neumann D. 1983. A view of some consensus methods for trees. In Numerical Taxonomy J. Felsenstein Ed. Springer 122--125.","DOI":"10.1007\/978-3-642-69024-2_18"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28639-4_11"},{"key":"e_1_2_1_21_1","unstructured":"Semple C. and Steel M. 2003. Phylogenetics. Oxford Lecture Series in Mathematics and its Applications vol. 24. Oxford University Press.  Semple C. and Steel M. 2003. Phylogenetics. Oxford Lecture Series in Mathematics and its Applications vol. 24. Oxford University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90181-8"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497299","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1497290.1497299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:40Z","timestamp":1750250740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1497290.1497299"],"URL":"https:\/\/doi.org\/10.1145\/1497290.1497299","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2006-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}