Oligomer sequences mapping

• US 8,731,843 B2
• Filed: 02/02/2010
• Issued: 05/20/2014
• Est. Priority Date: 02/03/2009
• Status: Active Grant

• Current Assignee: Complete Genomics Incorporated (BGI Genomics Co., Ltd.)
• Original Assignee: Complete Genomics Incorporated (BGI Genomics Co., Ltd.)
• Inventors: Halpern, Aaron L., Nazarenko, Igor
• Primary Examiner(s): Skibinsky, Anna
• Application Number:
  US12/698,994
• Publication Number:
  US 20110015864A1
• Time in Patent Office: 1,568 Days
• US Class Current: 702/19
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 30/20 Sequence assembly

Abstract

Mapping oligomer sequences includes receiving a set of related oligomer sequences, applying one or more key patterns derived from a set of oligomer sequence relationships to obtain one or more keys that are consistent with the set of related oligomer sequences, modifying positions within these keys, and locating the one or more keys in an index configured to map a plurality of candidate and/or validated keys to their respective possible and/or validated locations in a reference.

Claims

1. A method of oligomer sequence mapping, the method comprising:

receiving a data set of related oligomer sequences obtained from a same fragment of genetic material;

receiving a key pattern corresponding to a reference index;

receiving the reference index, the reference index generated by respectively applying the key pattern to each of a plurality of locations of a reference sequence to obtain a plurality of reference keys, the application of the key pattern to each of the locations selecting a same number of specified positions of the reference sequence, wherein the reference index includes the reference keys ordered by bases at one or more positions in the reference keys, the reference keys of the reference index being a same length;

applying the key pattern to the oligomer sequences in the data set to generate a first key comprising selected positions of the oligomer sequences;

modifying one or more bases at one or more positions of the first key to create a set of one or more modified first keys; and

comparing the modified first keys to the reference keys in the reference index to identify one or more reference keys that match to one or more of the modified first keys, thereby determining one or more candidate locations of the oligomer sequences in the reference sequence, wherein the method is performed with a computer.

2. The method of claim 1, wherein the one or more bases at the one or more positions are modified in the data set prior to application of the key pattern.

3. The method of claim 1, wherein the one or more bases at the one or more positions are modified following application of the key pattern.

4. The method of claim 1, further comprising:

validating candidate locations by comparing all bases of the data set to the indicated portions of the reference sequence corresponding to the matching reference keys.

5. The method of claim 1, wherein the one or more modifications include base substitutions to reflect all possible bases or combinations of bases at the one or more modified positions.

6. The method of claim 1, wherein the majority or all of the individual positions in the first key or the data set are individually substituted to create the set of modified first keys.

7. The method of claim 6, wherein the substitutions are adjacent substitutions.

8. The method of claim 6, wherein the substitutions are overlapping substitutions.

9. The method of claim 6, wherein the substitutions are non-adjacent substitutions.

10. The method of claim 1, wherein the one or more modifications are additions or deletion of positions in the key.

11. The method of claim 10, wherein the positions are modified individually.

12. The method of claim 1, wherein modifying the first key includes:

reordering the sequence of bases in the first key relative to an order of the bases occurring in the related oligomer sequences, wherein bases in the reference keys of the reference index are reordered relative to an order in the reference sequence.

13. A method of oligomer sequence mapping, comprising:

receiving data sets of sequences, each data set of related oligomer sequences obtained from a same fragment of genetic material;

receiving a key pattern corresponding to a reference index;

receiving the reference index, the reference index generated by respectively applying the key pattern to each of a plurality of locations of a reference sequence to obtain a plurality of reference keys, the application of the key pattern to each of the locations selecting a same number of specified positions of the reference sequence, wherein the reference index includes the reference keys ordered by bases at one or more positions in the reference keys, the reference keys of the reference index being a same length;

applying the key pattern to the oligomer sequences in each data set to generate keys comprising selected positions of the oligomer sequences of the data sets;

modifying individual positions of at least a portion of the keys to create a first set of modified keys;

modifying two or more combined positions of at least a portion of the keys to create a second set of modified keys; and

comparing the first and second set of modified keys to the reference index to determine one or more candidate locations of the oligomer sequences in the reference sequence, wherein the method is performed with a computer.

