Linear Time Algorithm for Tree-Child Network Containment

DOI10.1007/978-3-030-42266-0_8zbMath1500.92066OpenAlexW3012958836MaRDI QIDQ5041129

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

tree-child networksphylogeneticsnetwork containmenttree-child sequences

Mathematics Subject Classification ID

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

Related Items (3)

Finding agreement cherry-reduced subnetworks in level-1 networks ⋮ On cherry-picking and network containment ⋮ Novel phylogenetic network distances based on cherry picking

Cites Work

• Seeing the trees and their branches in the network is hard
• Solving the tree containment problem in linear time for nearly stable phylogenetic networks
• Locating a tree in a phylogenetic network
• 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
• Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time

This page was built for publication: Linear Time Algorithm for Tree-Child Network Containment