A Converse For the Capacity of the Shotgun Sequencing Channel with Erasures
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914056606056448 |
|---|---|
| author | Ali, Mohammed Ihsan Narayanan, Hrishi Krishnan, Prasad |
| author_facet | Ali, Mohammed Ihsan Narayanan, Hrishi Krishnan, Prasad |
| contents | The shotgun sequencing process involves fragmenting a long DNA sequence (input string) into numerous shorter, unordered, and overlapping segments (referred to as \emph{reads}). The reads are sequenced, and later aligned to reconstruct the original string. Viewing the sequencing process as the read-phase of a DNA storage system, the information-theoretic capacity of noise-free shotgun sequencing has been characterized in literature. Motivated by the base-wise quality scores available in practical sequencers, a recent work considered the \emph{shotgun sequencing channel with erasures}, in which the symbols in the reads are assumed to contain random erasures. Achievable rates for this channel were identified. In the present work, we obtain a converse for this channel. The arguments for the proof involve a careful analysis of a genie-aided decoder, which knows the correct locations of the reads. The converse is not tight in general. However, it meets the achievability result asymptotically in some channel parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21216 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Converse For the Capacity of the Shotgun Sequencing Channel with Erasures Ali, Mohammed Ihsan Narayanan, Hrishi Krishnan, Prasad Information Theory The shotgun sequencing process involves fragmenting a long DNA sequence (input string) into numerous shorter, unordered, and overlapping segments (referred to as \emph{reads}). The reads are sequenced, and later aligned to reconstruct the original string. Viewing the sequencing process as the read-phase of a DNA storage system, the information-theoretic capacity of noise-free shotgun sequencing has been characterized in literature. Motivated by the base-wise quality scores available in practical sequencers, a recent work considered the \emph{shotgun sequencing channel with erasures}, in which the symbols in the reads are assumed to contain random erasures. Achievable rates for this channel were identified. In the present work, we obtain a converse for this channel. The arguments for the proof involve a careful analysis of a genie-aided decoder, which knows the correct locations of the reads. The converse is not tight in general. However, it meets the achievability result asymptotically in some channel parameters. |
| title | A Converse For the Capacity of the Shotgun Sequencing Channel with Erasures |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.21216 |