A Reduction Algorithm for Computing the Hybridization Number of Two Trees

Bordewich, M.; Linz, S.; St. John, K.; Semple, C.

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/~linz or http://www.math.canterbury.ac.nz/~cas83.

Citation

Bordewich, M., Linz, S., St. John, K., & Semple, C. (2007). A Reduction Algorithm for Computing the Hybridization Number of Two Trees. Evolutionary Bioinformatics, 3, 86-98

• Journal Article Type: Article
• Publication Date: May 1, 2007
• Deposit Date: Jan 5, 2010
• Publicly Available Date: Jan 6, 2010
• Journal: Evolutionary Bioinformatics
• Electronic ISSN: 1176-9343
• Publisher: SAGE Publications
• Peer Reviewed: Peer Reviewed
• Volume: 3
• Pages: 86-98
• Keywords: Hybridization networks, Reticulate evolution, Agreement forest.
• Public URL: https://durham-repository.worktribe.com/output/1554772
• Publisher URL: http://www.la-press.com/journal.php?journal_id=17&issue_id=18