A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees

van Iersel, L.J.J.; Kelk, Steven; Lekić, Nela; Scornavacca, Celine

A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees

Journal article (2014)

Authors

L.J.J. van Iersel Centrum Wiskunde & Informatica (CWI)

Steven Kelk

Nela Lekić

Celine Scornavacca

Affiliation

External organisation

Phylogenetic networks Approximation algorithms Hybridization number Directed feedback vertex set

To reference this document use:

http://resolver.tudelft.nl/uuid:ad99cf6c-db1d-41b0-be5f-ec3d799bbf07

More Info

expand_more

Published Date

2014

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

Background
Reticulate events play an important role in determining evolutionary relationships. The problem of computing the minimum number of such events to explain discordance between two phylogenetic trees is a hard computational problem. Even for binary trees, exact solvers struggle to solve instances with reticulation number larger than 40-50.
Results
Here we present CycleKiller and NonbinaryCycleKiller, the first methods to produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations.
Conclusions
Using simulations, we demonstrate that these algorithms run quickly for large and difficult instances, producing solutions that are very close to optimality. As a spin-off from our simulations we also present TerminusEst, which is the fastest exact method currently available that can handle nonbinary trees: this is used to measure the accuracy of the NonbinaryCycleKiller algorithm. All three methods are based on extensions of previous theoretical work (SIDMA 26(4):1635-1656, TCBB 10(1):18-25, SIDMA 28(1):49-66) and are publicly available. We also apply our methods to real data.