Pattern Discovery Techniques for Determining Maximal Irredundant and Redundant Motifs

Abstract

Basis motifs are determined from an input sequence through an iterative technique that begins by creating small solid motifs and continues to create larger motifs that include “don't care” characters and that can include flexible portions. The small solid motifs, including don't care characters and flexible portions, are concatenated to create larger motifs. During each iteration, motifs are trimmed to remove redundant motifs and other motifs that do not meet certain criteria. The process is continued until no new motifs are determined. At this point, the basis set of motifs has been determined. The basis motifs are used to construct redundant motifs that are formed by determining sets for selected basis motifs. From these sets, unique intersection sets are determined. This process continues, by selecting additional basis motifs, until all basis motifs have been selected. An apparatus for performing the process is also disclosed.

1 . A method for determining flexible motifs for use in pattern discovery on an input sequence comprising a plurality of elements, the method comprising the steps of:
 determining a plurality of first flexible motifs from the input sequence, each first flexible motif comprising at least one element from the input sequence; and   combining each of the plurality of first flexible motifs with another of the plurality of first flexible motifs to create a plurality of combined flexible motifs;   
     
     
         2 . The method of  claim 1 , further comprising a step of selecting motifs of the combined flexible motifs and the plurality of first flexible motifs for removal based on at least one predetermined criteria. 
     
     
         3 . The method of  claim 1 , further comprising a step of removing suffix motifs in the combined flexible motifs and the first flexible motifs. 
     
     
         4 . The method of  claim 3 , further comprising a step of removing redundant motifs in the combined flexible motifs and the first flexible motifs. 
     
     
         5 . The method of  claim 4 , wherein each motif in the combined flexible motifs and the first flexible motifs has an associated location list, and wherein the step of removing redundant motifs comprises the steps of:
 determining any motif whose location list is a union of other location lists associated with motifs in the combined flexible motifs and the first flexible motifs; and   removing any motif whose location list is a union of other location lists associated with motifs in the combined flexible motifs and the first flexible motifs.   
     
     
         6 . The method of  claim 3 , further comprising a step of removing selected motifs in the combined flexible motifs and the first flexible motifs if the selected motifs do not occur in the combined flexible motifs and the first flexible motifs more than a predetermined number of times. 
     
     
         7 . The method of  claim 1 , further comprising a step of removing one or more flexible motifs of the concatenated flexible motifs and the first flexible motifs; and
 performing the steps of combining and removing until no new motifs are generated by said combining and removing steps.   
     
     
         8 . The method of  claim 1 , wherein:
 each first flexible motif is a solid element motif;   the step of determining a plurality of first flexible motifs comprises the steps of:
 determining a plurality of solid element motifs, each solid element motif comprising at least one element from the input sequence; and 
 creating a plurality of second flexible motifs by adding at least one don't care element to each of the solid element motifs; 
   the step of combining further comprises the steps of:
 selecting a motif from the solid element and second flexible motifs; 
 combining the selected motif with another selected motif from the solid element and second flexible motifs; and 
   performing the process of selecting and combining until each motif from the solid element and second flexible motifs has been combined with another motif from the solid element and second flexible motifs;   the method of  claim 1  further comprises the steps of:
 trimming the solid element, second flexible, and combined flexible motifs; and 
 performing the steps of combining and trimming until no new motifs are generated by said combining and trimming steps. 
   
     
     
         9 . The method of  claim 1 , wherein each element of the input sequence comprises a character from an alphabet. 
     
     
         10 . The method of  claim 1 , wherein at least one element of the input sequence comprises a set of characters. 
     
     
         11 . The method of  claim 1 , wherein each element of the input sequence comprises a real number. 
     
     
         12 . The method of  claim 7 , wherein one or more motifs of the combined flexible motifs and the first flexible motifs that remain following said removing step from a basis set of motifs and wherein the method further comprises the steps of:
 determining a plurality of motif sets from a plurality of selected motifs, the selected motifs selected from a plurality of basis motifs, wherein the plurality of selected motifs all begin with a selected element;   determining unique intersection sets from the plurality of motif sets; and   determining redundant motifs from the intersection sets and the motif sets.   
     
     
         13 . A computer system for pattern discovery on an input sequence comprising a plurality of elements, comprising:
 a memory that stores computer-readable code;   a processor operatively coupled to the memory, the processor configured to implement the computer-readable code, the computer readable code configured to:   determine a plurality of first flexible motifs from the input sequence, each first flexible motif comprising at lease one element from the input sequence; and   combine each of the plurality of first flexible motifs with another of the plurality of first flexible motifs to create a plurality of combined flexible motifs.   
     
     
         14 . An article of manufacture for pattern discovery on an input sequence comprising a plurality of elements, comprising:
 a machine readable medium containing one or more programs which when executed implement the steps of:   determining a plurality of first flexible motifs from the input sequence, each first flexible motif comprising at least one element from the input sequence; and   combining each of the plurality of first flexible motifs with another of the plurality of first flexible motifs to create a plurality of combined flexible motifs.