Method for identifying sub-sequences of interest in a sequence

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.

1 . A method for identifying a sequence of interest, comprising the steps of: 
 analyzing a data series based on a grammar comprising at least an initial grammar;    calculating a statistical heuristic for each sub-sequence of the analyzed data series;    comparing a selected statistical heuristic with one or more reference conditions;    updating 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    identifying the sequence as a sequence of interest based upon a termination result of the comparison.    
     
     
         2 . The method, as recited in  claim 1 , further comprising the step of iterating the steps of analyzing, calculating, comparing, and updating until a termination result of the comparison occurs.  
     
     
         3 . The method, as recited in  claim 1 , wherein the data series comprises one of a deoxyribonucleic acid sequence, a ribonucleic acid sequence, and an amino acid sequence.  
     
     
         4 . The method, as recited in  claim 1 , wherein calculating the statistical heuristic for each sub-sequence comprises computing the statistical heuristic using a minimum sufficient statistics algorithm.  
     
     
         5 . The method, as recited in  claim 1 , wherein calculating the statistical heuristic for each sub-sequence comprises computing a symbol compression ratio using an optimal symbol compression ratio algorithm.  
     
     
         6 . The method, as recited in  claim 1 , wherein the sequence of interest comprises a repeated sequence within the data series.  
     
     
         7 . The method, 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.  
     
     
         8 . The method, 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.  
     
     
         9 . 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.    
     
     
         10 . The tangible medium, as recited in  claim 9 , comprising code adapted to iterate the steps of analyzing, calculating, comparing, and updating until a termination result of the comparison occurs.  
     
     
         11 . The tangible medium, as recited in  claim 9 , wherein the code adapted to calculate the statistical heuristic for each sub-sequence computes the statistical heuristic using a minimum sufficient statistics algorithm.  
     
     
         12 . The tangible medium, as recited in  claim 9 , 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.  
     
     
         13 . The tangible medium, as recited in  claim 9 , 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.  
     
     
         14 . The tangible medium, as recited in  claim 9 , wherein the statistical heuristic comprises a symbol compression ratio and wherein the selected statistical heuristic comprises the symbol compression ratio having the lowest value.  
     
     
         15 . A method for processing a data series, the method comprising: 
 specifying a data series for analysis;    executing one or more routines configured to analyze the data series based on minimum description length principles; and    obtaining the analyzed data series comprising at least one sequence of interest.    
     
     
         16 . The method as recited in  claim 15 , wherein specifying a data series comprises specifying one of a deoxyribonucleic acid sequence, a ribonucleic acid sequence, and an amino acid sequence.  
     
     
         17 . The method as recited in  claim 15 , wherein the one or more executed routines implement one or more sufficient statistics algorithms.  
     
     
         18 . The method as recited in  claim 15 , wherein the one or more executed routines implement one or more optimal symbol compression algorithms.  
     
     
         19 . The method as recited in  claim 15 , wherein the at least one sequence of interest comprises a repeated sequence within the data series.  
     
     
         20 . A method for identifying a biological sequence of interest, the method comprising: 
 analyzing a biological polymer sequence based on a grammar comprising at least an initial grammar;    calculating a minimum description length heuristic for each sub-sequence of the analyzed biological polymer sequence;    comparing a selected minimum description length heuristic with one or more reference conditions;    updating 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    identifying the sub-sequence as a biological sequence of interest based upon a termination result of the comparison.    
     
     
         21 . The method, as recited in  claim 20 , wherein the biological polymer comprises one of a deoxyribonucleic acid, a ribonucleic acid, and a peptide.  
     
     
         22 . The method, as recited in  claim 20 , further comprising iterating the steps of analyzing, calculating, comparing, and updating until a termination result of the comparison occurs.  
     
     
         23 . The method, as recited in  claim 20 , 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.  
     
     
         24 . 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.    
     
     
         25 . The tangible medium, as recited in  claim 24 , comprising: 
 code adapted to iterate the steps of analyzing, calculating, comparing, and updating until a termination result of the comparison occurs.    
     
     
         26 . The tangible medium, as recited in  claim 24 , 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.