Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Constructing the Simplest Possible Phylogenetic Network from Triplets

Constructing the Simplest Possible Phylogenetic Network from Triplets 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Algorithmica Springer Journals

Constructing the Simplest Possible Phylogenetic Network from Triplets

Algorithmica , Volume 60 (2) – Jul 7, 2009

Loading next page...
 
/lp/springer-journals/constructing-the-simplest-possible-phylogenetic-network-from-triplets-zDPcPzGQ7g

References (35)

Publisher
Springer Journals
Copyright
Copyright © 2009 by The Author(s)
Subject
Computer Science; Data Structures, Cryptology and Information Theory; Computer Systems Organization and Communication Networks; Algorithm Analysis and Problem Complexity; Mathematics of Computing; Theory of Computation; Algorithms
ISSN
0178-4617
eISSN
1432-0541
DOI
10.1007/s00453-009-9333-0
Publisher site
See Article on Publisher Site

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.

Journal

AlgorithmicaSpringer Journals

Published: Jul 7, 2009

There are no references for this article.