The minimum evolution problem is hard: a link between tree inference and graph clustering problems.
BACKGROUND
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.
The Genome Analysis Centre, Norwich, UK.
Sarah
S
Bastkowski
School of Computing Sciences, University of East Anglia, Norwich, UK and.
Vincent
V
Moulton
Department of Mathematics and Computer Science, University of Greifswald, Greifswald, Germany.
Andreas
A
Spillner
School of Computing Sciences, University of East Anglia, Norwich, UK and.
Taoyang
T
Wu
D000465:Algorithms; D005075:Biological Evolution; D016000:Cluster Analysis; D003198:Computer Simulation; D006801:Humans; D008962:Models, Theoretical; D010802:Phylogeny; D012984:Software