๐Ÿ“–
Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
Thu-Hien To, Michel Habib

Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time

Author / Organization:
Science & Mathematics Published 2009 Verification Pending

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → 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 »