  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%.
