On cherry-picking and network containment

DOI10.1016/j.tcs.2020.12.031zbMath1478.92134arXiv1812.08065OpenAlexW3120473550MaRDI QIDQ2219064

Remie Janssen, Yukihiro Murakami

Publication date: 19 January 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

linear-time algorithmsphylogenetic networkstree containmentcherry-picking networkscherry-picking sequencesnetwork containment

Mathematics Subject Classification ID

Problems related to evolution (92D15)

Related Items (13)

Classes of explicit phylogenetic networks and their biological and mathematical significance ⋮ Orchard networks are trees with additional horizontal arcs ⋮ Rooted NNI moves and distance-1 tail moves on tree-based phylogenetic networks ⋮ Autopolyploidy, allopolyploidy, and phylogenetic networks with horizontal arcs ⋮ Labellable phylogenetic networks ⋮ Finding agreement cherry-reduced subnetworks in level-1 networks ⋮ Orienting undirected phylogenetic networks ⋮ Generation of orchard and tree-child networks ⋮ Phylogenetic network classes through the lens of expanding covers ⋮ Trinets encode orchard phylogenetic networks ⋮ Defining phylogenetic networks using ancestral profiles ⋮ A unifying characterization of tree-based networks and orchard networks using cherry covers ⋮ Novel phylogenetic network distances based on cherry picking

Cites Work

• Determining phylogenetic networks from inter-taxa distances
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• 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
• Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
• A class of phylogenetic networks reconstructable from ancestral profiles
• Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time
• Combining Networks Using Cherry Picking Sequences
• Linear Time Algorithm for Tree-Child Network Containment

This page was built for publication: On cherry-picking and network containment