Constructing the simplest possible phylogenetic network from triplets

Journal article (2011)

Authors

L.J.J. van Iersel University of Canterbury
Steven Kelk Centrum Wiskunde & Informatica (CWI)
Affiliation
External organisation
Phylogenetic networks Phylogenetics Polynomial-time algorithm Triplets Minimising reticulations
More Info
expand_more

Published Date

2011

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

A phylogenetic network is a directed acyclic graph that visualizes an
evolutionary history containing so-called reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T , where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network with smallest possible level in time O(|T |k+1), if k is a fixed upper bound on the level of the network.