A Wild Sheep Chase Through an Orchard
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910615614783488 |
|---|---|
| author | Dempsey, Jordan van Iersel, Leo Jones, Mark Murakami, Yukihiro Zeh, Norbert |
| author_facet | Dempsey, Jordan van Iersel, Leo Jones, Mark Murakami, Yukihiro Zeh, Norbert |
| contents | Orchards are a biologically relevant class of phylogenetic networks as they can describe treelike evolutionary histories augmented with horizontal transfer events. Moreover, the class has attractive mathematical characterizations that can be exploited algorithmically. On the other hand, undirected orchard networks have hardly been studied yet. Here, we prove that deciding whether an undirected, binary phylogenetic network is an orchard -- or equivalently, whether it has an orientation that makes it a rooted orchard -- is NP-hard. For this, we introduce a new characterization of undirected orchards which could be useful for proving positive results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10769 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Wild Sheep Chase Through an Orchard Dempsey, Jordan van Iersel, Leo Jones, Mark Murakami, Yukihiro Zeh, Norbert Populations and Evolution Computational Complexity Combinatorics Orchards are a biologically relevant class of phylogenetic networks as they can describe treelike evolutionary histories augmented with horizontal transfer events. Moreover, the class has attractive mathematical characterizations that can be exploited algorithmically. On the other hand, undirected orchard networks have hardly been studied yet. Here, we prove that deciding whether an undirected, binary phylogenetic network is an orchard -- or equivalently, whether it has an orientation that makes it a rooted orchard -- is NP-hard. For this, we introduce a new characterization of undirected orchards which could be useful for proving positive results. |
| title | A Wild Sheep Chase Through an Orchard |
| topic | Populations and Evolution Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2408.10769 |