title: Constructing a minimum phylogenetic network from a dense triplet set.
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)).
authors: Université Paris Diderot-Paris 7, LIAFA, Case 7014, 75205 Paris Cedex 13, France. michel.habib@liafa.jussieu.fr
authors: Michel
authors: M
authors: Habib
authors: Thu-Hien
authors: TH
authors: To
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D019143:Evolution, Molecular; D053263:Gene Regulatory Networks; D010802:Phylogeny