Who is Who in Phylogenetic Networks

Publications of Ming Li     Order by:   Type | Year

Associated keywords

approximation explicit-network from-network from-sequences galled-tree inapproximability phylogenetic-network phylogeny recombination

Article (Journal)

1 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."

InProceedings

2 Bin Ma, Lusheng Wang and Ming Li. Fixed topology alignment with recombination. In CPM98, Vol. 1448:174-188 of LNCS, springer, 1998. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://dx.doi.org/10.1007/BFb0030789.