Method for Identifying Sub-Sequences of Interest in a Sequence

• US 20080270439A1
• Filed: 03/06/2008
• Published: 10/30/2008
• Est. Priority Date: 06/02/2004
• Status: Active Grant

• Current Assignee: Global Life Sciences Solutions Operations UK Ltd. (Danaher Corporation)
• Original Assignee: General Electric Company
• Inventors: Evans, Scott Charles, Bush, Stephen Francis, Torres, Andrew Soliz
• Granted Patent: US 8,046,173 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• 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. The analysis may be used to iteratively update a grammar used to analyze the data series or updated versions of the data series. Furthermore, the technique provides for the calculation of a minimum description length heuristic, such as a symbol compression ratio, for each sub-sequence of the analyzed data sequence. The technique may then compare a selected heuristic value against one or more reference conditions to determine if additional iteration is to be performed. The grammar and the data sequence may be updated between iterations to include a symbol representing a string corresponding to the selected heuristic value based upon a non-termination result of the comparison. Alternatively, the string corresponding to the selected heuristic value may be identified as a sequence of interest based upon a termination result of the comparison.

Claims

1. A tangible, machine-readable media, comprising:

code adapted to analyze a data series based on a grammar comprising at least an initial grammar;

code adapted to calculate a statistical heuristic for each sub-sequence of the analyzed data series;

code adapted to compare a selected statistical heuristic with one or more reference conditions;

code adapted to update the grammar and the data series with a symbol representing a sequence corresponding to the selected statistical heuristic based upon a non-termination result of the comparison; and

code adapted to identify the sequence as a sequence of interest based upon a termination result of the comparison.

2. The tangible medium, as recited in claim 1, comprising code adapted to iterate the steps of analyzing, calculating, comparing, and updating until a termination result of the comparison occurs.

3. The tangible medium, as recited in claim 1, wherein the code adapted to calculate the statistical heuristic for each sub-sequence computes the statistical heuristic using a minimum sufficient statistics algorithm.

4. The tangible medium, as recited in claim 1, wherein the code adapted to calculate the statistical heuristic for each sub-sequence computes a symbol compression ratio using an optimal symbol compression ratio algorithm.

5. The tangible medium, as recited in claim 1, wherein the statistical heuristic comprises a minimum description length heuristic and wherein the selected statistical heuristic comprises the minimum description length heuristic having the lowest value.

6. The tangible medium, as recited in claim 1, wherein the statistical heuristic comprises a symbol compression ratio and wherein the selected statistical heuristic comprises the symbol compression ratio having the lowest value.

7. A tangible, machine-readable media, comprising:

code adapted to analyze a biological polymer sequence based on a grammar comprising at least an initial grammar;

code adapted to calculate a minimum description length heuristic for each sub-sequence of the analyzed biological polymer sequence;

code adapted to compare a selected minimum description length heuristic with one or more reference conditions;

code adapted to update the grammar and the biological polymer sequence with a symbol representing a sub-sequence corresponding to the selected minimum description length heuristic based upon a non-termination result of the comparison; and

code adapted to identify the sub-sequence as a biological sequence of interest based upon a termination result of the comparison.

8. The tangible medium, as recited in claim 7, comprising:

code adapted to iterate the steps of analyzing, calculating, comparing, and updating until a termination result of the comparison occurs.

9. The tangible medium, as recited in claim 7, wherein the minimum description length heuristic comprises a symbol compression ratio and the selected minimum description length heuristic comprises the symbol compression ratio having the lowest value.