Structural properties of distance-bounded phylogenetic reconciliation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912861195862016 |
|---|---|
| author | Antony, Cyriac Martino, Alessio Sinaimeri, Blerina |
| author_facet | Antony, Cyriac Martino, Alessio Sinaimeri, Blerina |
| contents | Phylogenetic reconciliation seeks to explain host-symbiont co-evolution by mapping parasite trees onto host trees through events such as cospeciation, duplication, host switching, and loss. Finding an optimal reconciliation that ensures time feasibility is computationally hard when timing information is incomplete, and the complexity remains open when host switches are restricted by a fixed maximum distance $d$. While the case $d=2$ is known to be polynomial, larger values are unresolved. In this paper, we study the cases $d=3$ and $d=4$. We show that although arbitrarily large cycles may occur, it suffices to check only bounded-size cycles (we provide a complete list), provided the reconciliation satisfies acyclicity (i.e., time-feasibility) in a stronger sense. These results do not resolve the general complexity, but highlight structural properties that advance the understanding of distance-bounded reconciliations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22193 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Structural properties of distance-bounded phylogenetic reconciliation Antony, Cyriac Martino, Alessio Sinaimeri, Blerina Populations and Evolution Phylogenetic reconciliation seeks to explain host-symbiont co-evolution by mapping parasite trees onto host trees through events such as cospeciation, duplication, host switching, and loss. Finding an optimal reconciliation that ensures time feasibility is computationally hard when timing information is incomplete, and the complexity remains open when host switches are restricted by a fixed maximum distance $d$. While the case $d=2$ is known to be polynomial, larger values are unresolved. In this paper, we study the cases $d=3$ and $d=4$. We show that although arbitrarily large cycles may occur, it suffices to check only bounded-size cycles (we provide a complete list), provided the reconciliation satisfies acyclicity (i.e., time-feasibility) in a stronger sense. These results do not resolve the general complexity, but highlight structural properties that advance the understanding of distance-bounded reconciliations. |
| title | Structural properties of distance-bounded phylogenetic reconciliation |
| topic | Populations and Evolution |
| url | https://arxiv.org/abs/2601.22193 |