Trace reconstruction from reads with indeterminant errors
Polynucleotide sequencing generates multiple reads of a polynucleotide molecule. Many or all of the reads contain errors. Trace reconstruction takes multiple reads generated by a polynucleotide sequencer and uses those multiple reads to reconstruct accurately the nucleotide sequence of the polynucleotide molecule. Some reads may contain errors that cannot be corrected. Thus, there may be reads that can be used throughout their entire length and other reads that have indeterminant errors which cannot be corrected. Rather than discarding the entire read when an indeterminant error is found, the portion of the read with the error is skipped and the sequence of the read following the error is used to reconstruct the trace. The amount of the read skipped is determined by the location of subsequence after the error that matches a consensus sequence of the other reads. Analysis resumes at a location determined by the location of the match.
1 . A method of recovering stored digital data comprising:
sequencing a deoxyribose nucleic acid (DNA) strand with a sequencing technology, wherein the DNA strand stores digital data thereby generating a plurality of reads;
generating a consensus output sequence from the plurality of reads of the DNA strand, the plurality of reads generated with less than 30× coverage by the sequencing technology that introduces a bursty error that includes multiple adjacent errors into a read of the plurality of reads by:
identifying a start of a portion of the read that contains the bursty error by identifying a position in the read that does not match a consensus sequence and cannot be classified as an insertion, a deletion, or a substitution after attempting such classification;
identifying an end of the portion of the read that contains the bursty error by identifying a position in the read that is flanked by a match-backwards region that matches a consensus sequence generated from the plurality of reads;
omitting only the portion of the read that contains the bursty error from generation of the consensus output sequence;
generating the consensus output sequence with portions of the read from either side of the portion of the read that contains the bursty error; and
converting the consensus output sequence into the digital data.
2 . The method of claim 1 , wherein the sequencing technology is Nanopore sequencing.
3 . The method of claim 1 , wherein the plurality of reads are generated with less than 25× coverage.
4 . The method of claim 1 , wherein the consensus output sequence is generated by comparing values for the plurality of reads at a position of comparison while aligning the plurality of reads with respect to each other based on insertions, deletions, and substitutions.
5 . The method of claim 4 , wherein comparing values for the plurality of reads comprises determining a plurality consensus base.
6 . The method of claim 1 , further comprising identifying an end of the portion of the read that contains the bursty error by identifying a position in the read that is flanked by a match-forwards region that matches a sequence generated by plurality voting from sequences of at least two other reads of the plurality of reads.
7 . A system for recovering stored digital data comprising:
a polynucleotide sequencer implementing a sequencing technology and configured to sequence a deoxyribose nucleic acid (DNA) strand to generate a plurality of reads, wherein the DNA strand stores digital data;
one or more processing units;
a memory coupled to the one or more processing units;
a sequence data interface configured to receive the plurality of reads of the DNA strand that were generated with less than 30× coverage by the sequencing technology that introduces a bursty error that includes multiple adjacent errors into a read of the plurality of reads;
a consensus output sequence generator stored in the memory and implemented by the one or more processing units to:
identify a start of a portion of the read that contains the bursty error by identifying a position in the read that does not match a consensus sequence and cannot be classified as an insertion, a deletion, or a substitution after attempting such classification;
identify an end of the portion of the read that contains the bursty error by identifying a position in the read that is flanked by a match-backwards region that matches a consensus sequence;
omit only the portion of the read that contains the bursty error from generation of a consensus output sequence; and
generate the consensus output sequence with portions of the read from either side of the portion of the read that contains the bursty error; and
a conversion module configured to convert the consensus output sequence into digital data.
8 . The system of claim 7 , wherein the sequencing technology of the polynucleotide sequencer is Nanopore sequencing.
9 . The system of claim 7 , wherein the plurality of reads are generated with less than 25× coverage.
10 . The system of claim 7 , wherein the consensus output sequence generator is further configured to generate the consensus output sequence by comparing values for the plurality of reads at a position of comparison while aligning the plurality of reads with respect to each other based on insertions, deletions, and substitutions.
11 . The system of claim 10 , wherein comparing values for the plurality of reads comprises determining a plurality consensus base.
12 . The system of claim 7 , wherein the consensus output sequence generator is further configured to identify an end of the portion of the read that contains the bursty error by identifying a position in the read that is flanked by a match-forwards region that matches a sequence generated by plurality voting from sequences of at least two other reads of the plurality of reads.
13 . A system comprising:
means for sequencing a deoxyribose nucleic acid (DNA) strand to generate a plurality of reads, wherein the DNA strand stores digital data;
one or more processing units;
a memory coupled to the one or more processing units, the memory storing instructions that, when executed by the one or more processing units, cause the system to perform acts comprising:
receiving the plurality of reads of the DNA strand that were generated with less than 30× coverage by the means for sequencing that introduces a bursty error that includes multiple adjacent errors into a read of the plurality of reads;
identifying a start of a portion of the read that contains the bursty error by identifying a position in the read that does not match a consensus sequence and is not classified as an insertion, a deletion, or a substitution;
identifying an end of the portion of the read that contains the bursty error by identifying a position in the read that is flanked by a match-backwards region that matches a consensus sequence generated from the plurality of reads;
omitting only the portion of the read that contains the bursty error from generation of a consensus output sequence;
generating the consensus output sequence with portions of the read from either side of the portion of the read that contains the bursty error; and
converting the consensus output sequence into digital data.
14 . The system of claim 13 , wherein the acts further comprise identifying an end of the portion of the read that contains the bursty error by identifying a position in the read that is flanked by a match-forwards region that matches a sequence generated by plurality voting from sequences of at least two other reads of the plurality of reads.
15 . The system of claim 13 , wherein the means for sequencing is a Nanopore sequencer.
16 . The system of claim 13 , wherein the plurality of reads are generated with less than 25× coverage.
17 . The system of claim 13 , wherein the consensus output sequence is generated by comparing values for the plurality of reads at a position of comparison while aligning the plurality of reads with respect to each other based on insertions, deletions, and substitutions.
18 . The system of claim 17 , wherein comparing values for the plurality of reads comprises determining a plurality consensus base.