Patent JPS57112243A successfully refreshed from Google Patents.
Patent US6493637B1 successfully refreshed from Google Patents.
US6493637B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Coincidence detection method, products and apparatus
Assignee: Queen's University
•
Filing: 1999-09-24
•
Granted: 2002-12-10
•
Expires: 2019-09-24
Abstract
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 of k-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.
Inventors
- 👤 Evan W. Steeg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:22
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/205; G06F40/216; G16; G16B; G16B40/00; A; A61; A61P; A61P31/00; A61P31/12; A61P31/14; A61P31/18; G06F40/279; G16B15/00; G16B15/20; G16B30/00; G16B30/10; G16B40/20; G16C; G16C20/00; G16C20/50
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
222 words
A coincidence detection method for use with a data set of objects, said objects having a number of attributes, the method comprising the steps of: sampling various subsets of the data set for a plurality 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 that has been detected in the previous step; 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.
Claim 2
Dependent Claim
222 words
A coincidence detection method for use with a data set of objects, said objects having a number of attributes, the method comprising the steps of: sampling various subsets of the data set for a plurality 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 that has been detected in the previous step; 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.
Claim 3
Dependent Claim
25 words
The coincidence detection method of claim 1 , wherein the comparison of observed and expected counts is calculated using a Chernoff bound on tail probabilities.
Claim 4
Dependent Claim
30 words
The coincidence detection method of claim 1 , wherein the counts are recorded by storing a running total of the count of each coincidence over all of the sampled subsets.
Claim 5
Dependent Claim
96 words
The method of claim 1 , 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(cset); 19. stats: =update_stats(cset, hypoth_test(expected, observed)); 20. endfor 21. print_final_stats(csets, stats); 22. end.
Claim 6
Dependent Claim
39 words
The coincidence method of claim 1 , 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.
Claim 7
Dependent Claim
24 words
A method comprising: the method of claim 1 , and the further step of: applying rules that are defined by the reported correlated attributes.
Claim 8
Dependent Claim
74 words
The method of claim 1 , 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 the objects and so that each state variable corresponds to an attribute.
Claim 9
Dependent Claim
60 words
The method of claim 1 , 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 the objects and so that each state variable or action type corresponds to an attribute.
Claim 10
Dependent Claim
38 words
The method of claim 1 , wherein at least one of the objects corresponds to a biological sample from a subject and at least one of the attributes corresponds to a biological parameter of genes or gene products.
Claim 11
Dependent Claim
18 words
The method of claim 9 , wherein at least one of the attributes corresponds to a phenotypic aspect.
Claim 12
Dependent Claim
19 words
The method of claim 9 , wherein at least one of the attributes corresponds to expression of a gene.
Claim 13
Dependent Claim
18 words
The method of claim 11 , wherein the expression of at least one gene is measured by mRNA.
Claim 14
Dependent Claim
19 words
The method of claim 11 , wherein the expression of at least one gene is measured by protein product.
Claim 15
Dependent Claim
37 words
The method of claim 9 , wherein at least some of the objects correspond to biological samples from a single subject collected over time and at least one of the attributes corresponds to expression of a gene.
Claim 16
Dependent Claim
18 words
The method of claim 14 , wherein the expression of at least one gene is measured by mRNA.
Claim 17
Dependent Claim
19 words
The method of claim 14 , wherein the expression of at least one gene is measured by protein product.
Claim 18
Dependent Claim
17 words
The method of claim 1 , wherein said plurality of iterations is a predetermined number of iterations.
Claim 19
Dependent Claim
112 words
A coincidence detection method for use with a data set of objects, each of the objects having at least one attribute, the method comprising the steps of: (1) sampling various subsets of the data set for a plurality of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes; (2) detecting attribute coincidences based on results of sampling of the data set; (3) recording attribute coincidences; and (4) comparing at least one recorded attribute coincidence count to at least one expected attribute coincidence count, wherein the expected attribute coincidence count is determined for a coincidence that has been detected in the preceding steps.
Claim 20
Dependent Claim
112 words
A coincidence detection method for use with a data set of objects, each of the objects having at least one attribute, the method comprising the steps of: (1) sampling various subsets of the data set for a plurality of iterations, each iteration the sampled subset of the data set having for each object the same subset of attributes; (2) detecting attribute coincidences based on results of sampling of the data set; (3) recording attribute coincidences; and (4) comparing at least one recorded attribute coincidence count to at least one expected attribute coincidence count, wherein the expected attribute coincidence count is determined for a coincidence that has been detected in the preceding steps.
Claim 21
Dependent Claim
23 words
The method of claim 18 , the method further comprising the step of: (5) reporting attribute coincidences based on result of said comparison.
Claim 22
Dependent Claim
23 words
The method of claim 19 , the method further comprising the step of applying rules that are defined by the reported attribute coincidences.
Claim 23
Dependent Claim
28 words
The method of claim 19 , wherein step (5) comprises the step of reporting at least one numerical correlation value and at least one k-tuple of correlated attributes.
Claim 24
Dependent Claim
21 words
The method of claim 18 , wherein the objects and the attributes of the data set are represented in a matrix.
Claim 25
Dependent Claim
21 words
The method of claim 18 , the method further comprising the step of separating the data set into subsets for sampling.
Claim 26
Dependent Claim
27 words
The method of claim 18 , wherein more than one subset of objects is sampled and the size of the subsets of objects sampled is a constant.
Claim 27
Dependent Claim
27 words
The method of claim 18 , wherein the comparison of the recorded attribute coincidences to said expected count is done using a Chernoff bound on tail probabilities.
Claim 28
Dependent Claim
29 words
The method of claim 18 , wherein step (3) comprises the step of storing a running total of counts of each attribute coincidence detected over all the subsets sampled.
Claim 29
Dependent Claim
39 words
The method of claim 18 , wherein at least one of the objects corresponds to a biological sample from a subject and at least one of the attributes corresponds to a biological parameter of a gene or gene product.
Claim 30
Dependent Claim
18 words
The method of claim 27 , wherein at least one of the attributes corresponds to a phenotypic aspect.
Claim 31
Dependent Claim
19 words
The method of claim 27 , wherein at least one of the attributes corresponds to expression of a gene.
Claim 32
Dependent Claim
18 words
The method of claim 29 , wherein the expression of at least one gene is measured by mRNA.
Claim 33
Dependent Claim
19 words
The method of claim 29 , wherein the expression of at least one gene is measured by protein product.
Claim 34
Dependent Claim
37 words
The method of claim 27 , wherein at least some of the objects correspond to biological samples from a single subject collected over time and at least one of the attributes corresponds to expression of a gene.
Claim 35
Dependent Claim
18 words
The method of claim 32 , wherein the expression of at least one gene is measured by mRNA.
Claim 36
Dependent Claim
19 words
The method of claim 32 , wherein the expression of at least one gene is measured by protein product.
Claim 37
Dependent Claim
50 words
The method of claim 18 , wherein at least one of the objects corresponds to a subject and at least some of the attributes correspond to the subjects' genes or gene expression patterns and the presence of a particular drug side-effect or side-effects after having been administered a particular drug.
Claim 38
Dependent Claim
52 words
The method of claim 18 , wherein at least one of the objects corresponds to a subject and at least some of the attributes correspond to the subjects' genes or gene expression patterns and the presence of a particular drug side-effect or side-effects after having been administered a particular combination of drugs.
Claim 39
Dependent Claim
45 words
The method of claim 18 , wherein at least one of the objects corresponds to a subject and at least some of the attributes correspond to the subjects' genes or gene expression patterns and the response of the subject to treatment using a particular drug.
Claim 40
Dependent Claim
47 words
The method of claim 18 , wherein at least one of the objects corresponds to a subject and at least some of the attributes correspond to the subjects' genes or gene expression patterns and the response of the subject to treatment using a particular combination of drugs.
Claim 41
Dependent Claim
17 words
The method of claim 18 , wherein said plurality of iterations is a predetermined number of iterations.
References Cited (Backward Citations)
GB2283840A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-12-09 | 2006-06-10 | 2006-12-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-12-09 | 2010-06-10 | 2010-12-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-12-09 | 2014-06-10 | 2014-12-10 | $7700.00 | Window Closed / Lapsed |