Hybridization number on three rooted binary trees is EPT

DOI10.1137/15M1036579MaRDI QIDQ2818206zbMATH OpenOpenAlexFDO

Authors Leo Van Iersel, Steven Kelk, Nela Lekić, Chris Whidden, Norbert Zeh

Publication date 6 September 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

agreement forestfixed parameter tractabilityhybridization numberreticulate evolutionrooted phylogenetic networkrooted phylogenetic tree

Mathematics Subject Classification ID

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

Abstract: Phylogenetic networks are leaf-labelled directed acyclic graphs that are used to describe non-treelike evolutionary histories and are thus a generalization of phylogenetic trees. The hybridization number of a phylogenetic network is the sum of all indegrees minus the number of nodes plus one. The Hybridization Number problem takes as input a collection of phylogenetic trees and asks to construct a phylogenetic network that contains an embedding of each of the input trees and has a smallest possible hybridization number. We present an algorithm for the Hybridization Number problem on three binary trees on $n$ leaves, which runs in time $O(c^{k}poly(n))$, with $k$ the hybridization number of an optimal network and $c$ a constant. For two trees, an algorithm with running time $O(3.18^{k}n)$ was proposed before whereas an algorithm with running time $O(c^{k}poly(n))$ had prior to this article remained elusive for more than two trees. The algorithm for two trees uses the close connection to acyclic agreement forests to achieve a linear exponent in the running time, while previous algorithms for more than two trees (explicitly or implicitly) relied on a brute force search through all possible underlying network topologies, leading to running times that are not $O(c^{k}poly(n))$ for any $c$. The connection to acyclic agreement forests is much weaker for more than two trees, so even given the right agreement forest, reconstructing the network poses major challenges. We prove novel structural results that allow us to reconstruct a network without having to guess the underlying topology. Our techniques generalize to more than three input trees with the exception of one key lemma that maps nodes in the network to tree nodes and, thus, minimizes the amount of guessing involved in constructing the network. The main open problem therefore is to establish a similar mapping for more than three trees.

Recommendations

• Kernelizations for the hybridization number problem on multiple nonbinary trees
• New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• On the complexity of computing the temporal hybridization number for two phylogenies

Cites work

• A framework for representing reticulate evolution
• A quadratic kernel for computing the hybridization number of multiple trees
• A supertree method for rooted trees
• Approximation algorithms for nonbinary agreement forests
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Bounding the number of hybridisation events for a consistent evolutionary history
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Fixed-parameter algorithms for maximum agreement forests
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Kernelizations for the hybridization number problem on multiple nonbinary trees

Cited in

(12)

• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
• When is a phylogenetic network simply an amalgamation of two trees?
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
• Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Heading in the right direction? Using head moves to traverse phylogenetic network space
• Combining Networks Using Cherry Picking Sequences
• A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
• Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
• Embedding phylogenetic trees in networks of low treewidth

This page was built for publication: Hybridization number on three rooted binary trees is EPT

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