Primer design using indexed genomic information

Abstract

Techniques for identifying regions in nucleic acid sequences for which to design highly discriminatory primers are provided. In some embodiments, a corpus of nucleic acid sequences may be divided into a first set and a second set, and a respective index may be built containing data structures representing a plurality of k-mers of each nucleic acid sequence. By comparing the data structures of the first index to one another, a system may iteratively determine whether each k-mer over a given region in one of the nucleic acid sequences in the first set are also found in every other sequence in the first set. By comparing against the data structures in the second index, a system may then iteratively determine whether all k-mers in the region can be found in the same order of in any of the nucleic acid sequences in the second set.

1 . A method for identifying nucleic acid sequence regions, comprising:
 at a system comprising one or more processors and memory storing instructions executable by the processor:
 receiving genomic data representing a plurality of nucleic acid sequences; 
 creating and storing data in a first index representing a first set of the plurality of nucleic acid sequences, wherein the first index comprises at least 4 12  elements representing respective permutations of nucleic acid sequences, and wherein the data created and stored in the first index comprises a first plurality of data structures each associated with a respective nucleic acid sequence of the first set; 
 creating and storing data in a second index representing a second set of the plurality of nucleic acid sequences, wherein the second index comprises at least 4 12  elements representing respective permutations of nucleic acid sequences, and wherein the data created and stored in the second index comprises a second plurality of data structures each associated with a respective nucleic acid sequence of the second set; 
 identifying, by the first index, a region appearing in every nucleic acid sequence in the first set; 
 confirming, by the second index, that the region appears in none of the nucleic acid sequences in the second set; and 
 generating and outputting data representing the identified region. 
   
     
     
         2 . The method of  claim 1 , wherein creating and storing data in the first index comprises:
 for each of the nucleic acid sequences in the first set, dividing the nucleic acid sequence into a plurality of sub-strings;   for each of the plurality of sub-strings, storing a respective one of the first plurality of data structures in the first index, wherein the respective one of the first plurality of data structures indicates an identity of the nucleic acid sequence, a permutation of bases forming the sub-string, and a position of the sub-string in the nucleic acid sequence.   
     
     
         3 . The method of  claim 2 , wherein identifying the region appearing in every nucleic acid sequence in the first set comprises determining, for a given sub-string of a first nucleic acid sequence of the first set, that a corresponding first data structure stored in the first index indicates a common permutation of bases as a second data structure stored in the first index for a second nucleic acid sequence in the first set. 
     
     
         4 . The method of  claim 3 , wherein identifying the region appearing in every nucleic acid sequence in the first set comprises determining that the second data structure indicates:
 an identity for the second nucleic acid sequence that matches an identity of a nucleic acid sequence that has been determined to include a previously-matched sub-string, wherein the previously-matched sub-string matches the first nucleic acid sequence at a span occurring immediately before the given sub-string in the first nucleic acid sequence; and   a position in the second nucleic acid sequence corresponding to a span occurring immediately after the previously-matched sub-string.   
     
     
         5 . The method of  claim 3 , wherein the determination is performed iteratively with respect to different sub-strings of the first nucleic acid sequence and different data structures in the first index, until a plurality of adjacent sub-strings of the first nucleic acid sequence are determined to occur in a same order in each of the other nucleic acid sequences in the first set,
 wherein the plurality of adjacent sub-strings of the first nucleic acid sequence together are at least a predefined minimum number of bases in length.   
     
     
         6 . The method of  claim 2 , wherein confirming that the region appears in none of the nucleic acid sequences in the second set comprises:
 determining, for at least one given sub-string of a nucleic acid sequence of the first set, whether a data structure stored in the second index for a nucleic acid sequence in the second set indicates all three of:
 a common permutation of bases as indicated by a data structure stored in the first index for the nucleic acid sequence of the first set; 
 an identity for the nucleic acid sequence of the second set that matches an identity of a nucleic acid sequence that has been determined to include a previously-matched sub-string, wherein the previously-matched sub-string matches the nucleic acid sequence of the first set at a span occurring immediately before the given sub-string in the nucleic acid sequence of the first set; and 
 a position in the nucleic acid sequence of the second set corresponding to a span occurring immediately after the previously-matched sub-string. 
   
     
     
         7 . The method of  claim 6 , wherein the determination is performed iteratively with respect to different sub-strings of the nucleic acid sequence of the first set in order to determine that, for every nucleic acid sequence in the second index, at least one data structure fails at least one of the three conditions for at least one sub-string in the region of the first nucleic acid sequence. 
     
     
         8 . The method of  claim 1 , wherein the plurality of nucleic acid sequences comprises one of DNA, cDNA, RNA, mRNA, PNA. 
     
     
         9 . The method of  claim 1 , wherein creating and storing data in the second index comprises:
 for each of the nucleic acid sequences in the second set, dividing the nucleic acid sequence into a plurality of sub-strings;   for each of the plurality of sub-strings, storing a respective one of the second plurality of data structures in the second index, wherein the respective one of the second plurality of data structures indicates an identity of the nucleic acid sequence, a permutation of bases forming the sub-string, and a position of the sub-string in the nucleic acid sequence.   
     
     
         10 . The method of  claim 1 , wherein the first set of the plurality of nucleic acid sequences comprises one or more complete genomic sequences. 
     
     
         11 . The method of  claim 1 , wherein the second set of the plurality of nucleic acid sequences comprises one or more complete genomic sequences. 
     
     
         12 . A system for identifying nucleic acid sequence regions, the system comprising:
 one or more processors;   memory storing one or more programs, the one or more programs configured to be executed by the one or more processors and including instructions to:   receive genomic data representing a plurality of nucleic acid sequences;   create and store data in a first index representing a first set of the plurality of nucleic acid sequences, wherein the first index comprises at least 4 12  elements representing respective permutations of nucleic acid sequences, and wherein the data created and stored in the first index comprises a first plurality of data structures each associated with a respective nucleic acid sequence of the first set;   create and store data in a second index representing a second set of the plurality of nucleic acid sequences, wherein the second index comprises at least 4 12  elements representing respective permutations of nucleic acid sequences, and wherein the data created and stored in the second index comprises a second plurality of data structures each associated with a respective nucleic acid sequence of the second set;   identify, by the first index, a region appearing in every nucleic acid sequence in the first set;   confirm, by the second index, that the region appears in none of the nucleic acid sequences in the second set; and   generate and output data representing the identified region.   
     
     
         13 . A non-transitory computer-readable storage medium storing one or more programs for identifying nucleic acid sequence regions, the one or more programs configured to be executed by one or more processors and including instructions to:
 receive genomic data representing a plurality of nucleic acid sequences;   create and store data in a first index representing a first set of the plurality of nucleic acid sequences, wherein the first index comprises at least 4 12  elements representing respective permutations of nucleic acid sequences, and wherein the data created and stored in the first index comprises a first plurality of data structures each associated with a respective nucleic acid sequence of the first set;   create and store data in a second index representing a second set of the plurality of nucleic acid sequences, wherein the second index comprises at least 4 12  elements representing respective permutations of nucleic acid sequences, and wherein the data created and stored in the second index comprises a second plurality of data structures each associated with a respective nucleic acid sequence of the second set;   identify, by the first index, a region appearing in every nucleic acid sequence in the first set;   confirm, by the second index, that the region appears in none of the nucleic acid sequences in the second set; and   generate and output data representing the identified region.