Optimal DNA shotgun sequencing: Noisy reads are as good as noiseless reads

作者：Motahari, Abolfazl; Ramchandran, Kannan; Tse, David; Ma, Nan

来源：2013 IEEE International Symposium on Information Theory, ISIT 2013, Turkey, 2013-07-07 To 2013-07-12.

DOI：10.1109/ISIT.2013.6620505

• DNA model
• Noise levels
• Read channels

We establish the fundamental limits of DNA shotgun sequencing under noisy reads. We show a surprising result: for the i.i.d. DNA model, noisy reads are as good as noiseless reads, provided that the noise level is below a certain threshold which can be surprisingly high. As an example, for a uniformly distributed DNA sequence and a symmetric substitution noisy read channel, the threshold is as high as 19%.