Locating a Tree in a Phylogenetic Network in Quadratic Time

Philippe Gambette 1 Andreas D.M. Gunawan 2 Anthony Labarre 1 Stéphane Vialette 1 Louxin Zhang 2
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Mathematics [Singapore]
Abstract : A fundamental problem in the study of phylogenetic networks is to determine whether or not a given phylogenetic network contains a given phylogenetic tree. We develop a quadratic-time algorithm for this problem for binary nearly-stable phylogenetic networks. We also show that the number of reticulations in a reticulation visible or nearly stable phylogenetic network is bounded from above by a function linear in the number of taxa.
Keywords : tree containment reticulation visible networks nearly-stable phylogenetic networks phylogenetic networks
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-01116231
Contributor : Philippe Gambette <>
Submitted on : Friday, February 13, 2015 - 10:20:07 AM
Last modification on : Thursday, July 5, 2018 - 2:46:01 PM
Long-term archiving on : Thursday, May 28, 2015 - 11:56:51 AM

File

2015GambetteGunawanLabarreVial...
Files produced by the author(s)

Licence

Copyright

Identifiers

Collections

UPEC-UPEM | LIGM_MOA | LIGM | ENPC | PARISTECH | ESIEE-PARIS

Citation

Philippe Gambette, Andreas D.M. Gunawan, Anthony Labarre, Stéphane Vialette, Louxin Zhang. Locating a Tree in a Phylogenetic Network in Quadratic Time. RECOMB 2015, Apr 2015, Varsovie, Poland. pp.96-107, ⟨10.1007/978-3-319-16706-0_12⟩. ⟨hal-01116231⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

475

Files downloads

253

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD