Access the full text.
Sign up today, get an introductory month for just $19.
(2010)
Phylogenetic Networks: Frontmatter
J. Oldman, Taoyang Wu, Leo Iersel, V. Moulton (2016)
TriLoNet: Piecing Together Small Networks to Reconstruct Reticulate Evolutionary Histories.Molecular biology and evolution, 33 8
(2015)
networks from nondense binet and trinet sets. Algorithmica
J. Whitfield (2012)
Phylogenetic Networks: Concepts, Algorithms and ApplicationsSystematic Biology, 61
K. Huber, L. Iersel, V. Moulton, Céline Scornavacca, Taoyang Wu (2014)
Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet SetsAlgorithmica, 77
Johannes Köbler, U. Schöning, J. Torán (1993)
The Graph Isomorphism Problem
K. Huber, Leo Iersel, V. Moulton, Taoyang Wu (2014)
How Much Information is Needed to Infer Reticulate Evolutionary Histories?Systematic Biology, 64
B. Holland, K. Huber, V. Moulton, P. Lockhart (2004)
Using consensus networks to visualize contradictory evidence for species phylogeny.Molecular biology and evolution, 21 7
D. Gusfield (2014)
ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks
Pierre Charbit, Stéphan Thomassé, Anders Yeo (2006)
The Minimum Feedback Arc Set Problem is NP-Hard for TournamentsCombinatorics, Probability and Computing, 16
(2011)
An introduction to phylogenetic networks
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
N. Alon (2006)
Ranking TournamentsSIAM J. Discret. Math., 20
M Goldberg (2003)
Handbook of graph theory
R. Tarjan (1972)
Depth-First Search and Linear Graph AlgorithmsSIAM J. Comput., 1
(2004)
Inferring phylogenies
J. Byrka, Sylvain Guillemot, J. Jansson (2008)
New Results on Optimizing Rooted Triplets ConsistencyDiscret. Appl. Math., 158
E. Bapteste, Leo Iersel, A. Janke, S. Kelchner, S. Kelk, J. McInerney, D. Morrison, Luay Nakhleh, M. Steel, L. Stougie, Jim Whitfield (2013)
Networks: expanding evolutionary thinking.Trends in genetics : TIG, 29 8
D. Bryant (2001)
A classification of consensus methods for phylogenetics
Phylogenetic networks are a generalization of evolutionary trees that are used by biologists to represent the evolution of organisms which have undergone reticulate evolution. Essentially, a phylogenetic network is a directed acyclic graph having a unique root in which the leaves are labelled by a given set of species. Recently, some approaches have been developed to construct phylogenetic networks from collections of networks on 2- and 3-leaved networks, which are known as binets and trinets, respectively. Here we study in more depth properties of collections of binets, one of the simplest possible types of networks into which a phylogenetic network can be decomposed. More specifically, we show that if a collection of level-1 binets is compatible with some binary network, then it is also compatible with a binary level-1 network. Our proofs are based on useful structural results concerning lowest stable ancestors in networks. In addition, we show that, although the binets do not determine the topology of the network, they do determine the number of reticulations in the network, which is one of its most important parameters. We also consider algorithmic questions concerning binets. We show that deciding whether an arbitrary set of binets is compatible with some network is at least as hard as the well-known graph isomorphism problem. However, if we restrict to level-1 binets, it is possible to decide in polynomial time whether there exists a binary network that displays all the binets. We also show that to find a network that displays a maximum number of the binets is NP-hard, but that there exists a simple polynomial-time 1/3-approximation algorithm for this problem. It is hoped that these results will eventually assist in the development of new methods for constructing phylogenetic networks from collections of smaller networks.
Bulletin of Mathematical Biology – Springer Journals
Published: Apr 6, 2017
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 an introductory month for just $19.
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.