Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-08-05
2002-07-16
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06421668
ABSTRACT:
TECHNICAL FIELD
The present invention relates to methods and systems for partitioning, or clustering, data into subsets of related data and, in particular, to a method and system for projecting a graph onto a clique graph that has applications in clustering gene expression patterns, methylation profiles, hybridization signals, and other types of experimental and observational data in scientific and technical fields and in economics.
BACKGROUND OF THE INVENTION
A frequently encountered problem in processing data generated by scientific experimentation and scientific and economic observation is that of partitioning data into related data subsets. For example, stock market analysts attempt to identify groups of stocks that rise and fall in price together in response to various cycles and trends. The observed data are the prices of each stock over a period of time, and the partitioning, or clustering, problem is one of grouping the stocks into related subsets of stocks that exhibit similar price behaviors. As another example, molecular biologists use large molecular arrays to monitor the expressions of genes in organisms over time and in response to various biological perturbations. One object in such studies is to identify groups, or clusters, of genes that all have similar expression patterns. Often, indications of the function of a gene product can be gleaned from determining that the expression of the corresponding gene is similar to the expression of a known gene. For example, an unknown gene that is always expressed immediately following expression of the p53 gene may indicate that the unknown gene product is somehow related to apoptosis.
The general class of problems exemplified in the previous paragraph is referred to as cluster analysis. The goal of cluster analysis is to partition entities into groups, called clusters, so that clusters are homogeneous and well-separated. There is an extensive literature on cluster analysis going back over two decades, including, the following three titles: (1) R. O. Duda and P. E. Hart,
Pattern classification and scene analysis
, Wiley-interscience, NY, 1973; (2) B. Everitt,
Cluster Analysis
, Edward Arnold, London, Third Edition, 1993; and (3) B. Mirkin,
Mathematical classification and clustering
, Kluwer Academic Publishers, 1996. There are many different approaches to defining desirable solutions to cluster analysis and for interpreting those solutions, and there are many different types of clustering that may be identified by clustering analysis. Most formulations of the problem yield NP hard problems. Therefore, many of the approaches emphasize heuristics and approximation. Many of the approaches to cluster analysis, particularly in the field of clustering gene expression patterns, utilize hierarchical methods in which phylogenetic trees are constructed using Euclidean distance metrics for evaluating the relatedness of the different expression patterns of various genes. Euclidean distance metrics are but a small subset of relatedness metrics that might be employed in clustering data, but clustering methods often depend on using a particular type of metric. In many of these approaches, prior assumptions concerning the nature of underlying clustering within the data are required in order to constrain a search for clusters. Many of these methods may often converge on local minima, rather than identifying the most optimal clustering patterns within the data according to some predefined measure of optimality.
Scientists, economists, and data analysts have therefore recognized the need for a method and system that can be applied to data in order to partition the data into related subsets, where the relatedness of the data can be specified by arbitrary methods. In addition, the need for an efficient method for identifying clustering within data that does not rely on prior assumptions about the data, including such things as the maximum number of clusters, a preferred cluster size, and other such constraints, has been recognized. Moreover, scientists, economists, and data analysts have recognized the need for an algorithm that has a high probability of determining an optimal or near-optimal partitioning of data into related data sets, rather than too quickly converging on less-than-optimal partitionings.
SUMMARY OF THE INVENTION
The present invention provides a method and system for partitioning data into related data subsets. In one embodiment of the present invention, the method and system takes,as inputs, a data set, a similarity matrix that specifies the relatedness of the data points, or entities within the data set, and a cutoff value that divides relatedness values into low affinity relatedness values and high affinity relatedness values. The method and system iteratively constructs successive clusters of related data subsets until all data points, or entities, are assigned to a cluster. Initially, all the data points, or entities, are unassigned. Unassigned data points are candidates for assignment to a cluster that is being constructed in a given iterative step. During each iterative step, data points assigned to the currently constructed cluster may be removed from the cluster and returned to the pool of candidates. During each iterative step, the method and system may alternate between choosing high affinity candidates and assigning them to the currently constructed cluster, and removing data points from the currently constructed cluster and returning the removed data points to the candidate pool.
Because the relatedness criteria are input as a similarity matrix, the method and system representing this embodiment of the present invention makes no assumptions or reliance on the metrics employed to generate the relatedness criteria. This embodiment of the present invention does not require specification of any additional constraints, such as preferred cluster sizes or a preferred number of clusters, in order to efficiently and effectively partition the data. Finally, because data points, or entities, may be alternatively added and removed during the construction of a given cluster, the method and system is far less prone to converge on sub-optimal partitionings than currently available systems.
REFERENCES:
patent: 4937747 (1990-06-01), Koller
patent: 5263120 (1993-11-01), Bickel
patent: 5857169 (1999-01-01), Seide
patent: 5933818 (1999-08-01), Kasravi et al.
patent: 5983224 (1999-11-01), Singh et al.
patent: 6012058 (2000-01-01), Fayyad et al.
patent: 6049797 (2000-04-01), Guha et al.
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6182091 (2001-01-01), Pitkow et al.
Ben-Dor, A. and Yakhini, Z. “Clustering Gene Expression Patterns”, Proceedings of the Third Annual International Conference on Computational Molecular Biology, Apr. 11-14, 1999, pp. 33-42.*
A. Ben-Dor and Z. Yakhini, “Clustering Gene Expression Patterns”, Proceedings of the Third Annual International Conference on Computational Molecular Biology, Apr. 11-14, 1999, pp. 33-42.*
E. Hartuv et al., “An Algorithm for Clustering cDNAs for Gene Expression Analysis”, Proceedings of the Third Annual International Conference on Computational Molecular Biology, Apr. 11-14, 1999, pp. 188-197.*
I. Hofman and R. Jarvis, “Robust and Efficient Cluster Analysis Using a Shared Near Neighbours Approach”, Proceedings of the 14th International Conference on Pattern Recognition, Aug. 16-20, 1998, vol. 1, pp. 243-247.*
R. Drmanac G. Lennon S. Drmanac I. Labat R. Crkvenjakov and H. Lehrach. Partial sequencing by oligohybridization: Concept and applications in genome analysis. In Proceedings of the first international conference on electrophoresis supercomputing and the human genome Edited by C. Cantor and H. Lim, pp. 60-75, Singapore, 1991, World Scientific.
A.P. Blanchard and L. Hood, Sequence to array:probing the genome's secrets. Nature Biotechnology, 14:1649-1996.
Large-scale temporal gene expression mapping of central nervouse system development Wen XL, Fuhrman S, Michaels GS, Carr DB, Smith S, Barker JL, Somogyi R. Proceeding
Ben-Dor Amir
Shamir Ron
Yakhini Zohar H
Agilent Technologie,s Inc.
Homere Jean R.
Wassum Luke S.
LandOfFree
Method and system for partitioning data into subsets of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for partitioning data into subsets of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for partitioning data into subsets of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860624