Bordewich, M. and Linz, S. and St. John, K. and Semple, C. (2007) 'A reduction algorithm for computing the hybridization number of two trees.', Evolutionary bioinformatics., 3 . pp. 86-98.
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.
|Keywords:||Hybridization networks, Reticulate evolution, Agreement forest.|
|Full text:||PDF - Published Version (408Kb)|
|Publisher Web site:||http://www.la-press.com/journal.php?journal_id=17&issue_id=18|
|Publisher statement:||This work is licensed under a Creative Commons Attribution 3.0 License (http://creativecommons.org/licenses/by/3.0/).|
|Record Created:||05 Jan 2010 09:50|
|Last Modified:||06 Dec 2011 16:30|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|