New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees

DOI10.1007/S00453-022-00946-8zbMATH Open1494.92075arXiv2007.13615OpenAlexW4229054548MaRDI QIDQ2149104FDOQ2149104

Authors: Yanyan Li 

Publication date: 28 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We study the problem of finding a temporal hybridization network for a set of phylogenetic trees that minimizes the number of reticulations. First, we introduce an FPT algorithm for this problem on an arbitrary set of $m$ binary trees with $n$ leaves each with a running time of $O(5^{k}cdotncdotm)$, where $k$ is the minimum temporal hybridization number. We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most $d$ and at most $k$ reticulations in $O((8k{)}^d{5}^{k}cdotncdotm)$ time. Lastly, we introduce a $O(6^{k}k!cdotkcdot{n}^2)$ time algorithm for computing a minimum temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.

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

Recommendations

• On the complexity of computing the temporal hybridization number for two phylogenies
• Hybridization number on three rooted binary trees is EPT
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• Analyzing and reconstructing reticulation networks under timing constraints
• Kernelizations for the hybridization number problem on multiple nonbinary trees

zbMATH Keywords

phylogenetic networksparameterized algorithmshybridization numberphylogenetic trees

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A cluster reduction for computing the subtree distance between phylogenies
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• On the complexity of computing the temporal hybridization number for two phylogenies
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• 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

Cited In (8)

• On the complexity of computing the temporal hybridization number for two phylogenies
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Hybridization number on three rooted binary trees is EPT
• Orchard networks are trees with additional horizontal arcs
• Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
• A quadratic kernel for computing the hybridization number of multiple trees
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• Analyzing and reconstructing reticulation networks under timing constraints

Uses Software

• GitHub

This page was built for publication: New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees

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