Sorting points into neighborhoods (spin)

• US 20070288540A1
• Filed: 09/01/2006
• Published: 12/13/2007
• Est. Priority Date: 03/01/2004
• Status: Abandoned Application

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Inventors: Domany, Eytan, Tsafrir, Ilan, Tsafrir, Dafna
• Application Number:
  US10/591,445
• Publication Number:
  US 20070288540A1
• Time in Patent Office: Days
• US Class Current: 708/300
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• 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
• CPC Class Codes: G16B 45/00 ICT specially adapted for bioinformatics-related data visualisation, e.g. displaying of maps or networks

Abstract

A method for an unsupervised analysis of data according to a reordered distance matrix. According to preferred embodiments thereof, the present invention is useful for large scale multidimensional data, more preferably data having at least four dimensions. The present invention is also preferably used for data comprising a plurality of objects characterized by continuous variables, for example variables having a continuum of possible values rather than a plurality of discrete values.

Claims

1. A method for analyzing data, comprising performing an unsupervised analysis of data according to a reordered distance matrix.

2. The method of claim 1, wherein said distance matrix is reordered using a weighting function.

3. The method of claim 1, suitable for automatically and semi-automatically analyzing data.

4. The method of claim 1, wherein the data comprises a plurality of objects characterized by continuous variables.

5. The method of claim 1, further comprising:

visualization of the data according to said analysis.

6. The method of claim 5, further comprising:

detecting at least one characteristic of the data according to said visualization.

7. The method of claim 1, further comprising:

detecting at least one characteristic of the data according to said analysis.

8. The method of claim 6, wherein the data is analyzed without reference to a predetermined order and/or wherein the data lacks pre-ordering.

9. The method of claim 1, comprising the SPIN method.

10. The method of claim 9, wherein the SPIN method comprises the Side-to-Side (STS) method, featuring a strictly increasing or decreasing vector for reordering said distance matrix.

11. The method of claim 10, wherein said STS method comprises:

Input;

D<sub>n×

n</sub> and a strictly increasing vector X

1. Compute S=D X.

2. Sort S in descending order to get S′

=P(S), where P is the sorting permutation.

3. If P(S) !=S, set D=P D^T and go to stage 1.

4. Output D.

12. The method of claim 11, further comprising performing stages 1-3 more than once.

13. The method of claim 11, further comprising using at least one heuristic to reorder D.

14. The method of claim 9, wherein the SPIN method comprises the Neighborhood method, featuring a matrix of fixed size.

15. The method of claim 14, wherein said Neighborhood method comprises:

Input;

D<sub>n×

n</sub> and W<sub>n×

n</sub>

1. Compute M=D W

2. Set P=arg min<sub>Qε

Sn</sub> tr(QM)

3. If tr (P M) !=tr (M), set D=P D PT and go to 1.

4. Output D.

16. The method of claim 15, further comprising performing stages 1-3 more than once.

17. The method of claim 15, further comprising using at least one heuristic to reorder D.

18. The method of claim 14, wherein the Neighborhood method features Gaussian smoothing.

19. The method of claim 15, wherein stage 2 is performed by solving the Linear Assignment Problem.

20. The method of claim 1, further comprising:

zooming in on a part of the data by separately examining a sub-matrix of the data according to said analysis.

21. The method of claim 20, further comprising:

separately examining a plurality of sub-matrices of the data according to said analysis; and

comparing results of said separate examinations to determine at least one characteristic of the data.

22. The method of claim 1, wherein the data comprises gene expression data and/or data from a gene microarray, comprising data from a large number of genes analyzed simultaneously.

23. The method of claim 1, wherein the data comprises data from expression of genes in cancerous tissue.

24. The method of claim 1, wherein the data comprises data related to a biological process, optionally including a biological cycle.

25. The method of claim 1 adapted for machine vision.

40. A method according to claim 1, for partitioning the data into a plurality of optionally overlapping subsets.

41. The method of claim 40, further comprising:

using the distance matrices calculated from each subset separately to find novel partitions.

42. The method of claim 1, further comprising implementing the method and presenting the data with an intuitive easy-to-use GUI.

44. The method of claim 1, further comprising optionally constraining said reordering according to a dendrogram from any hierarchical clustering method.

26. A method for analyzing gene expression data and/or data from a gene microarray, comprising data from a large number of genes analyzed simultaneously, comprising:

filtering the data according to a variance filter to form filtered data;

determining a distance matrix for said filtered data; and

reordering said distance matrix to analyze said filtered data.

27. The method of claim 26, further comprising:

analyzing said reordered distance matrix to determine at least one characteristic of said filtered data.

28. The method of claim 27, wherein said reordering is performed according to an automatic and/or semi-automatic, unsupervised analysis.

29. The method of claim 28, wherein said reordering is performed according to SPIN.

30. The method of claim 27, wherein the data is analyzed to determine a noise level in the data.

31. The method of claim 30, wherein said noise level is used to alter at least one characteristic of the microarray or of an experimental protocol for data collection.

32. The method of claim 27, wherein the data is analyzed to determine an inherent property of the data other than a property for which the experiment was designed.

33. The method of claim 26, wherein the data comprises cancer-related data.

34. The method of claim 26, adapted for ordering both samples and genes.

35. A method for analyzing data related to a biological process, optionally including a biological cycle, comprising the SPIN method.

36. A method for machine vision, comprising the SPIN method.

37. The method of claim 36, wherein the SPIN method is performed for analyzing a distance matrix for visual data.

38. The method of claim 37, further comprising:

zooming in on a part of the data by separately examining a sub-matrix of the data according to said analysis.

39. The method of claim 38, further comprising:

separately examining a plurality of sub-matrices of the data according to said analysis; and

comparing results of said separate examinations to determine at least one characteristic of the data.

43. A method for analyzing data from expression of genes in cancerous tissue, comprising the SPIN method.