Folding and unfolding phylogenetic trees and networks

DOI10.1007/S00285-016-0993-5MaRDI QIDQ338372zbMATH OpenOpenAlexWikidataFDO

Authors Katharina T. Huber, Taoyang Wu, Vincent Moulton, Mike Steel

Publication date 4 November 2016

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/1506.04438

zbMATH Keywords

phylogenetic networksgraph fibrationsmulti-labelled treestree and network reconciliationuniversal cover of a digraph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Phylogenetic networks are rooted, labelled directed acyclic graphs which are commonly used to represent reticulate evolution. There is a close relationship between phylogenetic networks and multi-labelled trees (MUL-trees). Indeed, any phylogenetic network $N$ can be 'unfolded' to obtain a MUL-tree $U(N)$ and, conversely, a MUL-tree $T$ can in certain circumstances be 'folded' to obtain a phylogenetic network $F(T)$ that exhibits $T$. In this paper, we study properties of the operations $U$ and $F$ in more detail. In particular, we introduce the class of stable networks, phylogenetic networks $N$ for which $F(U(N))$ is isomorphic to $N$, characterise such networks, and show that that they are related to the well-known class of tree-sibling networks. We also explore how the concept of displaying a tree in a network $N$ can be related to displaying the tree in the MUL-tree $U(N)$. To do this, we develop a phylogenetic analogue of graph fibrations. This allows us to view $U(N)$ as the analogue of the universal cover of a digraph, and to establish a close connection between displaying trees in $U(N)$ and reconciling phylogenetic trees with networks.

Recommendations

• Phylogenetic networks that are their own fold-ups
• Computational Science – ICCS 2005
• Tree-based unrooted phylogenetic networks
• Phylogenetic networks
• Phylogenetic Networks
• Phylogenetic networks from multi-labelled trees
• Rooting gene trees via phylogenetic networks
• The space of tree-based phylogenetic networks
• Transforming phylogenetic networks: moving beyond tree space

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Computing a consensus of multilabeled trees
• Fibrations of graphs
• Locating a tree in a phylogenetic network
• Phylogenetic networks from multi-labelled trees
• ReCombinatorics. The algorithmics of ancestral recombination graphs and explicit phylogenetic networks. With contributions from Charles H. Langley, Yun S. Song and Yufeng Wu
• Seeing the trees and their branches in the network is hard

Cited in

(18)

• Phylogenetic networks that are their own fold-ups
• Labellable phylogenetic networks
• Complexity and algorithms for MUL-tree pruning
• Embedding phylogenetic trees in networks of low treewidth
• Classes of explicit phylogenetic networks and their biological and mathematical significance
• Polynomial invariants for cactuses
• Zigzag zoology: Rips zigzags for homology inference
• Bounding the softwired parsimony score of a phylogenetic network
• Anomalous networks under the multispecies coalescent: theory and prevalence
• Morphological hierarchies: a unifying framework with new trees
• Uprooted phylogenetic networks
• Phylogenetic network classes through the lens of expanding covers
• The hybrid number of a ploidy profile
• Overlaid species forests
• Reconciling event-labeled gene trees with MUL-trees and species networks
• The rigid hybrid number for two phylogenetic trees
• MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
• The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics

Describes a project that uses

Uses Software

• PhyloNetwork
• PADRE

This page was built for publication: Folding and unfolding phylogenetic trees and networks

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