Finding Maximum Common Contractions Between Phylogenetic Networks
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_ | 1866929720604491776 |
|---|---|
| author | Marchand, Bertrand Tahiri, Nadia Tremblay-Savard, Olivier Lafond, Manuel |
| author_facet | Marchand, Bertrand Tahiri, Nadia Tremblay-Savard, Olivier Lafond, Manuel |
| contents | In this paper, we lay the groundwork on the comparison of phylogenetic networks based on edge contractions and expansions as edit operations, as originally proposed by Robinson and Foulds to compare trees. We prove that these operations connect the space of all phylogenetic networks on the same set of leaves, even if we forbid contractions that create cycles. This allows to define an operational distance on this space, as the minimum number of contractions and expansions required to transform one network into another. We highlight the difference between this distance and the computation of the maximum common contraction between two networks. Given its ability to outline a common structure between them, which can provide valuable biological insights, we study the algorithmic aspects of the latter. We first prove that computing a maximum common contraction between two networks is NP-hard, even when the maximum degree, the size of the common contraction, or the number of leaves is bounded. We also provide lower bounds to the problem based on the Exponential-Time Hypothesis. Nonetheless, we do provide a polynomial-time algorithm for weakly-galled trees, a generalization of galled trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16713 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding Maximum Common Contractions Between Phylogenetic Networks Marchand, Bertrand Tahiri, Nadia Tremblay-Savard, Olivier Lafond, Manuel Data Structures and Algorithms Computational Complexity In this paper, we lay the groundwork on the comparison of phylogenetic networks based on edge contractions and expansions as edit operations, as originally proposed by Robinson and Foulds to compare trees. We prove that these operations connect the space of all phylogenetic networks on the same set of leaves, even if we forbid contractions that create cycles. This allows to define an operational distance on this space, as the minimum number of contractions and expansions required to transform one network into another. We highlight the difference between this distance and the computation of the maximum common contraction between two networks. Given its ability to outline a common structure between them, which can provide valuable biological insights, we study the algorithmic aspects of the latter. We first prove that computing a maximum common contraction between two networks is NP-hard, even when the maximum degree, the size of the common contraction, or the number of leaves is bounded. We also provide lower bounds to the problem based on the Exponential-Time Hypothesis. Nonetheless, we do provide a polynomial-time algorithm for weakly-galled trees, a generalization of galled trees. |
| title | Finding Maximum Common Contractions Between Phylogenetic Networks |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2405.16713 |