Fast microarray expression data analysis method for network exploration

Abstract

A method for performing network reconstruction is provided. The method includes the steps of selecting a predictor set of features, adding a complement to the predictor set based on a quality of prediction, checking to see if all of the features of the predictor set are repeated, and then removing one feature from the predictor set. The algorithm and method repeat the steps of adding a complement, checking the predictor set and removing a feature until the features of the predictor set are repeated. If the features of the predictor set are repeated, the algorithm and method terminate.

1 . A method of network reconstruction comprising: 
 (a) selecting a target;    (b) selecting a predictor set of features;    (c) adding at least one complement to said predictor set based on a quality of prediction;    (d) checking to see if all of said features are repeated; and    (e) removing at least one feature from said predictor set; and    as a result of performing each of steps (a)-(e) at least once, reconstructing a network.    
   
   
       2 . A method as recited in  claim 1 , wherein said target can be changed and subsets of targets can be formed for predicting other associated predictor sets of features.  
   
   
       3 . A method as recited in  claim 1 , further comprising repeating steps (e), (c) and then (d) until determined in step (d) that all of said features of said predictor set have been repeated k times in a row, wherein k corresponds to the number of features in the predictor set.  
   
   
       4 . A method as recited in  claim 3 , wherein said predictor set of features is compared to other associated predictor sets to determine associated pathways that are used in network reconstruction.  
   
   
       5 . A method as recited in  claim 3 , wherein said predictor set of features is compared to other non-associated predictor sets to determine associated pathways that are used in network reconstruction.  
   
   
       6 . A method a recited in  claim 3 , wherein said predictor set is used in determining clusters.  
   
   
       7 . A method as recited in  claim 3 , wherein said k features of the predictor set are ordered; and wherein said feature that is removed from said predictor set is the first feature in the ordered predictor set.  
   
   
       8 . A method as recited in  claim 1 , wherein said selecting step comprises: 
 selecting k−1 number of features at random, wherein k is a number greater than 1.    
   
   
       9 . A method as recited in  claim 1 , wherein said features of said predictor set are selected in a defined order.  
   
   
       10 . A method as recited in  claim 1 , wherein said feature that is removed from said predictor set in step (d) is the earliest feature defined in the ordered predictor set.  
   
   
       11 . A method as recited in  claim 1 , wherein the predictor set and target are vectors in M-dimensional space, wherein M is a number greater than or equal to 1.  
   
   
       12 . A method as recited in  claim 1 , wherein said selected predictor set has a size of between 1-1000 features.  
   
   
       13 . A method as recited in  claim 1 , wherein said steps of selecting and adding are performed by a processor-based device using a first algorithm, and wherein said checking step is performed by a separate algorithm.  
   
   
       14 . The method of  claim 1  wherein said selecting step comprises selecting k−1 features associated with said target to include in said predictor set, wherein k is a number greater than 1.  
   
   
       15 . The method of  claim 14  wherein said adding step comprises adding a complement to said k−1 features to form a predictor set of k features.  
   
   
       16 . The method of  claim 15  wherein said checking step comprises checking to see if all of said k features of said predictor set have been repeated k times in a row.  
   
   
       17 . The method of  claim 16  wherein said removing step comprises: 
 if determined in step (d) that all of said k features of said predictor set have not been repeated k times in a row, removing a feature from said predictor set in step (e) and returning to step (c).    
   
   
       18 . The method of  claim 17  further comprising: 
 (f) if determined in step (d) that all of said k features of said predictor set have been repeated k times in a row, then determining such predictor set as a best predictor set of k features for predicting the presence of said target.    
   
   
       19 . The method of  claim 18  further comprising: 
 ordering the k−1 subset of features in a list.    
   
   
       20 . The method of  claim 19  wherein said adding said complement to said subset comprises: 
 adding said complement to one end of said list.    
   
   
       21 . The method of  claim 20  wherein said removing said feature from said predictor set comprises: 
 removing said feature from the other end of said list.    
   
   
       22 . The method of  claim 18  further comprising: 
 determining whether the determined best predictor set of k features for predicting the presence of said target satisfies a predetermined threshold for quality of prediction.    
   
   
       23 . The method of  claim 22  wherein if determined that the best predictor set of k features for predicting the presence of said target does not satisfy said predetermined threshold, then incrementing the value of k.  
   
   
       24 . The method of  claim 23  further comprising: 
 repeating steps (a)-(f) for the incremented value of k.    
   
   
       25 . The method of  claim 22  if determined that the best predictor set of k features for predicting the presence of said target does not satisfy said predetermined threshold, performing the following: 
 (g) selecting the determined best predictor set of k features; and    (h) adding at least one complement feature to said k features to form a new predictor set of k+1 features.    
   
   
       26 . The method of  claim 25  further comprising: 
 (i) checking to see if all of said k+1 features of said new predictor set have been repeated k+1 times in a row;    if determined in step (i) that all of said k+1 features of said new predictor set have not been repeated k+1 times in a row, removing at least one feature from said new predictor set and returning to step (g); and    (k) if determined in step (i) that all of said k+1 features of said new predictor set have been repeated k+1 times in a row, then determining such new predictor set as a best predictor set of k+1 features for predicting the presence of said target.    
   
   
       27 . The method of  claim 26  further comprising: 
 determining whether the determined best predictor set of k+1 features for predicting the presence of said target satisfies said predetermined threshold for quality of prediction.    
   
   
       28 . The method of  claim 1  wherein each of said features comprises corresponding measurement data.  
   
   
       29 . The method of  claim 1  wherein said target is a multiple dependency.  
   
   
       30 . The method of  claim 1  wherein said target is an associated pathway.  
   
   
       31 . Computer software, embodied on a computer-readable medium, and operable for performing network reconstruction, comprising an algorithm that performs the steps of: 
 (a) selecting a target;    (b) selecting a predictor set of features;    (c) adding a complement to said predictor set based on a quality of prediction;    (d) checking to see if all of said features are repeated; and    (e) removing one feature from said predictor set; and    as a result of performing each of steps (a)-(d) at least once, reconstructing a network.    
   
   
       32 . Computer software as recited in  claim 31 , wherein any of said steps of said algorithm are user defined.  
   
   
       33 . Computer software as recited in  claim 31 , wherein any of said steps of said algorithm are software defined.  
   
   
       34 . A method as recited in  claim 31 , further comprising repeating steps (e), (c) and then (d) until determined in step (d) that all of said features of said predictor set have been repeated k times in a row, wherein k corresponds to the number of features in the predictor set.  
   
   
       35 . The method of  claim 34  wherein said removing step comprises: 
 if determined in step (d) that all of said k features of said predictor set have not been repeated k times in a row, removing a feature from said predictor set in step (e) and returning to step (c).    
   
   
       36 . The method of  claim 35  further comprising: 
 (f) if determined in step (d) that all of said k features of said predictor set have been repeated k times in a row, then determining such predictor set as a best predictor set of k features for predicting the presence of said target.    
   
   
       37 . A system for performing network reconstruction, comprising: 
 (a) a computer; and    (b) computer software, embodied on a computer-readable medium, and executable by said computer for performing network reconstruction according to the steps of:    (i) selecting a predictor set of features;    (ii) adding a complement to said predictor set based on a quality of prediction;    (iii) checking to see if all of said features are repeated; and    (iv) removing one feature from said predictor set.    
   
   
       38 . A method as recited in  claim 37 , further comprising repeating steps (e), (c) and then (d) until determined in step (d) that all of said features of said predictor set have been repeated k times in a row, wherein k corresponds to the number of features in the predictor set.  
   
   
       39 . The method of  claim 38  wherein said removing step comprises: 
 if determined in step (d) that all of said k features of said predictor set have not been repeated k times in a row, removing a feature from said predictor set in step (e) and returning to step (c).    
   
   
       40 . The method of  claim 39  further comprising: 
 (f) if determined in step (d) that all of said k features of said predictor set have been repeated k times in a row, then determining such predictor set as a best predictor set of k features for predicting the presence of said target.    
   
   
       41 . A method of network reconstruction comprising: 
 selecting k−1 subset of features associated with a target;    ordering the k−1 subset of features in a list;    adding to one end of the list a complement feature to form a predictor set of k features;    determining whether the features of the predictor set have appeared k consecutive times;    if the features of the predictor set have not appeared k consecutive times, then removing a feature from the other end of the list;    if the features of the predictor set have appeared k consecutive times, then determining that the predictor set is a best predictor set of k features for predicting the presence of said target; and    using the determined best predictor set of k features for predicting the presence of said target.    
   
   
       42 . The method of  claim 38  further comprising: 
 adding a second complement feature to the one end of the list.    
   
   
       43 . The method of  claim 38  further comprising: 
 repeating said adding, determining, and removing steps until said determining step determines a predictor set of features that have appeared k consecutive times.    
   
   
       44 . The method of  claim 41  further comprising: 
 using the determined best predictor set of k features to determine the association of multiple dependencies.    
   
   
       45 . A method of network reconstruction comprising: 
 (a) selecting a subset of (k−x) features associated with a target, k being a number greater than 1 and x being a number greater than 0 and less than k;    (b) adding x complement features to said subset to form a predictor set of k features;    (c) checking to see if all of said k features of said predictor set have been repeated k times in a row;    (d) if determined in step (c) that all of said features of said predictor set have not been repeated k times in a row, removing at least one feature from said predictor set and returning to step (b); and    (e) if determined in step (c) that all of said features of said predictor set have been repeated k times in a row, then determining such predictor set as a best predictor set of k features for predicting said target.    
   
   
       46 . The method of  claim 45  further comprising: 
 using the determined best predictor set of k features to determine the association of multiple dependencies.    
   
   
       47 . The method of  claim 45  wherein if determined that using the best predictor set of k features to determine the association of multiple dependencies does not satisfy a predetermined quality of prediction threshold, then incrementing the value of k.  
   
   
       48 . The method of  claim 45  wherein said target is a multiple dependency.  
   
   
       49 . The method of  claim 45  wherein said target is an associated pathway.