Access the full text.
Sign up today, get DeepDyve free for 14 days.
L. Iersel, J. Keijsper, S. Kelk, L. Stougie, F. Hagen, T. Boekhout (2007)
Constructing Level-2 Phylogenetic Networks from TripletsIEEE/ACM Transactions on Computational Biology and Bioinformatics, 6
(2004)
Modeling, Reconstructibility, and Accuracy, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1 (1), pp
Yun Song, Y. Wu, D. Gusfield (2005)
Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolutionBioinformatics, 21 Suppl 1
J. Jansson, W. Sung (2005)
Algorithms for combining rooted triplets into a galled phylogenetic network
M. Henzinger, Valerie King, T. Warnow (1996)
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary BiologyAlgorithmica, 24
Lusheng Wang, Kaizhong Zhang, Louxin Zhang (2001)
Perfect phylogenetic networks with recombinationJournal of computational biology : a journal of computational molecular cell biology, 8 1
Leo Iersel, J. Keijsper, S. Kelk, L. Stougie, Ferry Hagen, Teun Boekhout
Constructing Level-2 Phylogenetic Networks from Triplets
Trinh Huynh, J. Jansson, N. Nguyen, W. Sung (2005)
Constructing a Smallest Refining Galled Phylogenetic Network
J. Hein (1990)
Reconstructing evolution of sequences subject to recombination using parsimony.Mathematical biosciences, 98 2
J. Jansson, W. Sung (2004)
Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted TripletsTheor. Comput. Sci., 363
J. Byrka, Paweł Gawrychowski, K. Huber, S. Kelk (2007)
Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networksJ. Discrete Algorithms, 8
(2006)
Phylogenetic network reconstruction approaches MARLON: constructing level one phylogenetic networks with a minimum amount of reticulation
L. Iersel, S. Kelk, Matthias Mnich (2007)
Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic NetworksJournal of bioinformatics and computational biology, 7 4
M. Bordewich, S. Linz, Katherine John, C. Semple (2007)
A Reduction Algorithm for Computing The Hybridization Number of Two TreesEvolutionary Bioinformatics Online, 3
Bernard Moret, Luay Nakhleh, T. Warnow, C. Linder, Anna Tholse, Anneke Padolina, Jerry Sun, R. Timme (2004)
Phylogenetic networks: modeling, reconstructibility, and accuracyIEEE/ACM Transactions on Computational Biology and Bioinformatics, 1
M. Baroni, S. Grünewald, V. Moulton, C. Semple (2005)
Bounding the Number of Hybridisation Events for a Consistent Evolutionary HistoryJournal of Mathematical Biology, 51
V. Makarenkov, D. Kevorkov, P. Legendre (2006)
Applied Mycology and Biotechnology
Ying-Jun He, Trinh Huynh, J. Jansson, W. Sung (2006)
Inferring phylogenetic relationships avoiding forbidden rooted tripletsJournal of bioinformatics and computational biology, 4 1
Luay Nakhleh, T. Warnow (2004)
Phylogenetic networks
Yun Song, J. Hein (2004)
On the minimum number of recombination events in the evolutionary history of DNA sequencesJournal of Mathematical Biology, 48
M. Baroni, C. Semple, M. Steel (2005)
A Framework for Representing Reticulate EvolutionAnnals of Combinatorics, 8
M. Bordewich, C. Semple (2007)
Computing the minimum number of hybridization events for a consistent evolutionary historyDiscret. Appl. Math., 155
(2006)
Phylogenetic Network Reconstruction Approaches, in Applied Mycology and Biotechnology, International Elsevier Series 6, Bioinformatics, pp
D. Huson, D. Bryant (2006)
Application of phylogenetic networks in evolutionary studies.Molecular biology and evolution, 23 2
V. Makarenkov, D. Kevorkov, P. Legendre (2006)
Phylogenetic Network Construction ApproachesApplied Mycology and Biotechnology, 6
A. Rambaut, N. Grassly (1997)
Seq-Gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic treesComputer applications in the biosciences : CABIOS, 13 3
A. Aho, Y. Sagiv, T. Szymanski, J. Ullman (1981)
Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational ExpressionsSIAM J. Comput., 10
(2005)
New Tools for Population Biology, International Journal for Parasitology, 35 (5), pp
C. Choy, J. Jansson, K. Sadakane, W. Sung (2004)
Computing the Maximum Agreement of Phylogenetic Networks
D. Morrison (2005)
Networks in phylogenetic analysis: new tools for population biology.International journal for parasitology, 35 5
L. Iersel, J. Keijsper, S. Kelk, L. Stougie, F. Hagen, T. Boekhout (2008)
Constructing level-2 phylogenetic networks from rooted triplets
(2007)
Theory and Empirical Study, Discrete Applied Mathematics, 155 (6-7), pp
D. Gusfield, Satish Eddhu, C. Langley (2004)
Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained RecombinationJournal of bioinformatics and computational biology, 2 1
D. Gusfield, Dean Hickerson, Satish Eddhu (2007)
An efficiently computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical studyDiscret. Appl. Math., 155
Stéphane Guindon, O. Gascuel (2003)
A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood.Systematic biology, 52 5
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.
Algorithmica – Springer Journals
Published: Jul 7, 2009
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.