Sequence identification and analysis

• US 7,809,765 B2
• Filed: 08/24/2007
• Issued: 10/05/2010
• Est. Priority Date: 08/24/2007
• Status: Active Grant

• Current Assignee: Global Life Sciences Solutions USA LLC (Danaher Corporation)
• Original Assignee: General Electric Company
• Inventors: Evans, Scott Charles, Markham, Thomas Stephen, Torres, Andrew Soliz
• Primary Examiner(s): Lee; Wilson
• Assistant Examiner(s): Thai; Hanh B
• Application Number:
  US11/844,619
• Publication Number:
  US 20090055425A1
• Time in Patent Office: 1,138 Days
• Field of Search: 707/802, 707/803, 707/804, 435/331, 435/333
• US Class Current: 707/802
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids

Abstract

The present technique provides for the analysis of a data series to identify sequences of interest within the series. Specifically, in accordance with one embodiment of the present technique, a method is provided comprising generating a data structure that stores characteristics about a plurality of sequences present in a data series. One or more sequences are identified based upon the contents of the data structure. In accordance with other aspects of the invention, more than one heuristic is calculated for each sequence under review. The plurality of heuristics associated with each sequence are evaluated to identify a sequence of interest.

Claims

1. A method for identifying a sequence of interest in a data series, comprising:

generating a data structure that stores characteristics about a plurality of sequences present in the data series;

identifying one or more sequences based upon the contents of the data structure;

evaluating one or more exit criteria to determine if an exit point has been reached;

updating the data structure to reflect the most recent identification of a sequence and

repeating the identification process if the exit criteria are not met; and

terminating if the exit criteria are met.

2. The method recited in claim 1, comprising providing at least one identified sequence to a user upon termination.

3. The method recited in claim 1, wherein the data structure is generated by analyzing the data series only once.

4. The method recited in claim 1, wherein the data structure is iteratively updated and maintained as sequence identification proceeds, without further reference to the data series.

5. The method recited in claim 1, wherein the data series comprises at least one of numerals, letters, or punctuation marks.

6. The method recited in claim 1, wherein the data series is a biological sequence selected from a deoxyribonucleic acid (DNA) sequence, a ribonucleic acid (RNA) sequence, or a peptide sequence.

7. A method for identifying a sequence of interest, comprising:

evaluating a plurality of heuristics for a candidate sequence from a plurality of candidate sequences present in a data series;

identifying a sequence in the plurality of candidate sequences based on the evaluation of the heuristics;

evaluating one or more exit criteria to determine if an exit point has been reached;

updating the data series or a corresponding data structure to reflect the most recent identification of a sequence and repeating the steps of evaluating the plurality of heuristics and identifing the sequences if the exit criteria are not met; and

terminating if the exit criteria are met.

8. The method recited in claim 7, comprising providing at least one identified sequence to a user upon termination.

9. The method recited in claim 7, wherein each heuristic comprises a data compression heuristic.

10. The method recited in claim 7 comprising calculating the plurality of heuristics for each respective candidate sequence.

11. The method of claim 7, wherein the plurality of heuristics are calculated using minimum description length (MDL) principles.

12. The method of claim 7, wherein the plurality of heuristics comprise different heuristic permutations derived for more than one iteration.

13. The method of claim 7, wherein at least one of the plurality of heurisitics comprises a symbol compression ratio (SCR) heuristic, a longest match (LM) heuristic, or a total compression (TC) heuristic.

14. A method for identifying a biological sequence of interest, comprising:

generating a data structure that stores characteristics about potential biological sequences of interest present in a biological polymer;

identifying one or more biological sequences based upon the contents of the data structure;

evaluating one or more exit criteria to determine if an exit point has been reached;

updating the data structure to reflect the most recent identification of a biological sequence and

repeating the identification process if the exit criteria are not met; and

terminating if the exit criteria are met.

15. The method recited in claim 14, comprising providing at least one identified biological sequence to a user upon termination.

16. The method recited in claim 14, wherein the biological polymer comprises one of a deoxyribonucleic acid (DNA) sequence, a ribonucleic acid (RNA) sequence, or a peptide sequence.

17. The method recited in claim 14, wherein the data structure is generated by analyzing the biological polymer only once.

18. The method recited in claim 14, wherein the data structure is iteratively updated and maintained, without further reference to the biological polymer.

19. One or more tangible, machine-readable media, comprising:

code adapted to generate a data structure that stores characteristics about a plurality of sequences present in a data series;

code adapted to identify one or more sequences based upon the contents of the data structure;

code adapted to evaluate one or more exit criteria to determine if an exit point has been reached;

code adapted to update the data structure to reflect the most recent identification of a sequence and repeating the identification process if the exit criteria are not met; and

code adapted to terminate if the exit criteria are met.

20. The tangible, machine-readable media recited in claim 19, wherein the code is adapted to provide at least one identified sequence to a user upon termination.

21. The tangible, machine-readable media recited in claim 19, wherein the code adapted to generate the data structure generates at least one of a matrix structure or a sequence array.

22. The tangible machine-readable media recited in claim 19, wherein the code adapted to generate the data structure analyzes the data series only once.

23. The tangible, machine-readable media recited in claim 19, wherein the code adapted to update the data structure iteratively updates the data structure without further reference to the data series.

24. One or more tangible, machine-readable media, comprising:

code adapted to evaluate a plurality of heuristics for a candidate sequence from a plurality of candidate sequences present in a data series;

code adapted to identify a sequence in the plurality of candidate sequences based on the evaluation of the heuristics;

code adapted to evaluate one or more exit criteria to determine if an exit point has been reached;

code adapted to update the data series or a corresponding data structure to reflect the most recent identification of a sequence and repeating the steps of evaluating the plurality of heuristics and identifing the sequences if the exit criteria are not met; and

code adapted to terminate if the exit criteria are met.

25. The tangible, machine-readable media recited in claim 24, comprising code adapted to provide at least one identified sequence to a user upon termination.

26. The tangible, machine-readable media recited in claim 24, wherein each heuristic comprises a data compression heuristic.

27. The tangible, machine-readable media recited in claim 24 comprising code adapted to calculate the plurality of heuristics for each respective candidate sequence.

28. The tangible, machine-readable media of claim 24, wherein the plurality of heuristics are calculated using minimum description length (MDL) principles.

29. The tangible, machine-readable media of claim 24, wherein the plurality of heuristics comprise different heuristic permutations derived for more than one iteration.

30. The tangible, machine-readable media of claim 24, wherein at least one of the plurlaity of heurisitics comprises a symbol compression ratio (SCR) heuristic, a longest match (LM) heuristic, or a total compression (TC) heuristic.