Unsupervised Building and Exploitation of Composite Descriptors

Abstract

Generally, the present invention provides a way of determining in an unsupervised manner additional members for a family that is defined initially through exemplar sequences. The present invention is unsupervised in that it proceeds without any information related to the exemplar sequences defining the family, without aligning the sequences, without prior knowledge of any patterns in the exemplar sequences, and without knowledge of the cardinality or characteristics of any features that may be present in the exemplar sequences. In one aspect of the invention, a method is used to take a set of unaligned sequences and discover several of many patterns common to some or all of the sequences. These patterns can then be used to determine if candidate sequences are members of the family. In another aspect of the invention, a method is used to take a set of sequences and to determine a set of maximal patterns common to a number of sequences The maximal patterns are determined without any previous knowledge about any properties of features that may be present in the processed sequences.

1 . A method for unsupervised building and exploitation of composite descriptors, the method comprising the steps of; 
 i. providing a training set of sequences, each sequence comprising a plurality of symbols;    ii determining a set of maximal patterns, each of the maximal patterns being common to a predetermined number of the sequences, wherein the step of determining a set of maximal patterns is performed without any knowledge about properties or features of sequences in the set of unaligned sequences;    iii determining which, if any, of the maximal patterns are statistically significant; and    iv creating a composite descriptor from the statistically significant maximal patterns.    
   
   
       2 . The method of  claim 1 , wherein the sequences in the training set are unaligned.  
   
   
       3 . The method of  claim 1 , wherein the step of creating a composite description from the statistically significant maximal patterns further comprises the steps determining which of the statistically significant maximal patterns are currently not part of the composite descriptor, adding those statistically significant maximal patterns that are currently not part of the composite descriptor to the composite descriptor, and removing the added statistically significant maximal patterns from the training set of sequences.  
   
   
       4 . The method of  claim 3 , wherein each symbol comes from an alphabet that describes DNA (deoxyribonucleic acid) or proteins.  
   
   
       5 . The method of  claim 1 , wherein the symbols are numerical.  
   
   
       6 . The method of  claim 3 , further comprising the steps of iterating steps (ii) through (iv) until either the training set contains no sequences or there are no statistically significant maximal patterns common to the sequences in the training set.  
   
   
       7 . The method of  claim 3 , further comprises the step of determining if a candidate sequence comprises a predetermined number of the statistically significant maximal patterns.  
   
   
       8 . The method of  claim 7 , comprising the steps of if the candidate sequence comprises the predetermined number of the statistically significant maximal patterns, adding the candidate sequence to the set of sequences to create a new training set of sequences and performing the steps (ii) through (iv) on the new training set of sequences.  
   
   
       9 . The method of  claim 1 , wherein the step of determining which, if any, of the maximal patterns ate statistically significant comprises the step of determining for each of the maximal patterns if a probability that this maximal pattern occurs in a sequence meets a predetermined threshold.  
   
   
       10 . The method of  claim 1 , wherein the set of maximal patterns is empty and wherein the step of determining a set of maximal patterns further comprises the steps of reducing the predetermined number of sequences and performing step (ii) again.  
   
   
       11 . A system for unsupervised building and exploitation of composite descriptors, comprising: 
 a memory that stores computer-readable code; and    a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to; 
 i. provide a training set of sequences, each sequence comprising a plurality of alphabetic symbols;  
 ii. determine a set of maximal patterns, each of the maximal patterns being common to a predetermined number of the sequences, wherein the maximal patterns are determined without any knowledge about properties or features of sequences in the set of unaligned sequences;  
 iii. determine which, if any, of the maximal patterns are statistically significant; and  
 iv. create a composite descriptor from the statistically significant maximal patterns  
   
   
   
       12 . An article of manufacture for unsupervised building and exploitation of composite descriptors, comprising: 
 a computer readable medium having computer readable code means embodied thereon, said computer readable program code means comprising; 
 a step to provide a training set of sequences, each sequence comprising a plurality of alphabetic symbols;  
 a step to determine a set of maximal patterns, each of the maximal patterns being common to a predetermined number of the sequences, wherein the maximal patterns are determined without any knowledge about properties or features of sequences in the set of unaligned sequences;  
 a step to determine which, if any, of the maximal patterns are statistically significant; and  
 a step to create a composite descriptor from the statistically significant maximal patterns.