Efficient comparison of polynucleotide sequences

A computer-based method of searching for a first 20 mer oligonucleotide sequence in a nucleotide data set, wherein said sequence is homologous to and differs by at most one nucleotide from a second 20 mer oligonucleotide target sequence, comprising:

• selecting a second 20 mer oligonucleotide target sequence having a sequence which is unique in a reference genomic nucleotide data set and which spans one single nucleotide polymorphism;
• determining if the selected second 20 mer sequence is present in a sequence determined from a sequencing reaction initiated on a nucleic acid sample to determine if a 20 mer sequence spanning said one single nucleotide polymorphism is present in the sample;
• if said 20 mer sequence is present, determining whether said sequence of said sequencing reaction is identical to said first 20 mer oligonucleotide sequence at said single nucleotide polymorphism;
• and
• generating a report indicating whether said second 20 mer is present in any sequence determined from the sequencing reaction.

A method of aligning a first 20 mer oligonucleotide sequence to all 20 mer fragments of a nucleotide data set comprising:

• indexing said dataset into perfect Hamming code 5 mers, wherein each said perfect Hamming code 5 mer has a set of 15 5 mers which form an equivalence class such that each of said 15 additional members of said class differs from said perfect Hamming code 5 mer by a Hamming code distance of 1, and wherein each said perfect Hamming code 5 mer differs from all other perfect Hamming code 5 mers by at least a Hamming code distance of 3;
• configuring said indexed 5 mers into a trie having a branching factor of 64 such that each leaf of said trie represents the perfect Hamming code 5 mers of said dataset and the equivalence class it defines;
• concatenating said trie such that each leaf of said index is a trunk of a second level indexed 5 mer trie, each leaf of said second level trie is a trunk of a third level trie and each leaf of said third level trie is a trunk of a fourth level trie, such that said concatenated trie has a depth of 4 and 644 leaves at its fourth level, and such that each 20 mer of said nucleic acids sample maps to only one path from a 4th level leaf to the first level trunk of said trie, wherein each unique trie path corresponds to a concatenation of four consecutive perfect Hamming code 5 mers to form a 20 mer fragment of said trie path;
• assigning all 20 mer fragments of said nucleotide data set to a unique trie path;
• identifying said trie path corresponding to said 20 mer oligonucleotide sequence;
• and
• comparing said 20 mer fragments of said trie path to said 20 mer oligonucleotide sequence, wherein said comparing comprises:
• comparing positions 1-5 of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 1 having at least on member which differs from at least one member of the equivalence class of the 5 mer oligonucleotide by a Hamming distance of 1,
• comparing positions 6-10 of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 2 having at least on member which differs from at least one member of the equivalence class of the 5 mer oligonucleotide by a Hamming distance of 1,
• comparing positions 11-15 of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 3 having at least on member which differs from at least one member of the equivalence class of the 5 mer oligonucleotide by a Hamming distance of 1,
• comparing positions 16-20 of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 4 having at least on member which differs from at least one member of the equivalence class of the 5 mer oligonucleotide by a Hamming distance of 1, and
• comparing said 20 mer oligonucleotide to the concatenated oligonucleotide comprising the four perfect Hamming code 5 mers,
• such that all possible oligonucleotide sequences having a Hamming code distance of at most 1 from a 20 mer oligonucleotide sequence due to having one single nucleotide polymorphism relative to the 20 mer oligonucleotide are analyzed through the selection and comparison of 121 out of a total of over 16 million equivalence classes in a four level index of concatenated 5 mers.

A computer based system for aligning a 20 mer oligonucleotide sequence to all 20 mer fragments of a nucleotide dataset comprising:

• an index component comprising perfect Hamming code 5 mers, wherein each said 5 mer has a set of 15 5 mers which form an equivalence class such that each additional member of said class differs from said perfect Hamming code 5 mer by a Hamming code distance of 1, and wherein each said perfect Hamming code 5 mer differs from all other perfect Hamming code 5 mers by at least a Hamming code distance of 3;
• an iterative trie component of said perfect Hamming code 5 mers having a branching factor of 64 such that each leaf of said trie represents a perfect Hamming code 5 mer of said dataset and the equivalence class it defines, and such that each leaf of a first level of said trie is the trunk of a second indexed 5 mer trie, each leaf of said second level trie is the trunk of a third level trie trunk, and each leaf of said third level trie is the trunk of a fourth level trie, such that said trie has a depth of 4 levels and 644 leaves, and such that each 20 mer of said nucleic acids sample maps to only one path from a 4th level leaf to the first level trunk of said trie;
• an assignment component that assigns all 20 mer fragments of said nucleotide data set to a unique trie path corresponding to said 20 mer fragments;
• an identification component identifying said trie path corresponding to said 20 mer oligonucleotide sequence;
• a comparing component for:
• comparing said 20 mer fragments of said trie path to said 20 mer oligonucleotide sequence,
• comparing a first five positions of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 1 having at least on member which differs from at least one member of the equivalence class of the 20 mer oligonucleotide by a Hamming distance of 1,
• comparing a second five positions of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 2 having at least on member which differs from at least one member of the equivalence class of the 20 mer oligonucleotide by a Hamming distance of 1,
• comparing a third five positions of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 3 having at least on member which differs from at least one member of the equivalence class of the 20 mer oligonucleotide by a Hamming distance of 1, and
• comparing a fourth five positions of said 20 mer oligonucleotide sequence to the thirty equivalence classes at level 4 having at least on member which differs from at least one member of the equivalence class of the 20 mer oligonucleotide by a Hamming distance of 1,
• such that all possible oligonucleotide sequences having a Hamming code distance of at most 1 from a 20 mer oligonucleotide sequence are analyzed through the selection of 121 out of a total of over 16 million equivalence classes in a four level index of concatenated 5 mers;
• and
• a report module capable of reporting the results of said evaluation to a user.