Linear time algorithm for tree-child network containment

DOI10.1007/978-3-030-42266-0_8zbMATH Open1500.92066OpenAlexW3012958836MaRDI QIDQ5041129FDOQ5041129

Authors Remie Janssen, Yukihiro Murakami 

Publication date 13 October 2022

Published in Algorithms for Computational Biology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-42266-0_8

zbMATH Keywords

phylogeneticstree-child networksnetwork containmenttree-child sequences

Mathematics Subject Classification ID

Problems related to evolution (92D15) Systems biology, networks (92C42)

Recommendations

• Solving the tree containment problem in linear time for nearly stable phylogenetic networks
• On cherry-picking and network containment
• Locating a tree in a phylogenetic network
• Solving the tree containment problem for reticulation-visible networks in linear time
• Solving the tree containment problem for genetically stable networks in quadratic time

Cites Work

• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
• Deciding the existence of a cherry-picking sequence is hard on two trees
• Locating a tree in a phylogenetic network
• Seeing the trees and their branches in the network is hard
• Solving the tree containment problem for genetically stable networks in quadratic time
• Solving the tree containment problem in linear time for nearly stable phylogenetic networks

Cited In (7)

• Embedding phylogenetic trees in networks of low treewidth
• Solving the tree containment problem in linear time for nearly stable phylogenetic networks
• Solving the tree containment problem for reticulation-visible networks in linear time
• On cherry-picking and network containment
• Finding agreement cherry-reduced subnetworks in level-1 networks
• Novel phylogenetic network distances based on cherry picking
• Do branch lengths help to locate a tree in a phylogenetic network?

This page was built for publication: Linear time algorithm for tree-child network containment

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