REPRESENTATION AND EXTRACTION OF BICLUSTERS FROM DATA ARRAYS

• US 20080027954A1
• Filed: 07/31/2006
• Published: 01/31/2008
• Est. Priority Date: 07/31/2006
• Status: Active Grant

• Current Assignee: City University of Hong Kong
• Original Assignee: City University of Hong Kong
• Inventors: YAN, Hong, GAN, Xiangchao, LIEW, Alan Wee-Chung
• Granted Patent: US 7,849,088 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 10/762 using clustering, e.g. of similar faces in social networks
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 2201/04 Recognition of patterns in DNA microarrays
• CPC Class Codes: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression
• CPC Class Codes: G16B 25/10 Gene or protein expression profiling; Expression-ratio estimation or normalisation
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/30 Unsupervised data analysis

Abstract

Gene expression, or other data is analyzed for the presence of biclusters. The data is represented as geometric data. Lines, planes and/or hyperplanes are detected in the geometric data using a transform such as a Hough Transform or its variations. The detected lines, planes and hyperplanes are analyzed to determine if they correspond to biclusters in the original data.

Claims

1. A method for use in data mining for biclusters in data, comprising detecting hyperplanes in said data.

2. A method according to claim 1, further comprising analyzing detected hyperplanes to determine whether they represent biclusters in the data and outputting biclusters located thereby.

3. A method according to claim 2, wherein analyzing the detected hyperplanes comprises determining if they correspond to one or more biclusters selected from the group consisting of:

constant biclusters, constant rows, constant columns, coherent values with additive model, coherent values with multiplicative model, and coherent values on columns with linear model.

4. A method according to claim 1, wherein detecting hyperplanes in said data comprises transforming the data into parameter space using a transform.

5. A method according to claim 4, wherein the transform comprises a Hough transform.

6. A method according to claim 5, wherein the Hough transform comprises a fast Hough transform.

7. A method according to claim 1, wherein the data comprises a set of data and further comprising, prior to detecting hyperplanes, splitting the data set into separate blocks of data and wherein detecting hyperplanes is performed separately for each block.

8. A method according to claim 7, wherein the data set corresponds to a two-dimensional array and is split along a first of the two dimensions, each block containing data for the whole of the second dimension in the set.

9. A method according to claim 7, further comprising, after detecting hyperplanes for each block:

analyzing detected hyperplanes to determine the presence of biclusters in the blocks;

testing whether biclusters found in the blocks extend into data in other block; and

outputting located biclusters for the complete data set.

10. A method according to claim 9, further comprising, prior to outputting located biclusters, detecting and deleting duplicated biclusters.

11. A method according to claim 10, further comprising, prior to splitting the complete data set into separate blocks of data, hierarchically clustering the data.

12. A method according to claim 2, wherein the biclusters that are located include two or more biclusters that overlap in the data.

13. A method according to claim 1, wherein said data is selected from the group consisting of:

gene expression data, chemical reaction data, chemical process data, electoral data, spending data and financial data.

14. A method according to claim 13, wherein said data is gene expression data derived from a plurality of microarrays.

15. A method according to claim 1, wherein said data corresponds to a two-dimensional array, with the biclusters comprising a subset of data in a first one of the two dimensions exhibiting a consistent pattern over a subset of data in a second one of the two dimensions.

16. A method according to claim 1, further comprising treating said data as geometric data prior to detecting hyperplanes.

17. A method of analyzing data for biclusters, comprising:

detecting hyperplanes in said data; and

analyzing detected hyperplanes to determine whether they represent biclusters in the data.

18. A method according to claim 17, wherein said data is selected from the group consisting of:

gene expression data, chemical reaction data, chemical process data, electoral data, spending data and financial data.

19. Apparatus for analyzing data for biclusters, comprising:

means for inputting the data; and

means for detecting hyperplanes in said data.

20. Apparatus according to claim 19, wherein the means for detecting hyperplanes in said data comprises a dedicated circuit.

21. Apparatus according to claim 19, wherein the means for detecting hyperplanes in said data comprises a programmed circuit.

22. Apparatus according to claim 19, comprising a computer, wherein the means for detecting hyperplanes in said data comprises a processor for running software to treat the input data as geometric data and detect hyperplanes in said data.

23. Apparatus according to claim 19, further comprising means for treating said data as geometric data.

24. A computer program product embodying a program of executable instructions to effect a method for use in analyzing data for biclusters, the method comprising detecting hyperplanes in said data as if it were geometric data.

25. A computer program product according to claim 24, comprising a portable memory.

26. A computer program product according to claim 24, comprising a memory, accessible for executing said instructions remotely, via a network.