Representation and extraction of biclusters from data arrays

• US 7,849,088 B2
• Filed: 07/31/2006
• Issued: 12/07/2010
• Est. Priority Date: 07/31/2006
• Status: Active Grant

• Current Assignee: City University of Hong Kong
• Original Assignee: City University of Hong Kong
• Inventors: LIEW, Alan Wee-Chung, GAN, Xiangchao, Yan, Hong
• Primary Examiner(s): Truong, Cam Y
• Assistant Examiner(s): VO, CECILE H
• Application Number:
  US11/461,152
• Publication Number:
  US 20080027954A1
• Time in Patent Office: 1,590 Days
• Field of Search: 707100-1041, 707 2- 6, 707/200, 707/1, 707/999.005, 707/999.006, 707/737, 707999001- 9, 707/999.102, 707/999.104, 707/999.107, 706 15- 20
• US Class Current: 707/737
• 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 of data mining for biclusters in data at least partially using a processor in communication with a memory storing instructions for execution by the processor to perform the method, the method comprising detecting hyperplanes in said data, said hyperplanes having at least two dimensions and obeying an equation

2. The method according to claim 1, wherein the transform comprises a Hough transform.

3. The method according to claim 2, wherein the Hough transform comprises a fast Hough transform.

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

5. The method according to claim 4, wherein the data corresponds to a two-dimensional array, and wherein each block of said plurality of separate blocks extends across an entire length of the two-dimensional array in a first direction and a part of the length of the two-dimensional array in a second direction.

6. The method according to claim 4, wherein the determining is performed for each of the plurality of blocks, the method further comprising:

testing whether biclusters found in a given block extends into data in another block; and

wherein the outputting comprises outputting located biclusters for all of the plurality of blocks.

7. The method according to claim 6, further comprising, prior to outputting located biclusters, detecting and deleting duplicated biclusters.

8. The method according to claim 7, further comprising, prior to the splitting, hierarchically clustering the data.

9. The method according to claim 1, wherein the biclusters that are located include two or more biclusters that overlap in the data.

10. The method according to claim 1, wherein said data is selected from a group consisting of:

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

11. The method according to claim 1, wherein said data is gene expression data derived from a plurality of microarrays.

12. The 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.

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

14. A method of analyzing data for biclusters, at least partially using a processor in communication with a memory storing instructions for execution by the processor to perform the method, the method comprising:

transforming said data into parameter space by applying a transform to the data;

detecting hyperplanes having at least two dimensions and obeying an equation

15. The method according to claim 14, wherein said data is selected from a group consisting of:

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

16. Apparatus for analyzing data for biclusters comprising a processor in communication with a memory storing instructions for execution by the processor to perform a method, the method comprising:

transforming said data into parameter space by applying a transform to the data;

detecting hyperplanes in said transformed data, said hyperplanes having at least two dimensions and obeying an equation

17. The apparatus according to claim 16, comprising a dedicated circuit for detecting hyperplanes.

18. The apparatus according to claim 16, comprising a programmed circuit for detecting hyperplanes.

19. The apparatus according to claim 16, comprising a computer, said computer having a processor for running software to treat the input data as geometric data and detect hyperplanes in said data.

20. The apparatus according to claim 16, wherein said data is treated as geometric data.

21. A computer program product for analyzing data for biclusters, the computer program product comprising:

a storage medium readable by a computer and storing instructions for execution by the computer for performing a method comprising;

transforming said data into parameter space using a transform, detecting hyperplanes in said data, said hyperplanes having at least two dimensions, determining whether the detected hyperplanes represent biclusters in the data, and outputting biclusters located thereby,

wherein the determining comprises determining if the detected hyperplanes correspond to one or more biclusters selected from a group consisting of;

constant biclusters, constant rows, constant columns, coherent values with additive model, coherent values with multiplicative model whereby each row or column can be obtained by multiplying another row or column by a constant value, and coherent values on columns with linear model whereby each column may be obtained by multiplying another column by a constant value and then adding a constant.

22. The computer program product according to claim 21, wherein said storage medium comprises a portable memory.

23. The computer program product according to claim 21, wherein said storage medium comprises a memory, accessible for executing said instructions remotely, via a network.

24. A method of data mining for biclusters in data at least partially using a processor in communication with a memory storing instructions for execution by the processor to perform the method, the method comprising detecting hyperplanes in said data, said hyperplanes having at least two dimensions, determining whether the hyperplanes represent biclusters in the data, and outputting the determined biclusters, wherein detecting hyperplanes in said data comprises transforming the data into parameter space by applying a transform to the data;

and wherein the biclusters are coherent values with additive model whereby each row or column can be obtained by adding a constant to another row or column, or coherent values with multiplicative model whereby each row or column can be obtained by multiplying another row or column by a constant value, or coherent values on columns with linear model whereby each column may be obtained by multiplying another column by a constant value and then adding a constant.