14. The method of claim 13, further comprising:

validating candidate locations for a first data set by comparing all bases of the first data set to indicated portions of the reference sequence corresponding to one or more reference keys matching to one or more first keys of the first data set.

15. The method of claim 13, wherein the modifications of the individual positions reflect all possible bases or combinations thereof.

16. A method of oligomer sequence mapping, comprising:

receiving data sets of sequences, each data set of related oligomer sequences obtained from a same fragment of genetic material;

receiving a key pattern corresponding to a reference index;

receiving the reference index, the reference index generated by respectively applying the key pattern to each of a plurality of locations of a reference sequence to obtain a plurality of reference keys, the application of the key pattern to each of the locations selecting a same number of specified positions of the reference sequence, wherein the reference index includes the reference keys ordered by bases at one or more positions in the reference keys, the reference keys of the reference index being a same length;

applying the key pattern to the oligomer sequences in each data set to generate keys comprising selected positions of the oligomer sequences of the data sets;

modifying two or more combined positions of at least a portion of the keys to create a first set of modified keys;

modifying two or more combined positions of at least a portion of the keys to create a second set of modified keys; and

comparing the first and second set of modified keys to the reference index to determine one or more candidate locations of the oligomer sequences in the reference sequence, wherein the method is performed with a computer.

17. The method of claim 16, further comprising:

validating candidate locations for a first data set by comparing all bases of the first data set to indicated portions of the reference sequence corresponding to one or more reference keys matching to one or more first keys of the first data set.

18. An oligomer sequence mapping system comprising:

an interface configured to receive;

a data set of related oligomer sequences obtained from a same fragment of genetic material, and

a key pattern corresponding to a reference index,

a memory that stores the reference index, the reference index generated by respectively applying the key pattern to each of a plurality of locations of a reference sequence to obtain a plurality of reference keys, the application of the key pattern to each of the locations causing a selection of a same number of specified positions of the reference sequence relative to the respective location, wherein the reference index stores the reference keys ordered by bases at one or more positions in the reference keys, the reference keys of the reference index being a same length; and

a processor coupled to the interface and to the memory, wherein the processor is configured to;

apply the key pattern to information in the data set to generate a first key comprising selected positions of the oligomer sequences;

modify one or more bases at one or more positions within the first key to create a set of one or more modified first keys, and

compare the first keys generated from the data set and the modified first keys to the reference keys in the reference index to identify one or more reference keys that match to one or more of the modified first keys, thereby determining one or more candidate locations of the oligomer sequences in the reference sequence, wherein the comparing uses the ordering of the reference keys in the reference index.

19. The system of claim 18, wherein the processor is further configured to validate the candidate locations by comparing bases of the data set to the indicated portions of the reference sequence corresponding to the matching reference keys.

20. The system of claim 18, wherein the processor is further configured to output locations of the oligomer sequences in the reference sequence.

21. The system of claim 18, wherein the processor is configured to perform multiple modification regimes using the data set.

22. The product of claim 18, wherein individual positions are modified.

23. The product of claim 18, wherein two or more combined positions are modified.

24. The system of claim 19, wherein the processor is configured to substitute the majority or all of the positions to create the set of modified first keys to reflect all possibilities of bases or combinations thereof.

25. A computer program product for oligomer sequence mapping, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:

receiving a data set of related oligomer sequences obtained from a same fragment of genetic material;

receiving a key pattern corresponding to a reference index;

receiving the reference index, the reference index generated by respectively applying the key pattern to each of a plurality of locations of a reference sequence to obtain a plurality of reference keys, the application of the key pattern to each of the locations selecting a same number of specified positions of the reference sequence, wherein the reference index includes the reference keys ordered by bases at one or more positions in the reference keys, the reference keys of the reference index being a same length;

applying the key pattern to information in the data set to generate a first key comprising selected positions of the oligomer sequences;

modifying multiple positions within the first key to create a set of modified first keys; and

comparing the modified first keys to the reference keys in the reference index to identify one or more reference keys that match to one or more of the modified first keys, thereby determining one or more candidate locations of the oligomer sequences in the reference sequence.