Trinets encode orchard phylogenetic networks
- 21 August 2021
- journal article
- research article
- Published by Springer Nature in Journal of Mathematical Biology
- Vol. 83 (3) , 1-20
Abstract
Rooted triples, rooted binary phylogenetic trees on three leaves, are sufficient to encode rooted binary phylogenetic trees. That is, if \({{\mathcal {T}}}\) and \({{\mathcal {T}}}'\) are rooted binary phylogenetic X-trees that infer the same set of rooted triples, then \({{\mathcal {T}}}\) and \({{\mathcal {T}}}'\) are isomorphic. However, in general, this sufficiency does not extend to rooted binary phylogenetic networks. In this paper, we show that trinets, phylogenetic network analogues of rooted triples, are sufficient to encode rooted binary orchard networks. Rooted binary orchard networks naturally generalise rooted binary tree-child networks. Moreover, we present a polynomial-time algorithm for building a rooted binary orchard network from its set of trinets. As a consequence, this algorithm affirmatively answers a previously-posed question of whether there is a polynomial-time algorithm for building a rooted binary tree-child network from the set of trinets it infers.
Keywords
All Related Versions
Funding Information
- Marsden Fund
This publication has 18 references indexed in Scilit:
- Counting Phylogenetic NetworksAnnals of Combinatorics, 2015
- How Much Information is Needed to Infer Reticulate Evolutionary Histories?Systematic Biology, 2014
- Encoding and Constructing 1-Nested Phylogenetic Networks with TrinetsAlgorithmica, 2012
- On encodings of phylogenetic networks of bounded levelJournal of Mathematical Biology, 2011
- Properties of Normal Phylogenetic NetworksBulletin of Mathematical Biology, 2009
- Constructing the Simplest Possible Phylogenetic Network from TripletsAlgorithmica, 2009
- Inferring a level-1 phylogenetic network from a dense set of rooted tripletsTheoretical Computer Science, 2006
- Algorithms for Combining Rooted Triplets into a Galled Phylogenetic NetworkSIAM Journal on Computing, 2006
- The evolution of supertreesTrends in Ecology & Evolution, 2004
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational ExpressionsSIAM Journal on Computing, 1981