Methods, Systems, Computer Readable Media, and Kits for Sample Identification

Abstract

A method for sequencing a polynucleotide sample having a barcode sequence includes: introducing a series of nucleotides to the polynucleotide sample according to a predetermined order of nucleotide flows; obtaining a series of signals resulting from the introducing of nucleotides to the polynucleotide sample; and resolving the series of signals over the barcode sequence to render a flowspace string, wherein the flowspace string is a codeword of an error-correcting code that is (i) designed based on and adapted for use with the predetermined order of nucleotide flows, and (ii) capable of distinguishing any codeword in the error-correcting code from the other codewords in the error-correcting code in the presence of zero, one, and two errors.

1 . A method for sequencing a polynucleotide sample having a barcode sequence, comprising:
 introducing a series of nucleotides to the polynucleotide sample according to a predetermined order of nucleotide flows;   obtaining a series of signals resulting from the introducing of nucleotides to the polynucleotide sample; and   resolving the series of signals over the barcode sequence to render a flowspace string, wherein the flowspace string is a codeword of an error-correcting code that is (i) designed based on and adapted for use with the predetermined order of nucleotide flows, and (ii) capable of distinguishing any codeword in the error-correcting code from the other codewords in the error-correcting code in the presence of zero, one, and two errors.   
     
     
         2 . The method of  claim 1 , wherein the error-correcting code is a ternary code and the predetermined flow ordering is a phase-protecting predetermined flow ordering. 
     
     
         3 . The method of  claim 1 , wherein the error-correcting code is a ternary code generated using a generator polynomial associated with a ternary cyclic code. 
     
     
         4 . The method of  claim 3 , wherein the generator polynomial comprises 10210122. 
     
     
         5 . The method of  claim 3 , wherein the generator polynomial comprises 1022201. 
     
     
         6 . The method of  claim 3 , wherein the generator polynomial comprises 1112. 
     
     
         7 . The method of  claim 1 , wherein each codeword of the error-correcting code includes at least one 2-mer and at least one 1-mer. 
     
     
         8 . The method of  claim 1 , wherein the error-correcting code is a quaternary code generated by applying a distance-preserving Gray map to an extended binary Golay code. 
     
     
         9 . The method of  claim 8 , wherein the quaternary code is generated by applying to the extended binary Golay code a Gray map mapping pairs of binary digits 0 and 1 of the extended binary Golay code to one of integers 0, 1, 2, and 3, wherein the Gray map mapping preserves a predetermined minimal distance. 
     
     
         10 . The method of  claim 8 , wherein the error-correcting code is further capable of distinguishing any codeword in the error-correcting code from the other codewords in the error-correcting code in the presence of three errors. 
     
     
         11 . The method of  claim 1 , wherein the error-correcting code is generated using an octacode. 
     
     
         12 . The method of  claim 1 , wherein the error-correcting code is a quaternary code. 
     
     
         13 . The method of  claim 1 , wherein the error-correcting code is further designed by verifying that a predetermined minimal distance between a codeword and other codewords in the error-correcting code using a Lee metric determined in flowspace. 
     
     
         14 . The method of  claim 1 , further comprising translating the flowspace string into a base sequence to obtain the sequence of the barcode sequence. 
     
     
         15 . The method of  claim 1 , further comprising:
 decoding the flowspace string to the correct flowspace codeword; and   translating the flowspace codeword into a base sequence to obtain the sequence of the barcode sequence.   
     
     
         16 . The method of  claim 1 , further comprising providing multiple different polynucleotide samples for multiplex sequencing by the series of flowed nucleotides, each different polynucleotide sample comprising a different barcode sequence that gives a different flowspace string, each different flowspace string being a different codeword of the error-correcting code. 
     
     
         17 . The method of  claim 1 , wherein any two flowspace codewords of the error-correcting code have a Hamming distance of at least 5. 
     
     
         18 . A system, including:
 a machine-readable memory; and   a processor configured to execute machine-readable instructions, which, when executed by the processor, cause the system to perform a method for sequencing a polynucleotide sample having a barcode sequence, comprising:
 introducing a series of nucleotides to the polynucleotide sample according to a predetermined order of nucleotide flows; 
 obtaining a series of signals resulting from the introducing of nucleotides to the polynucleotide sample; and 
 resolving the series of signals over the barcode sequence to render a flowspace string, wherein the flowspace string is a codeword of an error-correcting code that is (i) designed based on and adapted for use with the predetermined order of nucleotide flows, and (ii) capable of distinguishing any codeword in the error-correcting code from the other codewords in the error-correcting code in the presence of zero, one, and two errors. 
   
     
     
         19 . The system of  claim 18 , wherein the error-correcting code is a ternary code and the predetermined flow ordering is a phase-protecting predetermined flow ordering. 
     
     
         20 . A set of barcodes for nucleic acid sequencing, comprising: a plurality of nucleic acid base sequences, each nucleic acid base sequence being a base space representation of a flowspace representation of a codeword of an error-tolerant sample discrimination code, the error-tolerant sample discrimination code being (i) designed based on and adapted for use with the predetermined order of nucleotide flows, and (ii) capable of distinguishing any codeword in the error-correcting code from the other codewords in the error-correcting code in the presence of zero, one, and two errors.