Who is Who in Phylogenetic Networks

Publications of Radoslaw Suchecki     Order by:   Type | Year

Associated keywords

duplication explicit-network exponential-algorithm from-triplets galled-tree generation heuristic phylogenetic-network phylogeny Program-LEV1ATHAN Program-Lev1Generator reconstruction software

2012

1 Katharina Huber, Vincent Moulton, Andreas Spillner, Sabine Storandt and Radoslaw Suchecki. Computing a consensus of multilabeled trees. In ALENEX12, Pages 84-92, 2012. Keywords: duplication, explicit network, exponential algorithm, phylogenetic network, phylogeny. Note: http://siam.omnibooksonline.com/2012ALENEX/data/papers/020.pdf.         Toggle abstract In this paper we consider two challenging problems that arise in the context of computing a consensus of a collection of multilabeled trees, namely (1) selecting a compatible collection of clusters on a multiset from an ordered list of such clusters and (2) optimally refining high degree vertices in a multilabeled tree. Forming such a consensus is part of an approach to reconstruct the evolutionary history of a set of species for which events such as genome duplication and hybridization have occurred in the past. We present exact algorithms for solving (1) and (2) that have an exponential run-time in the worst case. To give some impression of their performance in practice, we apply them to simulated input and to a real biological data set highlighting the impact of several structural properties of the input on the performance.

2011

2 Katharina Huber, Leo van Iersel, Steven Kelk and Radoslaw Suchecki. A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks. In TCBB, Vol. 8(3):607-620, 2011. Keywords: explicit network, from triplets, galled tree, generation, heuristic, phylogenetic network, phylogeny, Program LEV1ATHAN, Program Lev1Generator, reconstruction, software. Note: http://arxiv.org/abs/0910.4067.         Toggle abstract "Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks-a type of network slightly more general than a phylogenetic tree-from triplets. Our algorithm has been made publicly available as the program Lev1athan. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, Lev1athan runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level-1 network, it will find such a network. The potential of Lev1athan is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that Lev1athan is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise. © 2011 IEEE."