TY - GEN

T1 - Sequence assembly from corrupted shotgun reads

AU - Ganguly, Shirshendu

AU - Mossel, Elchanan

AU - Racz, Miklos Z.

N1 - Funding Information:
The research of E.M. is supported by NSF grant CCF-1320105, DOD ONR grant N00014-14-1-0823, and Simons Foundation grant 328025. M.Z.R. thanks Jasmine Nirody and Rachel Wang for helpful discussions
Publisher Copyright:
© 2016 IEEE.

PY - 2016/8/10

Y1 - 2016/8/10

N2 - The prevalent technique for DNA sequencing consists of two main steps: shotgun sequencing, where many randomly located fragments, called reads, are extracted from the overall sequence, followed by an assembly algorithm that aims to reconstruct the original sequence. There are many different technologies that generate the reads: widely-used second-generation methods create short reads with low error rates, while emerging third-generation methods create long reads with high error rates. Both error rates and error profiles differ among methods, so reconstruction algorithms are often tailored to specific shotgun sequencing technologies. As these methods change over time, a fundamental question is whether there exist reconstruction algorithms which are robust, i.e., which perform well under a wide range of error distributions. Here we study this question of sequence assembly from corrupted reads. We make no assumption on the types of errors in the reads, but only assume a bound on their magnitude. More precisely, for each read we assume that instead of receiving the true read with no errors, we receive a corrupted read which has edit distance at most ϵ times the length of the read from the true read. We show that if the reads are long enough and there are sufficiently many of them, then approximate reconstruction is possible: we construct a simple algorithm such that for almost all original sequences the output of the algorithm is a sequence whose edit distance from the original one is at most O(ϵ) times the length of the original sequence.

AB - The prevalent technique for DNA sequencing consists of two main steps: shotgun sequencing, where many randomly located fragments, called reads, are extracted from the overall sequence, followed by an assembly algorithm that aims to reconstruct the original sequence. There are many different technologies that generate the reads: widely-used second-generation methods create short reads with low error rates, while emerging third-generation methods create long reads with high error rates. Both error rates and error profiles differ among methods, so reconstruction algorithms are often tailored to specific shotgun sequencing technologies. As these methods change over time, a fundamental question is whether there exist reconstruction algorithms which are robust, i.e., which perform well under a wide range of error distributions. Here we study this question of sequence assembly from corrupted reads. We make no assumption on the types of errors in the reads, but only assume a bound on their magnitude. More precisely, for each read we assume that instead of receiving the true read with no errors, we receive a corrupted read which has edit distance at most ϵ times the length of the read from the true read. We show that if the reads are long enough and there are sufficiently many of them, then approximate reconstruction is possible: we construct a simple algorithm such that for almost all original sequences the output of the algorithm is a sequence whose edit distance from the original one is at most O(ϵ) times the length of the original sequence.

UR - http://www.scopus.com/inward/record.url?scp=84985995304&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84985995304&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541302

DO - 10.1109/ISIT.2016.7541302

M3 - Conference contribution

AN - SCOPUS:84985995304

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 265

EP - 269

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -