Who is Who in Phylogenetic Networks

Publication no #683   Type :   Html | Bib | Both

Created: 2009-01-14 17:42:31     Modified: 2012-04-17 16:00:19

683 Thu-Hien To and Michel Habib. Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time. In CPM09, (5577):275-288, springer, 2009. Keywords: explicit network, from triplets, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/0901.1657.         Toggle abstract "For a given dense triplet set Τ there exist two natural questions [7]: Does there exist any phylogenetic network consistent with Τ? In case such networks exist, can we find an effective algorithm to construct one? For cases of networks of levels k = 0, 1 or 2, these questions were answered in [1,6,7,8,10] with effective polynomial algorithms. For higher levels k, partial answers were recently obtained in [11] with an O(/Τ/k+1)time algorithm for simple networks. In this paper, we give a complete answer to the general case, solving a problem proposed in [7]. The main idea of our proof is to use a special property of SN-sets in a level-k network. As a consequence, for any fixed k, we can also find a level-k network with the minimum number of reticulations, if one exists, in polynomial time. © 2009 Springer Berlin Heidelberg." @InProceedings{ToHabib2009,       AUTHOR = {To, Thu-Hien and Habib, Michel},       TITLE = {Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time},       YEAR = {2009},       BOOKTITLE = {CPM09},       NUMBER = {5577},       PAGES = {275-288},       SERIES = {LNCS},       PUBLISHER = {springer},       URL = {http://dx.doi.org/10.1007/978-3-642-02441-2_25},       NOTE = {http://arxiv.org/abs/0901.1657},       KEYWORDS = {explicit network, from triplets, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, reconstruction} }