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.
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.
| Original language | English |
|---|---|
| Pages (from-to) | 518-522 |
| Number of pages | 5 |
| Journal | Bioinformatics |
| Volume | 32 |
| Issue number | 4 |
| Early online date | 24 Oct 2015 |
| DOIs | |
| Publication status | Published - 15 Feb 2016 |
Profiles
-
Vincent Moulton
- School of Computing Sciences - Professor in Computational Biology
- Norwich Epidemiology Centre - Member
- Computational Biology - Member
Person: Research Group Member, Academic, Teaching & Research
-
Taoyang Wu
- School of Computing Sciences - Lecturer in Computing Sciences
- Computational Biology - Member
Person: Research Group Member, Academic, Teaching & Research