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

DOI10.1007/S11538-019-00641-WzbMATH Open1428.92080arXiv1811.06777OpenAlexW2963548057WikidataQ91816155 ScholiaQ91816155MaRDI QIDQ2008245FDOQ2008245

Authors: Yanyan Li 

Publication date: 22 November 2019

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

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.

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

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

zbMATH Keywords

tree-child networksphylogenetic networknetwork encodingreticulate-edge-deleted subnetworks

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Identifiability of local and global features of phylogenetic networks from average distances
• Orienting undirected phylogenetic networks
• Not all phylogenetic networks are leaf-reconstructible
• The tree of blobs of a species network: identifiability under the coalescent
• Leaf-reconstructibility of phylogenetic networks
• Classes of explicit phylogenetic networks and their biological and mathematical significance
• Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances
• Combining Networks Using Cherry Picking Sequences
• On cherry-picking and network containment
• A class of phylogenetic networks reconstructable from ancestral profiles
• 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)