Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.18281 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911074653044736 |
|---|---|
| author | Bonizzoni, Paola Della Vedova, Gianluca Gomez, Mauricio Soto Trucco, Gabriella |
| author_facet | Bonizzoni, Paola Della Vedova, Gianluca Gomez, Mauricio Soto Trucco, Gabriella |
| contents | The Persistent Perfect phylogeny, also known as Dollo-1, has been introduced as a generalization of the well-known perfect phylogenetic model for binary characters to deal with the potential loss of characters. The problem of deciding the existence of a Persistent Perfect phylogeny can be reduced to the one of recognizing a class of bipartite graphs whose nodes are species and characters. Thus an interesting question is solving directly the problem of recognizing such graphs. We present a polynomial-time algorithm for deciding Persistent Perfect phylogeny existence in maximal graphs, where no character's species set is contained within another character's species set. Our solution, that relies only on graph properties, narrows the gap between the linear-time simple algorithm for Perfect Phylogeny and the NP-hardness results for the Dollo-$k$ phylogeny with $k>1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_18281 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On recognizing graphs representing Persistent Perfect Phylogenies Bonizzoni, Paola Della Vedova, Gianluca Gomez, Mauricio Soto Trucco, Gabriella Data Structures and Algorithms The Persistent Perfect phylogeny, also known as Dollo-1, has been introduced as a generalization of the well-known perfect phylogenetic model for binary characters to deal with the potential loss of characters. The problem of deciding the existence of a Persistent Perfect phylogeny can be reduced to the one of recognizing a class of bipartite graphs whose nodes are species and characters. Thus an interesting question is solving directly the problem of recognizing such graphs. We present a polynomial-time algorithm for deciding Persistent Perfect phylogeny existence in maximal graphs, where no character's species set is contained within another character's species set. Our solution, that relies only on graph properties, narrows the gap between the linear-time simple algorithm for Perfect Phylogeny and the NP-hardness results for the Dollo-$k$ phylogeny with $k>1$. |
| title | On recognizing graphs representing Persistent Perfect Phylogenies |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.18281 |