2008 | OriginalPaper | Chapter
Constructing the Simplest Possible Phylogenetic Network from Triplets
Authors : Leo van Iersel, Steven Kelk
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A phylogenetic network is a directed acyclic graph that visualises an evolutionary history containing so-called
reticulations
such as recombinations, hybridisations 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, which minimises both the level and the total number of reticulations, in time
O
(|
T
|
k
+ 1
), if
k
is a fixed upper bound on the level.