Reconstructing semi-directed level-1 networks using few quarnets
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_ | 1866918102219882496 |
|---|---|
| author | Frohn, Martin Holtgrefe, Niels van Iersel, Leo Jones, Mark Kelk, Steven |
| author_facet | Frohn, Martin Holtgrefe, Niels van Iersel, Leo Jones, Mark Kelk, Steven |
| contents | Semi-directed networks are partially directed graphs that model evolution where the directed edges represent reticulate evolutionary events. We present an algorithm that reconstructs binary $n$-leaf semi-directed level-1 networks in $O( n^2)$ time from its quarnets (4-leaf subnetworks). Our method assumes we have direct access to all quarnets, yet uses only an asymptotically optimal number of $O(n \log n)$ quarnets. When the network is assumed to contain no triangles, our method instead relies only on four-cycle quarnets and the splits of the other quarnets. A variant of our algorithm works with quartets rather than quarnets and we show that it reconstructs most of a semi-directed level-1 network from an asymptotically optimal $O(n \log n)$ of the quartets it displays. Additionally, we provide an $O(n^3)$ time algorithm that reconstructs the tree-of-blobs of any binary $n$-leaf semi-directed network with unbounded level from $O(n^3)$ splits of its quarnets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06034 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconstructing semi-directed level-1 networks using few quarnets Frohn, Martin Holtgrefe, Niels van Iersel, Leo Jones, Mark Kelk, Steven Populations and Evolution Data Structures and Algorithms Combinatorics Semi-directed networks are partially directed graphs that model evolution where the directed edges represent reticulate evolutionary events. We present an algorithm that reconstructs binary $n$-leaf semi-directed level-1 networks in $O( n^2)$ time from its quarnets (4-leaf subnetworks). Our method assumes we have direct access to all quarnets, yet uses only an asymptotically optimal number of $O(n \log n)$ quarnets. When the network is assumed to contain no triangles, our method instead relies only on four-cycle quarnets and the splits of the other quarnets. A variant of our algorithm works with quartets rather than quarnets and we show that it reconstructs most of a semi-directed level-1 network from an asymptotically optimal $O(n \log n)$ of the quartets it displays. Additionally, we provide an $O(n^3)$ time algorithm that reconstructs the tree-of-blobs of any binary $n$-leaf semi-directed network with unbounded level from $O(n^3)$ splits of its quarnets. |
| title | Reconstructing semi-directed level-1 networks using few quarnets |
| topic | Populations and Evolution Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2409.06034 |