Reticulation-visible networks

DOI10.1016/J.AAM.2016.04.004MaRDI QIDQ281904zbMATH OpenOpenAlexFDO

Authors Magnus Bordewich, Charles Semple

Publication date 11 May 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

phylogenetic networkreticulation-visible networktree containment problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let $X$ be a finite set, $mathcalN$ be a reticulation-visible network on $X$, and $mathcalT$ be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not $mathcalN$ displays $mathcalT$. Furthermore, for all $|X|ge1$, we show that $mathcalN$ has at most $8|X|-7$ vertices in total and at most $3|X|-3$ reticulation vertices, and that these upper bounds are sharp.

Recommendations

• A decomposition theorem and two algorithms for reticulation-visible networks
• Locating a tree in a phylogenetic network in quadratic time
• When is a phylogenetic network simply an amalgamation of two trees?
• Display sets of normal and tree-child networks
• Solving the tree containment problem for reticulation-visible networks in linear time

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Locating a tree in a phylogenetic network
• Locating a tree in a phylogenetic network in quadratic time
• Seeing the trees and their branches in the network is hard

Cited in

(20)

• Solving the tree containment problem in linear time for nearly stable phylogenetic networks
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• When is a phylogenetic network simply an amalgamation of two trees?
• Non-essential arcs in phylogenetic networks
• Classes of explicit phylogenetic networks and their biological and mathematical significance
• Counting and enumerating galled networks
• Counting and enumerating tree-child networks and their subclasses
• Display sets of normal and tree-child networks
• Phylogenetic networks that are their own fold-ups
• Displaying trees across two phylogenetic networks
• Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks
• A QUBO formulation for the tree containment problem
• Tree containment with soft polytomies
• scientific article; zbMATH DE number 7238964 (Why is no real title available?)
• Size of a phylogenetic network
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
• Counting phylogenetic networks with few reticulation vertices: galled and reticulation-visible networks
• Characterizing and transforming DAGs within the \(\mathfrak{I}\)-lca framework
• ``Normal phylogenetic networks may be emerging as the leading class
• A decomposition theorem and two algorithms for reticulation-visible networks

This page was built for publication: Reticulation-visible networks

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