Methods and systems for conservative extraction of over-represented extensible motifs

Abstract

Methods and systems of extracting extensible motifs from a sequence include assigning a significance to extensible motifs within the sequence based upon a syntactic and statistical analysis, and identifying extensible motifs having a significance that exceeds a predetermined threshold.

1 . A method of extracting an extensible motif from a sequence, said method comprising:
 assigning a significance to an extensible motif within said sequence based upon a syntactic and statistical analysis; and   identifying an extensible motif having a significance that exceeds a predetermined threshold.   
     
     
         2 . The method of  claim 1 , wherein said assigning said significance comprises:
 scanning the sequence to identify patterns that have two solid characters;   storing start and end positions of the identified patterns; and   combining all cells with a dot character and the same start and end solid characters to construct extensible cells.   
     
     
         3 . The method of  claim 1 , wherein said assigning said significance comprises pruning by occurrences. 
     
     
         4 . The method of  claim 1 , wherein said assigning said significance comprises pruning by composition. 
     
     
         5 . A system for extracting an extensible motif from a sequence, said system comprising:
 means for assigning a significance to an extensible motif within said sequence based upon a syntactic and statistical analysis; and   means for identifying an extensible motif having a significance that exceeds a predetermined threshold.   
     
     
         6 . The system of  claim 5 , wherein said means for assigning said significance comprises:
 means for scanning the sequence to identify patterns that have two solid characters;   means for storing start and end positions of the identified patterns; and   means for combining all cells with a dot character and a same start and end solid characters to construct extensible cells.   
     
     
         7 . The system of  claim 5 , wherein said means for assigning said significance comprises pruning by occurrences. 
     
     
         8 . The system of  claim 5 , wherein said means for assigning said significance comprises pruning by composition. 
     
     
         9 . A system for extracting an extensible motif from a sequence, said system comprising:
 a unit that assigns a significance, comprising a z-score, to an extensible motif within said sequence based upon a syntactic and statistical analysis; and   a unit that identifies an extensible motif having a significance that exceeds a predetermined threshold,   wherein said unit that assigns the significance comprises a device that restricts a computation of the z-score for each of said motifs to classes of maximal motifs.   
     
     
         10 . The system of  claim 9 , wherein the z-score comprises an extensible z-score.