Who is Who in Phylogenetic Networks

Publication no #2228   Type :   Html | Bib | Both

Created: 2012-07-18 15:56:01     Modified: 2012-09-07 00:09:43

2228 Michel Habib and Thu-Hien To. Constructing a Minimum Phylogenetic Network from a Dense Triplet Set. In JBCB, Vol. 10(5):1250013, 2012. Keywords: explicit network, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/1103.2266.         Toggle abstract "For a given set L of species and a set T of triplets on L, we seek to construct a phylogenetic network which is consistent with T i.e. which represents all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When T is dense, there exist polynomial time algorithms to construct level-0,1 and 2 networks (Aho et al., 1981; Jansson, Nguyen and Sung, 2006; Jansson and Sung, 2006; Iersel et al., 2009). For higher levels, partial answers were obtained in the paper by Iersel and Kelk (2008), with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in Jansson and Sung (2006) and Iersel et al. (2009). For any k fixed, it is possible to construct a level-k network having the minimum number of hybrid vertices and consistent with T, if there is any, in time O(|T| k+1 n⌊4k/3⌋+1). © 2012 Imperial College Press." @Article{HabibTo2012,       AUTHOR = {Habib, Michel and To, Thu-Hien},       TITLE = {Constructing a Minimum Phylogenetic Network from a Dense Triplet Set},       YEAR = {2012},       JOURNAL = {JBCB},       VOLUME = {10},       NUMBER = {5},       PAGES = {1250013},       URL = {http://dx.doi.org/10.1142/S0219720012500138},       NOTE = {http://arxiv.org/abs/1103.2266},       KEYWORDS = {explicit network, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction} }