The minimum evolution problem is hard:A link between tree inference and graph clustering problems

Bastkowski, Sarah, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435, Spillner, Andreas and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2016) The minimum evolution problem is hard:A link between tree inference and graph clustering problems. Bioinformatics, 32 (4). pp. 518-522. ISSN 1367-4803

[thumbnail of ME_Bioinformatics_main_rev]
Preview
PDF (ME_Bioinformatics_main_rev) - Accepted Version
Download (109kB) | Preview

Abstract

Motivation: Distance methods are well suited for constructing massive phylogenetic trees. However, the computational complexity for Rzhetsky and Nei’s minimum evolution (ME) approach, one of the earliest methods for constructing a phylogenetic tree from a distance matrix, remains open. Results: We show that Rzhetsky and Nei’s 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.

Item Type: Article
Faculty \ School: Faculty of Science
Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Computational Biology
Faculty of Science > Research Groups > Norwich Epidemiology Centre
Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User: Pure Connector
Date Deposited: 03 Nov 2015 11:00
Last Modified: 19 Apr 2023 23:40
URI: https://ueaeprints.uea.ac.uk/id/eprint/54982
DOI: 10.1093/bioinformatics/btv623

Actions (login required)

View Item View Item