A Converse For the Capacity of the Shotgun Sequencing Channel with Erasures
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |