On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters

DOI10.1007/S00285-016-1068-3zbMATH Open1366.92087arXiv1511.08056OpenAlexW2177498511WikidataQ42288575 ScholiaQ42288575MaRDI QIDQ2358415FDOQ2358415

Authors: Philippe Gambette, Katharina T. Huber, Steven Kelk 

Publication date: 14 June 2017

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

Abstract: Phylogenetic networks have gained prominence over the years due to their ability to represent complex non-treelike evolutionary events such as recombination or hybridization. Popular combinatorial objects used to construct them are triplet systems and cluster systems, the motivation being that any network $N$ induces a triplet system $mathcalR(N)$ and a softwired cluster system $mathcalS(N)$. Since in real-world studies it cannot be guaranteed that all triplets/softwired clusters induced by a network are available it is of particular interest to understand whether subsets of $mathcalR(N)$ or $mathcalS(N)$ allow one to uniquely reconstruct the underlying network $N$. Here we show that even within the highly restricted yet biologically interesting space of level-1 phylogenetic networks it is not always possible to uniquely reconstruct a level-1 network $N$ even when all triplets in $mathcalR(N)$ or all clusters in $mathcalS(N)$ are available. On the positive side, we introduce a reasonably large subclass of level-1 networks the members of which are uniquely determined by their induced triplet/softwired cluster systems. Along the way, we also establish various enumerative results, both positive and negative, including results which show that certain special subclasses of level-1 networks $N$ can be uniquely reconstructed from proper subsets of $mathcalR(N)$ and $mathcalS(N)$. We anticipate these results to be of use in the design of, for example, algorithms for phylogenetic network inference.

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

Recommendations

• Constructing the simplest possible phylogenetic network from triplets
• Constructing the Simplest Possible Phylogenetic Network from Triplets
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• Computing and Combinatorics
• Trinets encode tree-child and level-2 phylogenetic networks

zbMATH Keywords

cluster systemstriplet systems

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Title not available (Why is that?)
• The complexity of reconstructing trees from qualitative characters and subtrees
• A framework for representing reticulate evolution
• The fine structure of galls in phylogenetic networks
• Basic phylogenetic combinatorics.
• Locating a tree in a phylogenetic network
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
• Reconstructing evolution of sequences subject to recombination using parsimony
• Computing the maximum agreement of phylogenetic networks
• Trinets encode tree-child and level-2 phylogenetic networks
• When two trees go to war
• Properties of normal phylogenetic networks
• On encodings of phylogenetic networks of bounded level
• All that glisters is not galled
• Constructing the simplest possible phylogenetic network from triplets
• Encoding and constructing 1-nested phylogenetic networks with trinets

Cited In (14)

• Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
• Encoding and constructing 1-nested phylogenetic networks with trinets
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances
• Constructing the Simplest Possible Phylogenetic Network from Triplets
• On encodings of phylogenetic networks of bounded level
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Computing consensus networks for collections of 1-nested phylogenetic networks
• Tripartitions do not always discriminate phylogenetic networks
• The weighted total cophenetic index: a novel balance index for phylogenetic networks
• Level-1 phylogenetic networks and their balanced minimum evolution polytopes
• Uprooted phylogenetic networks
• Constructing the simplest possible phylogenetic network from triplets
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats

Uses Software

• PhyloNetwork

This page was built for publication: On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters

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