Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
Overview & Synopsis
Given a dense triplet set $\mathcal{T}$, there arise two interesting questions: Does there exists any phylogenetic network consistent with $\mathcal{T}$? And if so, can we find an effective algorithm to construct one? For cases of networks of levels $k=0$ or $1$ or $2$, these questions were answered with effective polynomial algorithms. For higher levels $k$, partial answers were recently obtained with an $O(|\mathcal{T}|^{k+1})$ time algorithm for simple networks. In this paper we give a complete answer to the general case. The main idea is to use a special property of SN-sets in a level-k network. As a consequence, we can also find the level-k network with the minimum number of reticulations in polynomial time.
hal.science)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time |
|---|---|
| Author / Organization | Thu-Hien To, Michel Habib |
| Subject & Discipline | Multidisciplinary Academic Open Research |
| Categories | Science & Mathematics |
| Publication Year | 2009 |
| License / Rights | Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
HAL Open Science
(hal.science)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-229327 |
| Original Source Link | Visit Source Page on hal.science » |