Reconstructing tree-child networks from reticulate-edge-deleted subnetworks

DOI10.1007/S11538-019-00641-WMaRDI QIDQ2008245zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 22 November 2019

Published in Bulletin of Mathematical Biology (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

tree-child networksphylogenetic networknetwork encodingreticulate-edge-deleted subnetworks

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15)

Abstract: Network reconstruction lies at the heart of phylogenetic research. Two well studied classes of phylogenetic networks include tree-child networks and level-$k$ networks. In a tree-child network, every non-leaf node has a child that is a tree node or a leaf. In a level-$k$ network, the maximum number of reticulations contained in a biconnected component is $k$. Here, we show that level-$k$ tree-child networks are encoded by their reticulate-edge-deleted subnetworks, which are subnetworks obtained by deleting a single reticulation edge, if $kgeq2$. Following this, we provide a polynomial-time algorithm for uniquely reconstructing such networks from their reticulate-edge-deleted subnetworks. Moreover, we show that this can even be done when considering subnetworks obtained by deleting one reticulation edge from each biconnected component with $k$ reticulations.

Recommendations

• Not all phylogenetic networks are leaf-reconstructible
• A pattern recognition-based approach for phylogenetic network construction with constrained recombination
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
• Leaf-reconstructibility of phylogenetic networks
• Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances

Cites work

• Binets: fundamental building blocks for phylogenetic networks
• Constructing tree-child networks from distance matrices
• Determining phylogenetic networks from inter-taxa distances
• Encoding and constructing 1-nested phylogenetic networks with trinets
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
• Properties of normal phylogenetic networks
• Reconstructing evolution of sequences subject to recombination using parsimony
• Recovering normal networks from shortest inter-taxa distance information
• Research in Computational Molecular Biology
• Research in Computational Molecular Biology
• Trinets encode tree-child and level-2 phylogenetic networks

Cited in

(12)

• Classes of explicit phylogenetic networks and their biological and mathematical significance
• Orienting undirected phylogenetic networks
• Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances
• Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks
• A class of phylogenetic networks reconstructable from ancestral profiles
• On cherry-picking and network containment
• The tree of blobs of a species network: identifiability under the coalescent
• Identifiability of local and global features of phylogenetic networks from average distances
• Leaf-reconstructibility of phylogenetic networks
• Not all phylogenetic networks are leaf-reconstructible
• Combining Networks Using Cherry Picking Sequences
• Caterpillars on three and four leaves are sufficient to binary normal networks

This page was built for publication: Reconstructing tree-child networks from reticulate-edge-deleted subnetworks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2008245)