Combining Networks Using Cherry Picking Sequences

DOI10.1007/978-3-030-42266-0_7MaRDI QIDQ5041128zbMATH OpenOpenAlexFDO

Authors

Publication date 13 October 2022

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

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

zbMATH Keywords

FPT algorithmsnetwork hybridizationphylogenetic networkstree-child networks

Mathematics Subject Classification ID

Problems related to evolution (92D15)

Abstract: Phylogenetic networks are important for the study of evolution. The number of methods to find such networks is increasing, but most such methods can only reconstruct small networks. To find bigger networks, one can attempt to combine small networks. In this paper, we study the {sc Network Hybridization} problem, a problem of combining networks into another network with low complexity. We characterize this complexity via a restricted problem, {sc Tree-child Network Hybridization}, and we present an FPT algorithm to efficiently solve this restricted problem.

Recommendations

• Networks for sorting multitonic sequences
• A note on implementing combining networks
• scientific article; zbMATH DE number 3885324
• On probabilistic networks for selection, merging, and sorting
• Network structure and naive sequential learning
• scientific article; zbMATH DE number 3859160
• Accelerating certain outputs of merging and sorting networks
• scientific article; zbMATH DE number 403945

Cites work

• A class of phylogenetic networks reconstructable from ancestral profiles
• A framework for representing reticulate evolution
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• A quadratic kernel for computing the hybridization number of multiple trees
• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
• Binets: fundamental building blocks for phylogenetic networks
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Fixed-parameter algorithms for maximum agreement forests
• Hybridization number on three rooted binary trees is EPT
• Leaf-reconstructibility of phylogenetic networks
• Quarnet inference rules for level-1 networks
• Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
• Reconstructing tree-child networks from reticulate-edge-deleted subnetworks
• Trinets encode tree-child and level-2 phylogenetic networks

Cited in

(6)

• A note on implementing combining networks
• On the existence of a cherry-picking sequence
• Novel phylogenetic network distances based on cherry picking
• On cherry-picking and network containment
• Finding agreement cherry-reduced subnetworks in level-1 networks
• Reconstructing phylogenetic networks via Cherry picking and machine learning

This page was built for publication: Combining Networks Using Cherry Picking Sequences

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