Coincidence detection programmed media and system

Abstract

A method and system for detecting coincidences in a data set of objects, where each object has a number of attributes. Iteratively, equally-sized subsets of the data set of sampled, and coincidences (co-occurrences of a plurality of attribute values in one or more objects in the subset) are recorded. For each coincidence of interest, the expected coincidence count is determined and compared with the observed coincidence count; this comparison is used to determine a measure of correlation for the plurality of attributes for the coincidence. The resulting set ofk-tuples of correlated attributes is reported, a k-tuple of correlated attributes being a plurality of attributes for which the measure of correlation is above a predetermined threshold. The method and system (implemented on an array of processing nodes) is suitable for protein structure analysis, e.g. in HIV research.

1 . A coincidence detection method for use with a data set having a number of attributes, the method comprising the steps of: 
 representing a set of M objects in terms of a number N A  of variables (“attributes”), where an attribute is said to occur in an object if the object possesses the attribute;    sampling a subset of r i  out of the M objects, for each iteration among a predetermined number of iterations;    detecting and recording coincidences among sets of k of the attributes in each sampled subset of objects, a coincidence being the co-occurrence of 1≦k ≦ N   A  attributes in the same h i  out of r i  objects in the sampled subset, where 0≦h i ≦r i ,    determining an expected count of coincidences for any set of k attributes and a predetermined number of iterations of sampling and coincidence-counting as described above, the determining being performed before sampling and collecting, at the same time or after sampling and collecting;    comparing, for any set of k attributes and number of iterations of sampling and coincidence-counting, the observed count versus the expected count of coincidences, and from this comparison determining a measure of correlation (or association, or dependence) for the set of k attributes; and    reporting a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a set of k of the N A  attributes which have been determined by this process to have a value for a chosen correlation measure above a predetermined threshold value.    
     
     
         2 . A coincidence detection method for use with a data set of objects having a number of attributes, the method comprising the steps of 
 sampling a subset of the data set for a predetermined number of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes; detecting, and recording counts of, coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset of the data set being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording,    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence; and    reporting a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         3 . The coincidence detection method of  claim 2 , wherein the comparison of observed and expected counts is calculated using a Chernoff bound on tail probabilities.  
     
     
         4 . The coincidence detection method of  claim 2 , wherein the counts are recorded by storing a running total of the count of each coincidence over all of the sampled subsets  
     
     
         5 . A method for visual exploration of a data set of objects having a number of attributes, the method comprising the steps of. 
 sampling a subset of the data set for a predetermined number of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes;    detecting, and recording counts of, coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset of the data set being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording;    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence; and    reporting a set of k-tuples of correlated attributes to a user through a graphical interface, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         6 . A pre-processing method for use with a data modelling unit to capture and report to the data modelling unit higher order interactions of a data set of objects having a number of attributes, the method comprising the steps of sampling a subset of the data set for a predetermined number of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes; 
 detecting, and recording counts of, coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording;    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence; and    reporting to the data modelling unit a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         7 . A correlation elimination method for use with a data set of objects having a number of attributes, the method comprising the steps of. 
 sampling a subset of the data set for a predetermined number of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes;    detecting, and recording counts of, coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording;    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence; and    eliminating a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         8 . The method of  claim 2 , wherein the objects are sales transactions, each transaction comprising one or more purchased products, and the attributes are instances of sale of particular products or types of products.  
     
     
         9 . The method of  claim 2 , wherein the objects are time slices and the attributes are the status of elements in a system.  
     
     
         10 . The method of  claim 2 , wherein the objects are time slices and the attributes are prices, or price changes of, financial instruments or commodities.  
     
     
         11 . The method of  claim 2 , wherein the steps of the method are represented by the following pseudo-code 
 0. begin    1 read (MATRIX),    2. read (R, T);    3. compute_first_order_marginals(MATRIX);    4. csets :={};    5. for iter =1 to T do    6 sampled_rows :=rsample(R, MATRIX):    7. attributes :=get_attributes(sampled_rows);    8. all_coincidences :=find_all_coincidences(attributes);    9. for coincidence in all_coincidences do    10. if cset_already_exists(coincidence, csets)    11. then update_cset(coincidence, csets);    12. else add_new_cset(coincidence, csets);    13. endif    14. endfor    15. endfor    16. for cset in csets do    17. expected :=compute_expected_match_count(cset);    18. observed :=get_observed_match_count (set);    19. stats :=update_stats(cset, hypoth_test(expected, observed));    20. endfor    21. print_final_stats(csets, stats);    22. end.    
     
     
         12 . A coincidence detection system for use with a data set of objects, each object having a plurality of attributes, the system comprising: 
 means for sampling a subset of the data set for a predetermined number of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes;    means for detecting, and recording counts of, coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;    means for determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording;    means for comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence; and    means for reporting a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         13 . The coincidence detection system of  claim 12 , wherein the means of the system in the aggregate carry out a method represented by the following pseudo-code: 
 0. begin    1 read (MATRIX),    2. read (R, T);    3. compute_first_order_marginals(MATRIX);    4. csets :={};    5. for iter =1 to T do    6 sampled_rows :=rsample(R, MATRIX):    7. attributes :=get_attributes(sampled_rows);    8. all_coincidences :=find_all_coincidences(attributes);    9. for coincidence in all_coincidences do    10. if cset_already_exists(coincidence, csets)    11. then update_cset(coincidence, csets);    12. else add_new_cset(coincidence, csets);    13. endif    14. endfor    15. endfor    16. for cset in csets do    17. expected :=compute_expected_match_count(cset);    18. observed :=get_observed_match_count (set);    19. stats :=update_stats(cset, hypoth_test(expected, observed));    20. endfor    21. print_final_stats(csets, stats);    22. end.    
     
     
         14 . The coincidence detection system of  claim 12 , wherein the means for sampling a subset of the data set comprises means for dividing the data set into subsets for 
 sampling.    
     
     
         15 . The coincidence detection system of  claim 14 , wherein the means for detecting and recording counts of coincidences comprises an array of processing nodes, each processing node detecting and recording a respective subcount of coincidences, and wherein the means for comparing, for each coincidence of interest, said observed count of coincidences to said expected count of coincidences comprises means for merging said subcounts to provide said observed count.  
     
     
         16 . The coincidence detection system of  claim 15 , wherein at least one of said processing nodes comprises a respective subarray of processing nodes that detect and record respective subsubcounts of coincidences, and wherein said means for merging merges said subsubcounts to provide said subcounts and/or said observed count  
     
     
         17 . The coincidence detection system of  claim 15  or  16 , wherein each processing node comprises memory including an input buffer for storing received subsets of the data set and an output buffer for storing the subcount or the subsubcount; and a memory bus that transfers data to and from the memory.  
     
     
         18 . Coincidence detection programmed media for use with a computer and with a data set of objects having a number of attributes represented in a matrix of objects versus attributes, the programmed media comprising: 
 a computer program stored on storage media compatible with the computer, the computer program containing instructions to direct the computer to: 
 sample a subset of the data set for a predetermined number of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes;  
 detect and record counts of coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;  
 determine an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording;  
 compare, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determine a measure of correlation for the plurality of attributes for the coincidence; and  
 report a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold  
   
     
     
         19 . Coincidence detection system for use with a data set of objects having a number of attributes, the system comprising: 
 a computer; and    a computer program on media compatible with the computer, the computer program directing the computer to: 
 sample a subset of the data set for a predetermined number of iterations, each iteration the sampled subset having for each object the same subset of attributes,  
 detect, and record counts of, coincidences in each sampled subset-of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;  
 determine an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording,  
 compare, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determine a measure of correlation for the plurality of attributes for the coincidence, and  
 report a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.  
   
     
     
         20 . The coincidence method of  claim 2 , further comprising the step of representing the objects and attributes in a matrix of objects versus attributes prior to sampling the data set, the data set being sampled by sampling the matrix.  
     
     
         21 . A product having a set of attributes selected by: 
 sampling a subset of a data set representing objects versus attributes for a predetermined number of iterations, each iteration the sampled subset having for each object the same subset of attributes,    detecting, and recording counts of, coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets,    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording,    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence, and    reporting a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         22 . A product defined by applying a set of rules generated from: 
 sampling a subset of a data set representing objects versus attributes for a predetermined number of iterations, each iteration the sampled subset having for each object the same subset of attributes,    detecting and recording counts of coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the data set, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets,    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording,    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this    comparison determining a measure of correlation for the plurality of attributes for the coincidence, and    reporting a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         23 . A method comprising: 
 the method of  claim 2 , and the further step of:    applying rules that are defined by the reported correlated attributes.    
     
     
         24 . A peptide or peptidomimetic including a structural motif of the V3 loop of HIV envelope protien including spatial coordinates of residue A18/Q31/H×.  
     
     
         25 . A pharmaceutical composition comprising a ligand that interacts with a protein having a structural motif identified using the method of  claim 2 , and a pharmaceutically acceptable carrier or exicipient therefor.  
     
     
         26 . The pharmaceutical composition of  claim 25 , wherein the ligand comprises chemical moieties of suitable identity and spatially located relative to each other so that the moieties interact with corresponding residues or portions of the motif.  
     
     
         27 . The pharmaceutical composition of  claim 26 , wherein the ligand, by interacting with the motif, interferes with function of a region of the protein comprising the motif.  
     
     
         28 . An diagnostic agent comprising a ligand that interacts with a protein having a structural motif identified using the method of  claim 2 , and a detectable label linked to the ligand.  
     
     
         29 . A pharmaceutical composition for interacting with an envelope protein of human immunodeficiency virus (HIV), the envelope protein including a structural motif of the V3 loop having spatial coordinates of residues A18/Q31/H33, comprising a ligand including at least one functional group that interacts with the motif, and a pharmaceutically acceptable carrier or exicipient therefor.  
     
     
         30 . The pharmaceutical composition of  claim 29 , wherein the ligand includes at least one functional group capable of binding to and being present in an effective position in said ligand to bind to residue 18, at least one functional group capable of binding to and being present in an effective position in said ligand to bind to residue 31, and at least one functional group capable of binding to and being present in an effective position in said ligand to bind to residue 33.  
     
     
         31 . A method of designing a ligand to interact with a structural motif of an envelope protein of human immunodeficiency virus (HIV), the method comprising the steps of: providing a template having spatial coordinates of residues A18, Q31 and H33 in the V3 loop of HIV envelope protein, and computationally evolving a chemical ligand using an effective algorithm with spatial constraints, so that said evolved ligand includes at least one effective functional group that binds to the motif.  
     
     
         32 . The method of  claim 31 , wherein the ligand comprises: at least one functional group capable of binding to and being present in an effective position in said ligand to bind to residue 18, at least one functional group capable of binding to and being present in an effective position in said ligand to bind to residue 31, and at least one functional group capable of binding to and being present in an effective position in said ligand to bind to residue 33  
     
     
         33 . A method of identifying a ligand to bind with a structural motif of an envelope protein of human immunodeficiency virus (HIV), the method comprising the steps of providing a template having spatial coordinates of A18, Q31 and H33 in the V3 loop of HIV envelope protein; providing a data base containing structure and orientation of molecules; and screening said molecules to determine if they contain effective moieties spaced relative to each other so that the moieties interact with the motif  
     
     
         34 . The method of  claim 33 , wherein a first moiety of the molecule interacts with residue 18, a second moiety of the molecule interacts with residue 31 and a third moiety of the molecule interacts with residue 33.  
     
     
         35 . Antigens and vaccines embodying the covarying k-tuples described herein.  
     
     
         36 . A product being defined by its interaction with a set of attributes selected by: sampling a subset of a data set representing objects versus attributes for a predetermined number of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes, 
 detecting, and recording counts of, coincidences in each sampled subset of the data set, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets,    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording,    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence, and    reporting a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a pre-determined threshold    
     
     
         37 . The method of  claim 2 , wherein the objects are compounds and the attributes comprise particular chemical moieties  
     
     
         38 . The method of  claim 2 , wherein the objects are peptides or proteins and the attributes comprise particular structural or substructural patterns or motifs.  
     
     
         39 . The method of  claim 2 , wherein the objects are selected from the group consisting of compounds, molecular structures, nucleotide sequences and amino acid sequences and the attributes are features of the selected objects.  
     
     
         40 . The method of  claim 2 , wherein the objects are time slices and the attributes are biological parameters of genes or gene products.  
     
     
         41 . The method of  claim 2 , wherein the objects are documents that are electonically stored and/or electronically indexed and the attributes are topics.  
     
     
         42 . The method of  claim 2 , wherein the objects are customers and the attributes comprise products purchased or not purchased by those customers.  
     
     
         43 . The method of  claim 42 , wherein the attributes further comprise mailings made or not made to the customers.  
     
     
         44 . The method of  claim 2 , wherein the objects comprise products and the attributes comprise customers that have or have not purchased those products.  
     
     
         45 . The method of  claim 44 , wherein the attributes further comprise demographic variables of the customers  
     
     
         46 . The method of  claim 2 , wherein the objects are people with a particular disease or discorder and the attributes are potential contributing factors for the disease or disorder.  
     
     
         47 . The method of  claim 2 , wherein the objects are people with a number of different diseases or disorders and the attributes are potential contributing factors for the diseases or disorders.  
     
     
         48 . The method of  claim 2 , wherein the objects comprise factors potentially contributing to a disease or disorder and the attributes are people with or without those factors, wherein the method associates groups of people of substantially equivalent risk for the disease or disorder.  
     
     
         49 . The method of  claim 2 , wherein the objects are time slices and the attributes comprise the state of components in a system at time slices prior to failure of the system, wherein the method associates component states that may potentially cause failure of the system.  
     
     
         50 . The coincidence detection method of  claim 1 , where r i  is the same for every iteration.  
     
     
         51 . The method of  claim 2 , further comprising the steps of first creating a database of transitions between system states, wherein a system state is represented by a value of a state variable, over a chosen time quantum, and presenting the database, in whole or part, as a data set such that each state to state transition set corresponds to one of M objects and so that each state variable corresponds to an attribute.  
     
     
         52 . The method of  claim 2 , further comprising the steps of first creating a database of states and actions covering a chosen time quantum and presenting the database, in whole or part, as a data set such that each state/action/state triple corresponds to one of M objects and so that each state variable or action type corresponds to an attribute  
     
     
         53 . A coincidence detection method for use with a data set of objects having a number of attributes represented in a matrix of objects versus attributes, the method comprising the steps of: 
 sampling a subset of the matrix for a predetermined number of iterations, each iteration the sampled subset of the matrix having for each object the same subset of attributes;    detecting, and recording counts of, coincidences in each sampled subset of the matrix, a coincidence being the co-occurrence of a plurality of attribute values in one or more objects in a sampled subset of the matrix, where the plurality of attribute values is the same for each occurrence, the detecting and recording counts of coincidences in each sampled subset being performed before, at the same time or after sampling, detecting and recording counts of coincidences in other subsets;    determining an expected count for each coincidence of interest, the determining being performed before, at the same time, or after sampling, detecting and recording;    comparing, for each coincidence of interest, the observed count of coincidences versus the expected count of coincidences, and from this comparison determining a measure of correlation for the plurality of attributes for the coincidence, and    reporting a set of k-tuples of correlated attributes, where a k-tuple of correlated attributes is a plurality of attributes for which the measure of correlation is above a respective pre-determined threshold.    
     
     
         54 . The method of  claim 1 , wherein numerical correlation values are reported along with the set of k-tuples of correlated attributes.