Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

DOI10.1007/s00453-015-0069-8zbMath1357.92056arXiv1411.6804OpenAlexW1911223732WikidataQ59603599 ScholiaQ59603599MaRDI QIDQ513300

Leo van Iersel, Katharina T. Huber, Celine Scornavacca, Vincent L. Moulton, Taoyang Wu

Publication date: 6 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.6804

zbMATH Keywords

polynomial-time algorithmNP-hardphylogenetic treephylogenetic networkexponential-time algorithmsupernetworkAho algorithmtrinet

Mathematics Subject Classification ID

Problems related to evolution (92D15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (16)

Binets: fundamental building blocks for phylogenetic networks ⋮ Identifiability of species network topologies from genomic sequences using the logDet distance ⋮ Combining Networks Using Cherry Picking Sequences ⋮ Classes of explicit phylogenetic networks and their biological and mathematical significance ⋮ An algorithm for reconstructing level-2 phylogenetic networks from trinets ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Reconstruction of LGT networks from tri-LGT-nets ⋮ Beyond representing orthology relations by trees ⋮ Caterpillars on three and four leaves are sufficient to binary normal networks ⋮ Counting phylogenetic networks of level 1 and 2 ⋮ Trinets encode orchard phylogenetic networks ⋮ Identifying species network features from gene tree quartets under the coalescent model ⋮ Quarnet inference rules for level-1 networks ⋮ NCHB: a method for constructing rooted phylogenetic networks from rooted triplets based on height function and binarization ⋮ Hierarchies from lowest stable ancestors in nonbinary phylogenetic networks ⋮ Treewidth of display graphs: bounds, brambles and applications

Uses Software

• Dendroscope

Cites Work

• Unnamed Item
• Unnamed Item
• On encodings of phylogenetic networks of bounded level
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• Computing the maximum agreement of phylogenetic networks
• Trinets encode tree-child and level-2 phylogenetic networks
• Encoding and constructing 1-nested phylogenetic networks with trinets
• Computing the rooted triplet distance between galled trees by counting triangles
• The Fine Structure of Galls in Phylogenetic Networks
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
• Research in Computational Molecular Biology

This page was built for publication: Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets