Skip to Main content Skip to Navigation
Conference papers

Scanning Phylogenetic Networks is NP-hard

Abstract : Phylogenetic networks are rooted directed acyclic graphs used to depict the evolution of a set of species in the presence of reticulate events. Reconstructing these networks from molecular data is challenging and current algorithms fail to scale up to genome-wide data. In this paper, we introduce a new width measure intended to help design faster parameterized algorithms for this task. We study its relation with other width measures and problems in graph theory and finally prove that deciding it is NP-complete, even for very restricted classes of networks.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-02353161
Contributor : Celine Scornavacca <>
Submitted on : Thursday, November 7, 2019 - 11:07:31 AM
Last modification on : Friday, April 24, 2020 - 12:08:26 PM
Document(s) archivé(s) le : Saturday, February 8, 2020 - 11:26:07 PM

File

hrl.pdf
Files produced by the author(s)

Identifiers

Citation

Vincent Berry, Celine Scornavacca, Mathias Weller. Scanning Phylogenetic Networks is NP-hard. SOFSEM, Jan 2020, Limassol, Cyprus. pp.519-530, ⟨10.1007/978-3-030-38919-2_42⟩. ⟨hal-02353161⟩

Share

Metrics

Record views

137

Files downloads

238