Methods and systems for barcode error correction

Abstract

Methods and systems for designing large sets of barcodes that ensure robust and efficient error correction capabilities are described. Also described are methods for assigning barcodes to target analytes that minimize optical crowding in in situ detection applications. Furthermore, methods for performing barcode error correction and for performing barcode-assisted image registration and alignment are also described.

1 . A computer-implemented method for error correction of decoded target barcode sequences comprising:
 obtaining an image for each decoding cycle of a plurality of decoding cycles to obtain a series of images;   detecting, in each image of the series of images, one or more locations of one or more respective barcode probe sequences of a plurality of barcode probe sequences, wherein the one or more respective barcode probe sequences are hybridized or bound to one or more target oligonucleotide sequences or segments thereof;   decoding a plurality of target oligonucleotide sequences based on which decoding cycle and for which locations in one or more images of the series of images the one or more respective barcode probe sequences of the plurality are detected to obtain a plurality of decoded target oligonucleotide sequences; and   correcting one or more of the decoded target oligonucleotide sequences of the plurality by replacement with a known target oligonucleotide sequence, or proxy thereof, that has a maximum likelihood as computed from a probability distribution that provides probabilities for detecting a given barcode probe sequence at a given location in a given decoding cycle.   
     
     
         2 . The computer-implemented method of  claim 1 , further comprising detecting the presence of one or more target analytes in a sample based on the one or more corrected target oligonucleotide sequences. 
     
     
         3 . The computer-implemented method of  claim 1 , wherein the target oligonucleotide sequences comprise target analyte sequences. 
     
     
         4 . The computer-implemented method of  claim 3 , wherein the target analyte sequences comprise messenger ribonucleic acid (mRNA) sequences. 
     
     
         5 . The computer-implemented method of  claim 1 , wherein the target oligonucleotide sequences comprise target barcode sequences associated with target analytes. 
     
     
         6 . The computer-implemented method of  claim 5 , wherein the target barcode sequences comprise sequences of individual nucleotides. 
     
     
         7 . The computer-implemented method of  claim 5 , wherein the target barcode sequences comprise a plurality of segments, and each segment comprises a plurality of nucleotides. 
     
     
         8 . The computer-implemented method of  claim 7 , wherein the target barcode sequences function as proxies for target analyte sequences. 
     
     
         9 .- 10 . (canceled) 
     
     
         11 . The computer-implemented method of  claim 1 , wherein the correcting step further comprises replacement of the one or more decoded target oligonucleotide sequences with a known target oligonucleotide sequence from a subset of known target oligonucleotide sequences, or proxies thereof, that are within a specified pairwise edit distance of the decoded target oligonucleotide sequence, and wherein the maximum likelihood is computed from the probability distribution for the subset of known target oligonucleotide sequences. 
     
     
         12 . (canceled) 
     
     
         13 . The computer-implemented method of  claim 11 , wherein the specified pairwise edit distance comprises a specified pairwise Hamming distance of at most two times a specified error correction capability comprising correction of 1, 2, 3, 4, or 5 substitution errors. 
     
     
         14 . (canceled) 
     
     
         15 . The computer-implemented method of  claim 1 , wherein the correcting step further comprises an iterative calculation of maximum likelihood for the probability distribution to identify a candidate target oligonucleotide sequence for use in correction, and wherein the probability distribution is updated in each iteration based on the candidate target oligonucleotide sequence barcode. 
     
     
         16 . The computer-implemented method of  claim 15 , wherein the iterative calculation is complete when: (i) a predetermined number of iterations has been reached, (ii) the probability distribution remains substantially unchanged from one iteration to the next, or (iii) a number of corrected target oligonucleotide sequences remains substantially unchanged from one iteration to the next. 
     
     
         17 . (canceled) 
     
     
         18 . The computer-implemented method of  claim 1 , wherein the probability distribution is provided by a probabilistic model comprising a machine learning model. 
     
     
         19 . (canceled) 
     
     
         20 . The computer-implemented method of  claim 18 , wherein the machine learning model comprises a random forest or neural network model. 
     
     
         21 . The computer-implemented method of  claim 1 , wherein a number of decoding cycles in the plurality of decoding cycles is equal to a number of segments in the target oligonucleotide sequences. 
     
     
         22 . (canceled) 
     
     
         23 . The computer-implemented method of  claim 1 , wherein the plurality of target oligonucleotide sequences is a plurality of target barcode sequences that comprises a specified total number of unique nucleic acid barcode sequences, and wherein each unique nucleic acid barcode sequence, or segment thereof, of the plurality is selected to have:
 a specified maximum nucleotide length;   a specified minimum pairwise edit distance relative to other unique nucleic acid barcode sequences, or segments thereof, of the plurality; and   at least one additional characteristic selected from a list consisting of: a specified total nucleotide length, a specified number of segments, a specified segment length, a specified upper limit on guanine-cytosine (GC) content, a specified maximum length for homopolymer subsequences, and a specified dilution factor for at least one segment.   
     
     
         24 . (canceled) 
     
     
         25 . The computer-implemented method of  claim 23 , wherein the specified minimum pairwise edit distance comprises a specified minimum pairwise Hamming distance of at least two times a specified error correction capability comprising correction of 1, 2, 3, 4, or 5 substitution errors. 
     
     
         26 . (canceled) 
     
     
         27 . The computer-implemented method of  claim 23 , wherein the at least one additional characteristic comprises a specified minimum number of segments of at least two. 
     
     
         28 . The computer-implemented method of  claim 23 , wherein the at least one additional characteristic comprises a specified minimum segment length of at least two nucleotides. 
     
     
         29 . The computer-implemented method of  claim 23 , wherein the at least one additional characteristic comprises a specified upper limit on guanine-cytosine (GC) content of about 50%. 
     
     
         30 . The computer-implemented method of  claim 23 , wherein the at least one additional characteristic comprises a specified maximum length for homopolymer subsequences of 7 nucleotides. 
     
     
         31 . The computer implemented method of  claim 23 , wherein at least one segment of at least one target barcode sequence of the plurality encodes for an “OFF” state that is not visualized in at least one decoding cycle. 
     
     
         32 . The computer-implemented method of  claim 23 , wherein the at least one additional property comprises a specified decoding dilution factor of at least 10% for the least one segment. 
     
     
         33 . (canceled) 
     
     
         34 . The computer-implemented method of  claim 23 , wherein each target barcode sequence of the plurality is rank-ordered according to an average pairwise edit distance from all other target acid barcode sequences of the plurality, and assigned to a corresponding target gene transcript of the same rank from a list of corresponding genes rank-ordered by relative expression level. 
     
     
         35 . (canceled) 
     
     
         36 . The computer-implemented method of  claim 34 , wherein the rank-ordered unique nucleic acid barcode sequences are assigned to corresponding rank-ordered target gene transcripts such that optical crowding is reduced during a decoding process used to decode the unique nucleic acid barcode sequences. 
     
     
         37 . The computer-implemented method of  claim 23 , wherein the specified total number of unique nucleic acid barcode sequences is at least 1,000. 
     
     
         38 .- 40 . (canceled) 
     
     
         41 . The computer-implemented method of  claim 23 , wherein the unique nucleic acid barcode sequences of the plurality have been incorporated into a set of target-specific probe molecules. 
     
     
         42 . The computer-implemented method of  claim 23 , wherein each unique nucleic acid barcode sequence is attached to a different feature of a spatial array. 
     
     
         43 . The computer-implemented method of  claim 23 , wherein each unique nucleic acid barcode sequence is attached to a different bead of a bead array. 
     
     
         44 . A system comprising:
 one or more processors;   memory operably coupled to the one or more processors; and   one or more programs stored in the memory that, when executed by the one or more processors, cause the system to execute a method comprising:
 obtaining an image for each decoding cycle of a plurality of decoding cycles to obtain a series of images; 
 detecting, in each image of the series of images, one or more locations of one or more respective barcode probe sequences of a plurality of barcode probes sequences, wherein the one or more respective barcode probe sequences are hybridized or bound to one or more target oligonucleotide sequences or segments thereof; 
 decoding a plurality of target oligonucleotide sequences based on which decoding cycle and for which locations in one or more images of the series of images the one or more respective barcode probe sequences of the plurality are detected to obtain a plurality of decoded target oligonucleotide sequences; and 
 correcting one or more of the decoded target oligonucleotide sequences of the plurality by replacement with a known target oligonucleotide sequence, or proxy thereof, that has a maximum likelihood as computed from a probability distribution that provides probabilities for detecting a given barcode probe sequence at a given location in a given decoding cycle. 
   
     
     
         45 . A non-transitory computer-readable storage medium storing one or more programs, the one or more programs comprising instructions which, when executed by one or more processors of a computing platform, cause the computing platform to perform a method comprising:
 obtaining an image for each decoding cycle of a plurality of decoding cycles to obtain a series of images;   detecting, in each image of the series of images, one or more locations of one or more respective barcode probe sequences of a plurality of barcode probes sequences, wherein the one or more respective barcode probe sequences are hybridized or bound to one or more target oligonucleotide sequences or segments thereof;   decoding a plurality of target oligonucleotide sequences based on which decoding cycle and for which locations in one or more images of the series of images the one or more respective barcode probe sequences of the plurality are detected to obtain a plurality of decoded target oligonucleotide sequences; and   correcting one or more of the decoded target oligonucleotide sequences of the plurality by replacement with a known target oligonucleotide sequence, or proxy thereof, that has a maximum likelihood as computed from a probability distribution that provides probabilities for detecting a given barcode probe sequence at a given location in a given decoding cycle.