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

Sarah Bastkowski, Vincent Moulton, Andreas Spillner, Taoyang Wu (Lead Author)

Research output: Contribution to journalArticle

3 Citations (Scopus)
8 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)518-522
Number of pages5
JournalBioinformatics
Volume32
Issue number4
Early online date24 Oct 2015
DOIs
Publication statusPublished - 15 Feb 2016

Cite this