- A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees
- IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Volume | Issue number
- 10 | 1
- Pages (from-to)
- Number of pages
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
Here, we present a new fixed parameter tractable algorithm to compute the hybridization number (r) of two rooted, not necessarily binary phylogenetic trees on taxon set (X) in time ((6r r) · poly(n)), where (n= |X|). The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on (X), and several insights from the softwired clusters literature. This yields a surprisingly simple and practical bounded-search algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem.
- go to publisher's site
- Other links
- Link to publication in Scopus
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.