TY - GEN
T1 - Capacity of the Shotgun Sequencing Channel
AU - Ravi, Aditya Narayan
AU - Vahid, Alireza
AU - Shomorony, Ilan
N1 - ACKNOWLEDGEMENTS The work of Aditya Narayan Ravi and Ilan Shomorony was supported in part by the NSF Grant CCF-2007597 and in part by the NSF CAREER Award under Grant CCF-2046991. The work of A. Vahid was in part supported by NSF grants ECCS-2030285 and CNS-2106692.
PY - 2022
Y1 - 2022
N2 - Most DNA sequencing technologies are based on the shotgun paradigm: many short reads are obtained from random unknown locations in the DNA sequence. A fundamental question, studied in [1], is what read length and coverage depth (i.e., the total number of reads) are needed to guarantee reliable sequence reconstruction. Motivated by DNA-based storage, we study the coded version of this problem; i.e., the scenario in which the DNA molecule being sequenced is a codeword from a predefined codebook. Our main result is an exact characterization of the capacity of the resulting shotgun sequencing channel as a function of the read length and coverage depth. In particular, our results imply that while in the uncoded case, O(n) reads of length greater than 2logn are needed for reliable reconstruction of a length-n binary sequence, in the coded case, only O(n/log n) reads of length greater than log n are needed for the capacity to be arbitrarily close to 1.
AB - Most DNA sequencing technologies are based on the shotgun paradigm: many short reads are obtained from random unknown locations in the DNA sequence. A fundamental question, studied in [1], is what read length and coverage depth (i.e., the total number of reads) are needed to guarantee reliable sequence reconstruction. Motivated by DNA-based storage, we study the coded version of this problem; i.e., the scenario in which the DNA molecule being sequenced is a codeword from a predefined codebook. Our main result is an exact characterization of the capacity of the resulting shotgun sequencing channel as a function of the read length and coverage depth. In particular, our results imply that while in the uncoded case, O(n) reads of length greater than 2logn are needed for reliable reconstruction of a length-n binary sequence, in the coded case, only O(n/log n) reads of length greater than log n are needed for the capacity to be arbitrarily close to 1.
KW - DNA shotgun sequencing
KW - DNA-based storage
KW - channel capacity
UR - https://www.scopus.com/pages/publications/85136279709
UR - https://www.scopus.com/pages/publications/85136279709#tab=citedBy
U2 - 10.1109/ISIT50566.2022.9834409
DO - 10.1109/ISIT50566.2022.9834409
M3 - Conference contribution
AN - SCOPUS:85136279709
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 210
EP - 215
BT - 2022 IEEE International Symposium on Information Theory, ISIT 2022
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2022 IEEE International Symposium on Information Theory, ISIT 2022
Y2 - 26 June 2022 through 1 July 2022
ER -