Phase transition in the computational complexity of the shortest common superstring and genome assembly
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913259110531072 |
|---|---|
| author | Fernandez, L. A. Martin-Mayor, V. Yllanes, D. |
| author_facet | Fernandez, L. A. Martin-Mayor, V. Yllanes, D. |
| contents | Genome assembly, the process of reconstructing a long genetic sequence by aligning and merging short fragments, or reads, is known to be NP-hard, either as a version of the shortest common superstring problem or in a Hamiltonian-cycle formulation. That is, the computing time is believed to grow exponentially with the the problem size in the worst case. Despite this fact, high-throughput technologies and modern algorithms currently allow bioinformaticians to handle datasets of billions of reads. Using methods from statistical mechanics, we address this conundrum by demonstrating the existence of a phase transition in the computational complexity of the problem and showing that practical instances always fall in the 'easy' phase (solvable by polynomial-time algorithms). In addition, we propose a Markov-chain Monte Carlo method that outperforms common deterministic algorithms in the hard regime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_09986 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Phase transition in the computational complexity of the shortest common superstring and genome assembly Fernandez, L. A. Martin-Mayor, V. Yllanes, D. Statistical Mechanics Computational Complexity Biological Physics Genomics Genome assembly, the process of reconstructing a long genetic sequence by aligning and merging short fragments, or reads, is known to be NP-hard, either as a version of the shortest common superstring problem or in a Hamiltonian-cycle formulation. That is, the computing time is believed to grow exponentially with the the problem size in the worst case. Despite this fact, high-throughput technologies and modern algorithms currently allow bioinformaticians to handle datasets of billions of reads. Using methods from statistical mechanics, we address this conundrum by demonstrating the existence of a phase transition in the computational complexity of the problem and showing that practical instances always fall in the 'easy' phase (solvable by polynomial-time algorithms). In addition, we propose a Markov-chain Monte Carlo method that outperforms common deterministic algorithms in the hard regime. |
| title | Phase transition in the computational complexity of the shortest common superstring and genome assembly |
| topic | Statistical Mechanics Computational Complexity Biological Physics Genomics |
| url | https://arxiv.org/abs/2210.09986 |