INDEXING A REFERENCE SEQUENCE FOR OLIGOMER SEQUENCE MAPPING

• US 20100287165A1
• Filed: 02/02/2010
• Published: 11/11/2010
• 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
• Granted Patent: US 8,738,296 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• 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

Abstract

Generating an index includes receiving a reference sequence and applying one or more key patterns to the reference sequence to obtain a plurality of keys in the index. Each of the one or more key patterns is derived based on a corresponding set of oligomer sequence relationships of a plurality of oligomer sequences that are expected to be generated from the reference, and the keys correspond to a plurality of candidate and/or validated locations in the reference sequence.

Claims

1. A method of generating an index, comprising:

a. applying one or more key patterns to a reference to generate a plurality of keys, wherein the key patterns are based on predicted data set sequence relationships having at least one variable separation distance; and

b. providing the keys in a searchable medium;

wherein each key corresponds to one or more possible locations within the reference.

2. The method of claim 1, wherein the predicted sequence relationships comprise both variable and fixed separation distances.

3. The method of claim 1, further comprising storing the plurality of keys in a computer readable medium.

4. The method of claim 1, wherein the keys are generated by applying the one or more key patterns using sequential base key generation.

5. The method of claim 4, wherein the key pattern is sequentially forwarded on the reference by a single base.

6. The method of claim 1, wherein the index comprises keys generated using a genomic sequence as the reference.

7. The method of claim 6, wherein the genomic sequence comprises human sequence.

8. The method of claim 6, wherein the genomic sequence comprises substantially an entire genomic sequence.

9. The method of claim 1, wherein the reference comprises RNA or cDNA sequence.

10. The method of claim 1, wherein the RNA or cDNA sequence comprises human sequence.

11. The method of claim 1, wherein the reference includes two or more variations of a single reference.

12. The method of claim 1, wherein an index includes keys generated from two or more references.

13. The method of claim 1, wherein the predicted sequence data sets are based in part on statistical distribution information for conserved positions in the data sets.

14. The method of claim 13, wherein the statistical distribution information includes predicted distribution of distances between two or more adjacent oligomers.

15. The method of claim 13, wherein the statistical distribution information includes predicted distribution of distance combinations within a set of related oligomers.

16. The method of claim 1, wherein the key pattern has a pattern length sufficiently long to avoid generating an undesired number of candidate locations in the reference.

17. The method of claim 1, wherein the index comprises keys having bases in the sequential order of the reference.

18. The method of claim 1, wherein the keys are reordered. The method of claim 1, wherein the index includes two or more sub-indexes.

19. The method of claim 19, wherein the index includes a prefix index.

21. The method of claim 19, wherein the index further includes a suffix index.

20. The method of claim 20, wherein the entries in the prefix index map to a plurality of offsets in a sub-index.

22. The method of claim 22, wherein the entries in the suffix index map to a plurality of possible locations in the reference.

23. A system for generating an index for oligomer sequence analysis, comprising:

an interface configured to receive a reference; and

a processor coupled to the interface, configured to apply one or more key patterns to the reference to obtain a plurality of keys in the index, wherein the one or more key patterns are derived based on predicted data set sequence relationships comprising at least one area of variable separation distance; and

the keys correspond to possible locations in the reference.

24. A computer program product for generating an index, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

receiving a reference; and

applying one or more key patterns to the reference to obtain a plurality of keys in an index, wherein

the one or more key patterns are derived from predicted data set sequence relationships comprising at least one area of variable separation distance; and

the keys correspond to possible locations in the reference.