{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:03Z","timestamp":1787337603973,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>Inferring evolutionary trees has long been a challenging problem for both biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quartet topologies) and then recombining these inferred quartet topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.<\/jats:p>","DOI":"10.1137\/s0097539799361683","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1942-1961","source":"Crossref","is-referenced-by-count":86,"title":["A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application"],"prefix":"10.1137","volume":"30","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Kearney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Alan Frieze, Haim Kaplan, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 21\u2013301450599","DOI":"10.1109\/SFCS.1996.548460"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy,\n                      Proof verification and hardness of approximation problems\n                      , in Proceedings of the 33rd IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society Press, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Ben\u2010Dor, B. Chor, D. Graur, R. Ophir, and D. Pelleg,\n                      From four\u2013taxon trees to phylogenies: The case of mammalian evolution\n                      , in Proceedings of the 2nd Annual International Conference on Computational Molecular Biology, ACM Press, 1998, pp. 9\u201319.","DOI":"10.1145\/279069.279078"},{"key":"R4","unstructured":"V. Berry,\n                      private communication\n                      , LIRM, Montpellier, France, 1998."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Vincent Berry, Olivier Gascuel, Inferring evolutionary trees with strong combinatorial evidence, Lecture Notes in Comput. Sci., Vol. 1276, Springer, Berlin, 1997, 111\u201312399f:92011","DOI":"10.1007\/BFb0045078"},{"key":"R6","unstructured":"D. Bryant,\n                      Structures in Biological Classification\n                      , Ph.D. thesis, Department of Mathematics and Statistics, University of Canterbury, Canterbury, UK, 1997."},{"key":"R7","unstructured":"P. Buneman,\n                      The recovery of trees from measures of dissimilarity\n                      , in Mathematics in the Archaeological and Historical Sciences, F. R. Hodson, D. G. Kendall, and P. Tautu, eds., Edinburgh University Press, Edinburgh, 1971, pp. 387\u2013395."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"P\u00e9ter Erd\u00f6s, Michael Steel, L\u00e1szl\u00f3 Sz\u00e9kely, Tandy Warnow, Constructing big trees from short sequences, Lecture Notes in Comput. Sci., Vol. 1256, Springer, Berlin, 1997, 827\u20138371616238","DOI":"10.1007\/3-540-63165-8_235"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01734359"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1086\/412935"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"P. E. Kearney,\n                      The ordinal quartet method\n                      , in Proceedings of the 2nd Annual International Conference on Computational Molecular Biology, ACM Press, 1998, pp. 125\u2013134.","DOI":"10.1145\/279069.279105"},{"key":"R12","first-page":"406","volume":"4","author":"Saitou N.","year":"1987","journal-title":"Molecular Biology and Evolution"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a025664"},{"key":"R15","unstructured":"D. L. Swofford, G. J. Olsen, P. J. Waddell, and D. M. Hillis,\n                      Phylogenetic inference\n                      , in Molecular Systematics, 2nd ed., D. M. Hillis, C. Moritz, and B. K. Mable, eds., Sinauer Associates, Sunderland, MA, 1996, pp. 407\u2013514."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1126\/science.1590849"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1126\/science.1840702"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799361683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:15Z","timestamp":1787336415000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799361683"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539799361683"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799361683","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}