Who is Who in Phylogenetic Networks

Publication no #680   Type :   Html | Bib | Both

Created: 2008-12-25 23:13:14     Modified: 2014-07-08 07:51:58

680 Bin Ma, Lusheng Wang and Ming Li. Fixed topology alignment with recombination. In DAM, Vol. 104:281-300, 2000. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7759.         Toggle 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. © 2014 van Iersel et al.; licensee BioMed Central Ltd." @Article{MWL2000,       AUTHOR = {Ma, Bin and Wang, Lusheng and Li, Ming},       TITLE = {Fixed topology alignment with recombination},       YEAR = {2000},       JOURNAL = {DAM},       VOLUME = {104},       PAGES = {281-300},       URL = {http://dx.doi.org/10.1186/1471-2105-15-127},       NOTE = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7759},       ANNOTE = {BIBUPDATE : 20081225},       KEYWORDS = {approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination} }