A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees

DOI10.1007/s00453-021-00914-8OpenAlexW2964024049MaRDI QIDQ2118383

Yanyan Li

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter algorithmsphylogenetic networkshybridization number

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (5)

Combining Networks Using Cherry Picking Sequences ⋮ New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees ⋮ Orchard networks are trees with additional horizontal arcs ⋮ Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks ⋮ Bounding the number of reticulations in a tree-child network that displays a set of trees

Uses Software

• SPRSupertrees

Cites Work

• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• A cluster reduction for computing the subtree distance between phylogenies
• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
• Bounding the number of hybridisation events for a consistent evolutionary history
• A quadratic kernel for computing the hybridization number of multiple trees
• Hybridization Number on Three Rooted Binary Trees is EPT
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Computing Maximum Agreement Forests without Cluster Partitioning is Folly

This page was built for publication: A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees