Who is Who in Phylogenetic Networks

Publication no #475   Type :   Html | Bib | Both

Created: 2007-11-17 01:16:43     Modified: 2016-04-28 12:36:02

475 Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen and Teun Boekhout. Constructing level-2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450-462 of LNCS, springer, 2008. Keywords: explicit network, from triplets, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, polynomial, Program Level2, reconstruction. Note: http://homepages.cwi.nl/~iersel/level2full.pdf. An appendix with proofs can be found here http://arxiv.org/abs/0707.2890.         Toggle abstract "Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so, to construct such a network [24]. Here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data. © 2009 IEEE." @InProceedings{IKKSHB2008,       AUTHOR = {van Iersel, Leo and Keijsper, Judith and Kelk, Steven and Stougie, Leen and Hagen, Ferry and Boekhout, Teun},       TITLE = {Constructing level-2 phylogenetic networks from triplets},       YEAR = {2008},       BOOKTITLE = {RECOMB08},       VOLUME = {4955},       PAGES = {450-462},       SERIES = {LNCS},       PUBLISHER = {springer},       URL = {http://dx.doi.org/10.1109/TCBB.2009.22},       NOTE = {http://homepages.cwi.nl/~iersel/level2full.pdf. An appendix with proofs can be found here http://arxiv.org/abs/0707.2890},       ANNOTE = {BIBUPDATE : 20080124},       KEYWORDS = {explicit network, from triplets, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, polynomial, Program Level2, reconstruction} }