{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T09:16:13Z","timestamp":1761988573659,"version":"build-2065373602"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Distance methods are well suited for constructing massive phylogenetic trees. However, the computational complexity for Rzhetsky and Nei\u2019s minimum evolution (ME) approach, one of the earliest methods for constructing a phylogenetic tree from a distance matrix, remains open.<\/jats:p><jats:p>Results: We show that Rzhetsky and Nei\u2019s ME problem is NP-complete, and so probably computationally intractable. We do this by linking the ME problem to a graph clustering problem called the quasi-clique decomposition problem, which has recently also been shown to be NP-complete. We also discuss how this link could potentially open up some useful new connections between phylogenetics and graph clustering.<\/jats:p><jats:p>Contact: \u00a0taoyang.wu@uea.ac.uk<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv623","type":"journal-article","created":{"date-parts":[[2015,10,25]],"date-time":"2015-10-25T07:00:56Z","timestamp":1445756456000},"page":"518-522","source":"Crossref","is-referenced-by-count":4,"title":["The minimum evolution problem is hard: a link between tree inference and graph clustering problems"],"prefix":"10.1093","volume":"32","author":[{"given":"Sarah","family":"Bastkowski","sequence":"first","affiliation":[{"name":"1 The Genome Analysis Centre, Norwich, UK,"}]},{"given":"Vincent","family":"Moulton","sequence":"additional","affiliation":[{"name":"2 School of Computing Sciences, University of East Anglia, Norwich, UK and"}]},{"given":"Andreas","family":"Spillner","sequence":"additional","affiliation":[{"name":"3 Department of Mathematics and Computer Science, University of Greifswald, Greifswald, Germany"}]},{"given":"Taoyang","family":"Wu","sequence":"additional","affiliation":[{"name":"2 School of Computing Sciences, University of East Anglia, Norwich, UK and"}]}],"member":"286","published-online":{"date-parts":[[2015,10,24]]},"reference":[{"key":"2023020110313409700_btv623-B1","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1142\/S0219720004000557","article-title":"Ancestral maximum likelihood of evolutionary trees is hard","volume":"2","author":"Addario-Berry","year":"2004","journal-title":"J. Bioinfo. Comput. Biol."},{"key":"2023020110313409700_btv623-B2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","article-title":"Correlation clustering","volume":"56","author":"Bansal","year":"2004","journal-title":"Mach. Learn."},{"key":"2023020110313409700_btv623-B3","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/s00453-009-9339-7","article-title":"Exact algorithms for cluster editing: evaluation and experiments","volume":"60","author":"B\u00f6cker","year":"2011","journal-title":"Algorithmica"},{"key":"2023020110313409700_btv623-B4","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-540-92695-5_4","article-title":"On effectively finding maximal quasi-cliques in graphs","volume":"5313","author":"Brunato","year":"2008","journal-title":"Lect. Notes Comput. Sci."},{"key":"2023020110313409700_btv623-B5","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1002\/net.20280","article-title":"The minimum evolution problem: overview and classification","volume":"53","author":"Catanzaro","year":"2009","journal-title":"Networks"},{"key":"2023020110313409700_btv623-B6","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/S0092-8240(87)80007-1","article-title":"Computational complexity of inferring phylogenies from dissimilarity matrices","volume":"49","author":"Day","year":"1987","journal-title":"Bull. Math. Biol."},{"key":"2023020110313409700_btv623-B7","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1089\/106652702761034136","article-title":"Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle","volume":"19","author":"Desper","year":"2002","journal-title":"J. Comput. Biol."},{"key":"2023020110313409700_btv623-B8","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1093\/molbev\/msh049","article-title":"Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least-squares tree fittings","volume":"21","author":"Desper","year":"2004","journal-title":"Mol. Biol. Evol."},{"key":"2023020110313409700_btv623-B9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/oso\/9780198566106.003.0001","article-title":"The minimum-evolution distance-based approach to phylogenetic inference","volume-title":"Mathematics of Evolution and Phylogeney","author":"Desper","year":"2005"},{"key":"2023020110313409700_btv623-B10","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF01188585","article-title":"A robust model for finding optimal evolutionary trees","volume":"13","author":"Farach","year":"1995","journal-title":"Algorithmica"},{"key":"2023020110313409700_btv623-B11","doi-asserted-by":"crossref","first-page":"S13","DOI":"10.1186\/1471-2164-16-S1-S13","article-title":"Phylogenetic placement of metagenomic reads using the minimum evolution principle","volume":"16","author":"Filipski","year":"2015","journal-title":"BMC Genomics"},{"key":"2023020110313409700_btv623-B12","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.orl.2011.10.003","article-title":"Approximating the balanced minimum evolution problem","volume":"40","author":"Fiorini","year":"2012","journal-title":"Oper. Res. Lett."},{"key":"2023020110313409700_btv623-B13","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1007\/s00453-011-9487-4","article-title":"Editing graphs into disjoint unions of dense clusters","volume":"61","author":"Guo","year":"2011","journal-title":"Algorithmica"},{"key":"2023020110313409700_btv623-B14","article-title":"On the minimum edge cover and vertex partition by quasi-cliques problems","author":"Kaya","year":"2013","journal-title":"HAL Res. Rep."},{"key":"2023020110313409700_btv623-B15","first-page":"235","article-title":"Phylogenetic analysis: concepts and methods","volume":"23","author":"Kidd","year":"1971","journal-title":"Am. J. Genet."},{"key":"2023020110313409700_btv623-B16","doi-asserted-by":"crossref","first-page":"1481","DOI":"10.1089\/cmb.2011.0156","article-title":"Pedigree reconstruction using identity by descent","volume":"18","author":"Kirkpatrick","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023020110313409700_btv623-B17","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/j.dam.2012.07.019","article-title":"On the maximum quasi-clique problem","volume":"161","author":"Pattillo","year":"2013","journal-title":"Disc. Appl. Math."},{"key":"2023020110313409700_btv623-B18","first-page":"1073","article-title":"Theoretical foundation of the minimum-evolution method of phylogenetic inference","volume":"10","author":"Rzhetsky","year":"1993","journal-title":"Mol. Biol. Evol."},{"key":"2023020110313409700_btv623-B19","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetictrees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol."},{"key":"2023020110313409700_btv623-B20","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Survey: graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comput. Sci. Rev."},{"volume-title":"Theory of Linear and Integer Programming","year":"1986","author":"Schrijver","key":"2023020110313409700_btv623-B21"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/4\/518\/49017422\/bioinformatics_32_4_518.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/4\/518\/49017422\/bioinformatics_32_4_518.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T00:22:03Z","timestamp":1718151723000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/4\/518\/1744318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,24]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv623","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2016,2,15]]},"published":{"date-parts":[[2015,10,24]]}}}