Abstract
The reconstruction of the evolutionary history of a set of species is an important problem in classification and phylogenetics. Phylogenetic networks are a generalization of evolutionary trees that are used to represent histories for species that have undergone reticulate evolution, an important evolutionary force for many organisms (e.g. plants or viruses). In this paper, we present a novel approach to understanding the structure of networks that are not necessarily binary. More specifically, we define the concept of a closed set and show that the collection of closed sets of a network forms a hierarchy, and that this hierarchy can be deduced from either the subtrees or subnetworks on all 3-subsets. This allows us to also show that closed sets generalize the concept of the SN-sets of a binary network, sets which have proven very useful in elucidating the structure of binary networks. We also characterize the minimal closed sets (under set inclusion) for a special class of networks (2-terminal networks). Taken together, we anticipate that our results should be useful for the development of new phylogenetic network reconstruction algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
CARDONA, G., LLABRES, M., ROSSELLO, F., and VALIENTE, G. (2011), “Comparison of Galled Trees,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8, 410–427.
DRESS, A., MOULTON, V., STEEL, M., and WU, T. (2010), “Species, Clusters and the ’Tree of life’: A Graph-Theoretic Perspective,” Journal of Theoretical Biology, 265, 535–542.
FISCHER, J., and HUSON, D. (2010), “New Common Ancestor Problems in Trees and Directed Acyclic Graphs,” Information Processing Letters, 110, 331–335.
GUSFIELD, D. (2014), ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks, MIT Press.
HUBER, K.T., and MOULTON, V. (2012), “Encoding and Constructing 1-Nested Phylogenetic Networks with Trinets,” Algorithmica, 616, 714–738.
HUBER, K.T., VAN IERSEL, L.,MOULTON, V., SCORNAVACCA, C., and WU, T. (2017), “Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets,” Algorithmica, 77, 173–200.
HUBER, K.T., VAN IERSEL, L., MOULTON, V., and WU, T. (2015), “How Much Information is Needed to Infer Reticulate Evolutionary Histories,” Systematic Biology, 64, 102–111.
HUBER, K.T., VAN IERSEL, L., KELK, S., and SUCHECKI, R. (2011), “A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8, 635–649.
HUSON, D.H., RUPP, R., and SCORNAVACCA, C. (2010), Phylogenetic Networks: Concepts, Algorithms and Applications, Cambridge University Press.
JANSSON, J., NGUYEN, N., and SUNG, W.-K. (2006), “Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network,” SIAM Journal of Computing, 35, 1098–1121.
JANSSON, J., and SUNG, W.-K. (2006), “Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted Triplets,” Theoretical Computer Science, 363, 60–68.
JETTEN, L., and VAN IERSEL, L. (2016), “Nonbinary Tree-Based Phylogenetic Networks,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, in press.
LOVÁSZ, L., and PLUMMER, M.D. (1986), Matching Theory (Vol. 121, North-Holland Mathematics Studies), Elsevier Science Ltd.
NAKHLEH, L. (2011), “Evolutionary Phylogenetic Networks: Models and Issues,” in Problem Solving Handbook in Computational Biology and Bioinformatics, Springer, pp. 125–158.
OLDMAN, J.,WU, T., VAN IERSEL, L., and MOULTON, V. (2016), “Trilonet: Piecing Together Small Networks to Reconstruct Reticulate Evolutionary Histories,” Molecular Biology and Evolution, 33, 2151–2162.
SEMPLE, C., and STEEL, M. (2003), Phylogenetics, Oxford University Press.
TO, T,-H, and HABIB, M. (2009), “Level-k Phylogenetic Networks are Constructable from a Dense Triplet Set in Polynomial Time”, in Annual Symposium on Combinatorial Pattern Matching, Springer, pp. 275–288.
VAN IERSEL, L., KEIJSPER, J., KELK, S., STOUGIE, L., HAGEN, F., and BOEKHOUT, T. (2009), “Constructing Level-2 Phylogenetic Networks from Triplets,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6, 667–681.
VAN IERSEL, L., and KELK, S. (2011), “Constructing the Simplest Possible Phylogenetic Network from Triplets,” Algorithmica, 60, 207–235.
VAN IERSEL, L., and MOULTON, V. (2014), “Trinets Encode Tree-Child and Level-2 Phylogenetic Networks,” Journal of Mathematical Biology, 68, 1707–1729.
VAN IERSEL, L., MOULTON, V., DE SWART, E., and WU, T. (2017), “Binets: Fundamental Building Blocks for Phylogenetic Networks,” Bulletin of Mathematical Biology, 79, 1135–1154.
Author information
Authors and Affiliations
Corresponding author
Additional information
We would like to thank the two anonymous referees for their helpful and constructive comments on a previous version of this paper.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Huber, K.T., Moulton, V. & Wu, T. Hierarchies from Lowest Stable Ancestors in Nonbinary Phylogenetic Networks. J Classif 36, 200–231 (2019). https://doi.org/10.1007/s00357-018-9279-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00357-018-9279-5