title: A reduction algorithm for computing the hybridization number of two trees.
abstract: Hybridization is an important evolutionary process for many groups of species. Thus, conflicting signals in a data set may not be the result of sampling or modeling errors, but due to the fact that hybridization has played a significant role in the evolutionary history of the species under consideration. Assuming that the initial set of gene trees is correct, a basic problem for biologists is to compute this minimum number of hybridization events to explain this set. In this paper, we describe a new reduction-based algorithm for computing the minimum number, when the initial data set consists of two trees. Although the two-tree problem is NP-hard, our algorithm always gives the exact solution and runs efficiently on many real biological problems. Previous algorithms for the two-tree problem either solve a restricted version of the problem or give an answer with no guarantee of the closeness to the exact solution. We illustrate our algorithm on a grass data set. This new algorithm is freely available for application at either http://www.bi.uni-duesseldorf.de/approximately linz or http://www.math.canterbury.ac.nz/approximately cas83.
authors.affiliation: Department of Computer Science, Durham University, Durham DH1 3LE, United Kingdom.
authors.forename: Magnus
authors.initials: M
authors.lastname: Bordewich
authors.forename: Simone
authors.initials: S
authors.lastname: Linz
authors.forename: Katherine
authors.initials: K
authors.lastname: St John
authors.forename: Charles
authors.initials: C
authors.lastname: Semple