Complexity and Enumeration in Models of Genome Rearrangement
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912047422242816 |
|---|---|
| author | Bailey, Lora Blake, Heather Smith Cochran, Garner Fox, Nathan Levet, Michael Mahmoud, Reem Matson, Elizabeth Singgih, Inne Stadnyk, Grace Wang, Xinyi Wiedemann, Alexander |
| author_facet | Bailey, Lora Blake, Heather Smith Cochran, Garner Fox, Nathan Levet, Michael Mahmoud, Reem Matson, Elizabeth Singgih, Inne Stadnyk, Grace Wang, Xinyi Wiedemann, Alexander |
| contents | In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the Pairwise Rearrangement problem in the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010) is $\#\textsf{P}$-complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model (Feijao & Meidanis, IEEE ACM Trans. Comp. Biol. Bioinf. 2011), the problem of enumerating all medians ($\#$Median) is logspace-computable ($\textsf{FL}$), improving upon the previous polynomial-time ($\textsf{FP}$) bound of Miklós & Smith (RECOMB 2015). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_01851 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Complexity and Enumeration in Models of Genome Rearrangement Bailey, Lora Blake, Heather Smith Cochran, Garner Fox, Nathan Levet, Michael Mahmoud, Reem Matson, Elizabeth Singgih, Inne Stadnyk, Grace Wang, Xinyi Wiedemann, Alexander Genomics Computational Complexity Combinatorics 92-08, 92D10, 92D20, 68Q17 F.2.2 In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the Pairwise Rearrangement problem in the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010) is $\#\textsf{P}$-complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model (Feijao & Meidanis, IEEE ACM Trans. Comp. Biol. Bioinf. 2011), the problem of enumerating all medians ($\#$Median) is logspace-computable ($\textsf{FL}$), improving upon the previous polynomial-time ($\textsf{FP}$) bound of Miklós & Smith (RECOMB 2015). |
| title | Complexity and Enumeration in Models of Genome Rearrangement |
| topic | Genomics Computational Complexity Combinatorics 92-08, 92D10, 92D20, 68Q17 F.2.2 |
| url | https://arxiv.org/abs/2305.01851 |