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

DOI10.1007/S00453-022-00946-8MaRDI QIDQ2149104zbMATHOpenAlexFDO

Authors Yanyan Li

Publication date 28 June 2022

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

phylogenetic networksparameterized algorithmshybridization numberphylogenetic trees

Mathematics Subject Classification ID

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

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.

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

Cites work

• A cluster reduction for computing the subtree distance between 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
• 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
• Deciding the existence of a cherry-picking sequence is hard on two trees
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• On the complexity of computing the temporal hybridization number for two phylogenies

Cited in

(7)

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

Describes a project that uses

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)