Computing the minimum number of hybridization events for a consistent evolutionary history
From MaRDI portal
Publication:881571
DOI10.1016/j.dam.2006.08.008zbMath1111.92041OpenAlexW2148274789MaRDI QIDQ881571
Magnus Bordewich, Charles Semple
Publication date: 30 May 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.08.008
phylogenetic networkreticulate evolutionrooted phylogenetic treeagreement forestrooted subtree prune and regrafthybrid phylogeny
Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Complexity and performance of numerical algorithms (65Y20)
Related Items (30)
Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees ⋮ Combining Networks Using Cherry Picking Sequences ⋮ Kernelizations for the hybridization number problem on multiple nonbinary trees ⋮ Properties of normal phylogenetic networks ⋮ New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees ⋮ The rigid hybrid number for two phylogenetic trees ⋮ Analyzing and reconstructing reticulation networks under timing constraints ⋮ The hybrid number of a ploidy profile ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ On the existence of a cherry-picking sequence ⋮ Reconstruction of some hybrid phylogenetic networks with homoplasies from distances ⋮ On the complexity of computing the temporal hybridization number for two phylogenies ⋮ A quadratic kernel for computing the hybridization number of multiple trees ⋮ Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable ⋮ Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies ⋮ On the fixed parameter tractability of agreement-based phylogenetic distances ⋮ On unrooted and root-uncertain variants of several well-known phylogenetic network problems ⋮ Constructing the simplest possible phylogenetic network from triplets ⋮ When two trees go to war ⋮ Rotation distance is fixed-parameter tractable ⋮ Reconstruction of certain phylogenetic networks from the genomes at their leaves ⋮ Computing the rooted triplet distance between phylogenetic networks ⋮ NCHB: a method for constructing rooted phylogenetic networks from rooted triplets based on height function and binarization ⋮ Hybridization Number on Three Rooted Binary Trees is EPT ⋮ A 3-approximation algorithm for the subtree distance between phylogenies ⋮ Efficiently Calculating Evolutionary Tree Measures Using SAT ⋮ Note on the hybridization number and subtree distance in phylogenetics ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ Heading in the right direction? Using head moves to traverse phylogenetic network space ⋮ Computing Maximum Agreement Forests without Cluster Partitioning is Folly
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstructing evolution of sequences subject to recombination using parsimony
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Optimization, approximation, and complexity classes
- A framework for representing reticulate evolution
- On the computational complexity of the rooted subtree prune and regraft distance
- Bounding the number of hybridisation events for a consistent evolutionary history
- Fundamentals of Computation Theory
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- On the complexity of comparing evolutionary trees
This page was built for publication: Computing the minimum number of hybridization events for a consistent evolutionary history
