title: Quantifying hybridization in realistic time.
abstract: Recently, numerous practical and theoretical studies in evolutionary biology aim at calculating the extent to which reticulation-for example, horizontal gene transfer, hybridization, or recombination-has influenced the evolution for a set of present-day species. It has been shown that inferring the minimum number of hybridization events that is needed to simultaneously explain the evolutionary history for a set of trees is an NP-hard and also fixed-parameter tractable problem. In this article, we give a new fixed-parameter algorithm for computing the minimum number of hybridization events for when two rooted binary phylogenetic trees are given. This newly developed algorithm is based on interleaving-a technique using repeated kernelization steps that are applied throughout the exhaustive search part of a fixed-parameter algorithm. To show that our algorithm runs efficiently to be applicable to a wide range of practical problem instances, we apply it to a grass data set and highlight the significant improvements in terms of running times in comparison to an algorithm that has previously been implemented.
authors.affiliation: Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand.
authors.forename: Joshua
authors.initials: J
authors.lastname: Collins
authors.forename: Simone
authors.initials: S
authors.lastname: Linz
authors.forename: Charles
authors.initials: C
authors.lastname: Semple
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D019143:Evolution, Molecular; D006824:Hybridization, Genetic / Q000235:genetics*; D008957:Models, Genetic; D013997:Time Factors