WE1.R6.3

On Achievable Rates for the Shotgun Sequencing Channel with Erasures

Hrishi Narayanan, Prasad Krishnan, Nita Parekh, International Institute of Information Technology, Hyderabad (IIIT-H), India

Session:
Coding in Biology 3

Track:
17: Information and Coding in Biology

Location:
Sigma/Delta

Presentation Time:
Wed, 10 Jul, 10:30 - 10:50

Session Chair:
Emanuele Viterbo, Monash University
Abstract
In shotgun sequencing, the input string (typically, a long DNA sequence composed of nucleotide bases) is sequenced as multiple overlapping fragments of much shorter lengths (called reads). Modelling the shotgun sequencing pipeline as a communication channel for DNA data storage, the capacity of this channel was identified in a recent work, assuming that the reads themselves are noiseless substrings of the original sequence. Modern shotgun sequencers however also output quality scores for each base read, indicating the confidence in its identification. Bases with low quality scores can be considered to be erased. Motivated by this, we consider the shotgun sequencing channel with erasures, where each symbol in any read can be independently erased with some probability delta. We identify achievable rates for this channel, using a random code construction and a decoder that uses typicality-like arguments to merge the reads.
Resources