Trace reconstruction of polymer sequences using quality scores
Polymeric molecules such as deoxyribose nucleic acid (DNA) provide a storage medium for digital data that has advantages over conventional storage media. Accessing digital data stored in polymers includes decoding the output of sequencers which detect the physical order of monomer subunits in the polymers. This output includes errors which are corrected through the process of trace reconstruction. Trace reconstruction identifies a consensus output sequence from a set of noisy output reads provided by a sequencer. The accuracy of trace reconstruction is improved by using weighted majority voting to determine the consensus output sequence. Weights are based on quality labels assigned by the sequencer to its output. Quality labels may be derived from empirical error data. A quality label for a single position in an output read may be determined independently or it may be influenced by quality labels of other nearby positions in the read.
1 . A method of storing a digital file, the method comprising:
chemically synthesizing a pool of oligonucleotides having a sequence of nucleotide bases that encode original digital data which is the digital file;
sequencing the pool of oligonucleotides with a nanopore sequencer;
receiving an output file generated by the nanopore sequencer, the output file comprising a plurality of oligonucleotide reads and associated quality labels for individual base calls in the plurality of oligonucleotide reads, wherein the output file contains errors introduced by the nanopore sequencer;
assigning error probabilities to the associated quality labels based on empirical error data obtained from nanopore sequencing of a set of multiple test oligonucleotides with known sequences;
clustering a subset of the plurality of oligonucleotide reads to create a cluster of oligonucleotide reads representing a same nucleotide;
determining that the cluster of reads includes between three and eight oligonucleotide reads and determining a consensus output sequence for the cluster of oligonucleotides by weighted majority voting;
aligning the cluster of oligonucleotides reads at a position of comparison;
determining a consensus output sequence for the cluster of oligonucleotides reads by weighted majority voting of base calls in the oligonucleotides reads at the position of comparison;
determining that an other cluster of reads includes less than three or more than ten oligonucleotides reads and determining the consensus output sequence for the other cluster of oligonucleotides reads by majority voting without error probability weighting; and
converting the consensus output sequence into decoded digital data, wherein the decoded digital data is identical to the original digital data and encodes the digital file.
2 . The method of claim 1 , wherein the error probabilities are based on sums of deletion probabilities, insertion probabilities, and substitution probabilities.
3 . The method of claim 1 , wherein a base call in the cluster of oligonucleotide reads is weighted based on an average of an error probability assigned to a quality label associated with the base call and the error probabilities assigned to quality labels associated with at least two adjacent base calls.
4 . The method of claim 1 , wherein:
a weight used for base calls associated with a lowest quality label or a second lowest quality label is zero; and
a weight used for base calls associated with any of a top half of the associated quality labels is based on a lowest error probability of any quality label for the lowest quality half of the quality labels.
5 . The method of claim 1 , wherein a base call s in the cluster of polynucleotide reads is weighted by log((1−P S )/P S ), wherein P s is the error probability assigned to a quality label associated with the base call s.
6 . A method of recovering a digital file stored in a polymer pool, the method comprising:
sequencing the polymer pool with a sequencer, a sequence of monomers in the polymer pool encoding original digital data which is the digital file;
assigning error probabilities to quality labels;
receiving a cluster of reads with associated quality labels for read symbols in the reads, the cluster comprising reads representing a same polymer, wherein the reads contain errors introduced by a machine that performs the sequencing;
determining a number of reads in the cluster;
if the cluster of reads includes at least a first threshold number of oligonucleotide reads and no more than a second threshold number of oligonucleotide reads, determining a consensus output sequence for the cluster of reads by weighted majority voting of the read symbols with weights based on the error probabilities;
if the cluster of reads includes more than the second threshold number of reads, determining the consensus output sequence for the cluster of reads by majority voting without error probability weighting; and
converting the consensus output sequence into decoded digital data, wherein the decoded digital data is identical to the original digital data and encodes the digital file.
7 . The method of claim 6 , further comprising deriving the error probabilities for the quality labels based on empirical error data obtained from sequencing a set of multiple test polymers with known sequences.
8 . The method of claim 6 , further comprising aligning the reads in the cluster of reads at a position of comparison spanning the reads, wherein the weighted majority voting is performed at the position of comparison and identifies a consensus output read symbol for the position of comparison.
9 . The method of claim 6 , further comprising, excluding a low-reliability read from the cluster of reads based on an overall reliability of the low-reliability read, wherein a low-reliability read has overall reliability below a cutoff threshold or is a read with the lowest overall reliability in the cluster of reads.
10 . The method of claim 6 , wherein a read symbol of the read symbols is weighted based on error probabilities of adjacent read symbols in a window including the read symbol.
11 . The method of claim 6 , wherein a read symbol s in the reads is weighted by log((1−P S )/P S ), wherein P s is the error probability assigned to a quality label associated with the read symbol s.
12 . The method of claim 6 , further comprising chemically synthesizing the polymer pool with the sequence of monomers that encode the digital file.
13 . A system for storing a digital file in a polymer pool, the system comprising:
one or more processing units;
a memory coupled to the one or more processing units;
an error probability module stored in the memory and implemented on the one or more processing units to:
assign error probabilities to quality labels provided by a sequencer; and
a consensus output sequence generator stored in the memory and implemented on the one or more processing units to:
receive a cluster of reads and associated quality labels for read symbols in the reads, the cluster comprising reads representing a polymer strand, wherein errors in the reads are introduced by the sequencer and a sequence of monomers in the reads encode original digital data which is the digital file;
determine a number of reads in the cluster;
if the cluster of reads includes at least a first threshold number of reads and no more than a second threshold number of reads, determine a consensus output sequence for the cluster of reads based on weighted majority voting of the read symbols weighted by the error probabilities; and
if the cluster of reads includes more than the second threshold number of reads, determining the consensus output sequence for the cluster of reads by majority voting without error probability weighting; and
a conversion module stored in the memory and implemented on the one or more processing units to convert the consensus output sequence into decoded digital data, wherein the decoded digital data is identical to the original digital data and encodes the digital file.
14 . The system of claim 13 , wherein the error probability module is further implemented on the one or more processing units to derive the error probabilities for the quality labels based on empirical error data obtained from sequencing a set of multiple test polymers with known sequences.
15 . The system of claim 13 , further comprising a clustering module stored in the memory and implemented on the one or more processing units to cluster a plurality of reads based on a likelihood of the reads being derived from a same polymer thereby creating the cluster of reads.
16 . The system of claim 13 , further comprising a read alignment module stored in the memory and implemented on the one or more processing units to align the reads in the cluster of reads at a position of comparison spanning the reads, wherein the consensus output sequence generator performs the weighted majority voting at the position of comparison and identifies a consensus output read symbol for the position of comparison.
17 . The system of claim 13 , wherein the consensus output sequence generator is further implemented on the one or more processing units to exclude a low-reliability read from the cluster of reads based on an overall reliability of the low-reliability read, wherein a low-reliability read has overall reliability below a cutoff threshold or is a read with the lowest overall reliability in the cluster.
18 . The system of claim 13 , wherein the error probability module is further implemented on the one or more processing units to determine an error probability for a read symbol based on error probabilities of adjacent read symbols in a window including the read symbol.
19 . The system of claim 13 , wherein a read symbol of the read symbols is weighted by log((1−P S )/P S ), wherein P s is the error probability assigned to the quality label associated with the read symbol.
20 . The system of claim 13 , further comprising a synthesizer configured to synthesize the polymer pool according to instructions specifying the sequence of monomers that encode original digital data.