Constructing a Minimum-Level Phylogenetic Network from a Dense Triplet Set in Polynomial Time

摘要

For a given set $\mathcal{L}$ of species and a set $\mathcal{T}$ of tripletson $\mathcal{L}$, one wants to construct a phylogenetic network which isconsistent with $\mathcal{T}$, i.e which represents all triplets of$\mathcal{T}$. The level of a network is defined as the maximum number ofhybrid vertices in its biconnected components. When $\mathcal{T}$ is dense,there exist polynomial time algorithms to construct level-$0,1,2$ networks (Ahoet al. 81, Jansson et al. 04, Iersel et al. 08). For higher levels, partialanswers were obtained by Iersel et al. 2008 with a polynomial time algorithmfor simple networks. In this paper, we detail the first complete answer for thegeneral case, solving a problem proposed by Jansson et al. 2004: for any $k$fixed, it is possible to construct a minimum level-$k$ network consistent with$\mathcal{T}$, if there is any, in time$O(|\mathcal{T}|^{k+1}n^{\lfloor\frac{4k}{3}\rfloor+1})$. This is an improvedresult of our preliminary version presented at CPM'2009.