Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies

Throughout the last decade, we have seen much progress towards characterising and computing the minimum hybridisation number for a set P of rooted phylogenetic trees. Roughly speaking, this minimum quantifies the number of hybridisation events needed to explain a set of phylogenetic trees by simultaneously embedding them into a phylogenetic network. From a mathematical viewpoint, the notion of agreement forests is the underpinning concept for almost all results that are related to calculating the minimum hybridisation number for when |P|=2. However, despite various attempts, characterising this number in terms of agreement forests for |P|>2 remains elusive. In this paper, we characterise the minimum hybridisation number for when P is of arbitrary size and consists of not necessarily binary trees. Building on our previous work on cherry-picking sequences, we first establish a new characterisation to compute the minimum hybridisation number in the space of tree-child networks. Subsequently, we show how this characterisation extends to the space of all rooted phylogenetic networks. Moreover, we establish a particular hardness result that gives new insight into some of the limitations of agreement forests.

• Publication year

  2017

• Venue

  Advances in Applied Mathematics

• Publication date

  2017-12-12

• Fields of study

  Biology, Mathematics, Computer Science

• Identifiers
  DOI 10.1016/J.AAM.2019.01.004arXiv 1712.04131
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Foreign DNA acquisition by invertebrate genomes.

  2017cited by this paper
• How reticulated are species?

  2015cited by this paper
• Horizontal gene transfer: building the web of life

  2015cited by this paper
• Determining phylogenetic networks from inter-taxa distances

  2015cited by this paper
• Hybridization Number on Three Rooted Binary Trees is EPT

  2014influential reference
• Ancient hybridizations among the ancestral genomes of bread wheat

  2014cited by this paper
• Cherry Picking: A Characterization of the Temporal Hybridization Number for a Set of Phylogenies

  2013influential reference
• An Ultrafast Tool for Minimum Reticulate Networks

  2013cited by this paper
• On the complexity of computing the temporal hybridization number for two phylogenies

  2013cited by this paper
• Algorithms for Reticulate Networks of Multiple Phylogenetic Trees

  2012cited by this paper
• A Simple Fixed Parameter Tractable Algorithm for Computing the Hybridization Number of Two (Not Necessarily Binary) Trees

  2012cited by this paper
• Quantifying Hybridization in Realistic Time

  2011cited by this paper
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set

  2011cited by this paper
• Fast Computation of the Exact Hybridization Number of Two Phylogenetic Trees

  2010cited by this paper
• Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees

  2010cited by this paper
• Locating a tree in a phylogenetic network

  2010cited by this paper
• Comparison of Tree-Child Phylogenetic Networks

  2007cited by this paper
• Computing the minimum number of hybridization events for a consistent evolutionary history

  2007cited by this paper
• Bounding the Number of Hybridisation Events for a Consistent Evolutionary History

  2005cited by this paper
• Phylogenetic networks: modeling, reconstructibility, and accuracy

  2004cited by this paper
• Complexity of common subsequence and supersequence problems and related problems

  1989cited by this paper
• BIOINFORMATICS ORIGINAL PAPER

  year unknowncited by this paper
• Citation for Published Item: Use Policy Computing the Hybridization Number of Two Phylogenetic Trees Is Fixed-parameter Tractable

  year unknowncited by this paper

• PhyloX: A Python package for complete phylogenetic network workflows

  2024cites this paper
• A Wild Sheep Chase Through an Orchard

  2024cites this paper
• Inferring Phylogenetic Networks from Multifurcating Trees via Cherry Picking and Machine Learning.

  2024cites this paper
• When is a set of phylogenetic trees displayed by a normal network?

  2024influential citation
• The tree-child network inference problem for line trees and the shortest common supersequence problem for permutation strings

  2024cites this paper
• Characterising rooted and unrooted tree-child networks

  2024influential citation
• Finding agreement cherry-reduced subnetworks in level-1 networks

  2023cites this paper
• The tree-child network inference problem for line trees and the shortest common supersequences for permutations are NP-hard

  2023cites this paper
• Constructing phylogenetic networks via cherry picking and machine learning

  2023influential citation
• A fast and scalable method for inferring phylogenetic networks from trees by aligning lineage taxon strings

  2023cites this paper
• A Fixed-Parameter Tractable Algorithm for Finding Agreement Cherry-Reduced Subnetworks in Level-1 Orchard Networks

  2023cites this paper
• Computing the Bounds of the Number of Reticulations in a Tree-Child Network That Displays a Set of Trees

  2023influential citation
• The tree-child network problem for line trees and the shortest common supersequences for permutations

  2023cites this paper
• Cherry picking in forests: A new characterization for the unrooted hybrid number of two phylogenetic trees

  2022cites this paper
• Defining Phylogenetic Network Distances Using Cherry Operations

  2022cites this paper
• Reconstructing Phylogenetic Networks via Cherry Picking and Machine Learning

  2022cites this paper
• The rigid hybrid number for two phylogenetic trees

  2021cites this paper
• Comparing the topology of phylogenetic network generators

  2021cites this paper
• Novel Phylogenetic Network Distances Based on Cherry Picking

  2021cites this paper
• Algorithms for Computational Biology: 7th International Conference, AlCoB 2020, Missoula, MT, USA, April 13–15, 2020, Proceedings

  2020influential citation
• New FPT Algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees

  2020cites this paper
• Weakly displaying trees in temporal tree-child network

  2020cites this paper
• Linear Time Algorithm for Tree-Child Network Containment

  2020cites this paper
• A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

  2019influential citation
• Combining Networks Using Cherry Picking Sequences

  2019cites this paper
• Tree structure in phylogenetic networks

  2019cites this paper
• On cherry-picking and network containment

  2018cites this paper
• Solving Phylogenetic Network Containment Problems using Cherry-picking Sequences

  2018influential citation