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

DOI10.1007/S00285-016-1068-3MaRDI QIDQ2358415zbMATH OpenOpenAlexWikidataFDO

Authors Philippe Gambette, Katharina T. Huber, Steven Kelk

Publication date 14 June 2017

Published in Journal 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/1511.08056

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)

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.

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

Cites work

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

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
• On encodings of phylogenetic networks of bounded level
• Constructing the Simplest Possible Phylogenetic Network from Triplets
• 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
• Level-1 phylogenetic networks and their balanced minimum evolution polytopes
• The weighted total cophenetic index: a novel balance index for phylogenetic networks
• Constructing the simplest possible phylogenetic network from triplets
• Uprooted phylogenetic networks
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats

Describes a project that uses

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)