Methods, systems and computer program products for identifying conditional associations among features in samples

• US 20020133498A1
• Filed: 01/11/2002
• Published: 09/19/2002
• Est. Priority Date: 01/17/2001
• Status: Abandoned Application

• Current Assignee: Smithkline Beecham Corporation (GSK plc)
• Original Assignee: Smithkline Beecham Corporation (GSK plc)
• Inventors: Xia, Tai-he, Young, Sidney Stanley, Keefer, Christopher E.
• Application Number:
  US10/044,680
• Publication Number:
  US 20020133498A1
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• 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 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
• CPC Class Codes: G16B 5/20 Probabilistic models

Abstract

Conditional associations among features in samples are identified by defining a matrix having rows that represent the samples and columns that represent the features. Each row-column position of the matrix has a first binary value if the sample that is associated with the row exhibits the feature that is associated with the column, and a second binary value if a sample that is associated with the row does not exhibit the feature that is associated with the column. Recursive partitioning then is performed for each column. In particular, for each column, the column is recursively partitioned relative to the remaining ones of the columns, to define a tree of conditional branches for the rows for each column. The collection of trees of conditional branches for the columns may be displayed and/or analyzed to identify conditional associations of interest. Continuous features, wherein each row-column position of the matrix has a value selected from a continuous range of values, also may be analyzed.

Claims

1. A method of identifying conditional associations among a plurality of features in a plurality of samples, the method comprising:

defining a matrix having a plurality of rows that represent the plurality of samples and a plurality of columns that represent the plurality of features, each row-column position of the matrix having a first binary value if the sample that is associated with the row exhibits the feature that is associated with the column and a second binary value if the sample that is associated with the row does not exhibit the feature that is associated with the column; and

for each column, recursively partitioning the column relative to remaining ones of the columns to define a tree of conditional branches for the rows for each column.

2. A method according to claim 1 wherein the recursively partitioning is followed by:

analyzing the trees of conditional branches for the columns to identify the conditional associations.

3. A method according to claim 1 wherein the recursively partitioning is followed by:

displaying the trees of conditional branches for the columns to identify the conditional associations.

4. A method according to claim 1 wherein the recursively partitioning comprises the following that are performed for each column:

for the column, comparing a number of occurrences of the first binary value in both the column and in each of the remaining columns to define a score for each of the remaining columns;

selecting one of t he remaining columns based upon the scores;

dividing the rows that are associated with the one of the remaining columns based on whether the first value or the second value is present in the rows, to thereby obtain two sub-matrices and two corresponding branches of a tree; and

repeatedly performing the comparing, selecting and dividing for the columns of each of the sub matrices that are associated with the two branches of the tree to obtain remaining branches of the tree.

5. A method according to claim 4 wherein the selecting comprises selecting one of the remaining columns that has a maximum score.

6. A method according to claim 4 wherein the selecting comprises selecting one of the remaining columns based upon the scores and auxiliary information concerning the samples.

7. A method according to claim 4 wherein the repeatedly performing comprises repeatedly performing the comparing, selecting and dividing of the rows of each sub-matrix until a predefined termination is reached.

8. A method according to claim 7 wherein the predefined termination comprises at least one of the scores in the remaining columns being less than a predetermined score, the number of rows in a sub-matrix being less than a predetermined number and the tree having a predetermined depth.

9. A method according to claim 4 wherein the comparing a number of occurrences of the first binary value in both the column and in each of the remaining columns to define a score for each of the remaining columns comprises comparing a number of occurrences of the first binary value in both the column and in each of the remaining columns using at least one of a Pearson chi-square, likelihood ratio statistic and measure of agreement metric.

10. A method according to claim 1 wherein the samples are biological samples, the features are genes, the first binary value indicates that the gene is expressed in the biological sample and the second binary value indicates that the gene is not expressed in the biological sample.

11. A method of identifying conditional associations among a plurality of features in a plurality of samples, the method comprising:

defining a matrix having a plurality of rows that represent the plurality of samples and a plurality of columns that represent the plurality of features, each row-column position of the matrix having a value selected from a continuous range of values that indicates an amount that the sample that is associated with the row exhibits the feature that is associated with the column; and

for each column, recursively partitioning the column relative to remaining ones of the columns to define a tree of conditional branches for the rows for each column.

12. A method according to claim 11 wherein the recursively partitioning comprises the following that are performed for each column:

for the column, identifying an association between the column and each of the remaining columns to define a score for each of the remaining columns;

selecting one of the remaining columns based upon the scores;

dividing the rows that are associated with the one of the remaining columns based on range partitions of the values in the rows to thereby obtain at least two sub-matrices and at least two corresponding branches of a tree; and

repeatedly performing the comparing, selecting and dividing for the columns of each of the sub matrices that are associated with the at least two branches of the tree to obtain remaining branches of the tree.

13. A method according to claim 12 wherein the selecting comprises selecting one of the remaining columns that has a highest correlation coefficient with the column.

14. A method according to claim 11 wherein the samples are biological samples, the features are continuous traits of the biological samples and the value indicates an amount that the biological sample that is associated with the row exhibits the continuous trait.

16. A method according to claim 15 wherein the samples are biological samples and the features are discrete traits of the biological samples.

17. A method according to claim 15 wherein the samples are biological samples and the features are continuous traits of the biological samples.

19. A system according to claim 18 further comprising:

means for analyzing the trees of conditional branches for the columns to identify the conditional associations.

20. A system according to claim 18 further comprising:

means for displaying the trees of conditional branches for the columns to identify the conditional associations.

21. A system according to claim 18 wherein the means for recursively partitioning comprises:

means for comparing a number of occurrences of the first binary value in both the column and in each of the remaining columns to define a score for each of the remaining columns;

means for selecting one of the remaining columns based upon the scores;

means for dividing the rows that are associated with the one of the remaining columns based on whether the first value or the second value is present in the rows, to thereby obtain two sub-matrices and two corresponding branches of a tree; and

means for repeatedly activating the means for comparing, the means for selecting and the means for dividing for the columns of each of the sub matrices that are associated with the two branches of the tree to obtain remaining branches of the tree.

22. A system according to claim 21 wherein the means for selecting comprises means for selecting one of the remaining columns that has a maximum score.

23. A system according to claim 21 wherein the means for selecting comprises means for selecting one of the remaining columns based upon the scores and auxiliary information concerning the samples.

24. A system according to claim 21 wherein the means for repeatedly activating comprises means for repeatedly activating the means for comparing, the means for selecting and the means for dividing for the rows of each sub-matrix until a predefined termination is reached.

25. A system according to claim 24 wherein the predefined termination comprises at least one of the scores in the remaining columns being less than a predetermined score, the number of rows in a sub-matrix being less than a predetermined number and the tree having a predetermined depth.

26. A system according to claim 21 wherein the means for comparing a number of occurrences of the first binary value in both the column and in each of the remaining columns to define a score for each of the remaining columns comprises means for comparing a number of occurrences of the first binary value in both the column and in each of the remaining columns using at least one of a Pearson chi-square, likelihood ratio statistic and measure of agreement metric.

27. A system according to claim 18 wherein the samples are biological samples, the features are genes, the first binary value indicates that the gene is expressed in the biological sample and the second binary value indicates that the gene is not expressed in the biological sample.

29. A system according to claim 28 wherein the means for recursively partitioning comprises:

means for identifying an association between the column and each of the remaining columns to define a score for each of the remaining columns;

means for selecting one of the remaining columns based upon the scores;

means for dividing the rows that are associated with the one of the remaining columns based on range partitions of the values in the rows to thereby obtain at least two sub-matrices and at least two corresponding branches of a tree; and

means for repeatedly activating the means for comparing, the means for selecting and the means for dividing for the columns of each of the sub matrices that are associated with the at least two branches of the tree to obtain remaining branches of the tree.

30. A system according to claim 29 wherein the means for selecting comprises means for selecting one of the remaining columns that has a highest correlation coefficient with the column.

31. A system according to claim 28 wherein the samples are biological samples, the features are continuous traits of the biological samples and the value indicates an amount that the biological sample that is associated with the row exhibits the continuous trait.

15. A method of identifying associations among a plurality of features in a plurality of samples, the method comprising:

generating at least two trees of conditional branches for a corresponding at least two of the features, each tree of conditional branches indicating conditional associations for a corresponding feature relative to remaining ones of the plurality of features.

18. A system for identifying conditional associations among a plurality of features in a plurality of samples, the system comprising:

a matrix having a plurality of rows that represent the plurality of samples and a plurality of columns that represent the plurality of features, each row-column position of the matrix having a first binary value if the sample that is associated with the row exhibits the feature that is associated with the column and a second binary value if the sample that is associated with the row does not exhibit the feature that is associated with the column; and

means for recursively partitioning each column relative to remaining ones of the columns to define a tree of conditional branches for the rows for each column.

28. A system for identifying conditional associations among a plurality of features in a plurality of samples, the system comprising:

a matrix having a plurality of rows that represent the plurality of samples and a plurality of columns that represent the plurality of features, each row-column position of the matrix having a value selected from a continuous range of values that indicates an amount that the sample that is associated with the row exhibits the feature that is associated with the column; and

means for recursively partitioning each column relative to remaining ones of the columns to define a tree of conditional branches for the rows for each column.

32. A system for identifying associations among a plurality of features in a plurality of samples, the system comprising:

means for generating at least two trees of conditional branches for a corresponding at least two of the features, each tree of conditional branches indicating conditional associations for a corresponding feature relative to remaining ones of the plurality of features; and

means for displaying the at least two trees of conditional branches.

33. A system according to claim 32 wherein the samples are biological samples and the features are discrete traits of the biological samples.

34. A system according to claim 32 wherein the samples are biological samples and the features are continuous traits of the biological samples.

36. A computer program product according to claim 35 further comprising:

computer-readable program code that is configured to analyze the trees of conditional branches for the columns to identify the conditional associations.

37. A computer program product according to claim 35 further comprising:

computer-readable program code that is configured to display the trees of conditional branches for the columns to identify the conditional associations.

38. A computer program product according to claim 35 wherein the computer-readable program code that is configured to recursively partition comprises:

computer-readable program code that is configured to compare a number of occurrences of the first binary value in both the column and in each of the remaining columns to define a score for each of the remaining columns;

computer-readable program code that is configured to select one of the remaining columns based upon the scores;

computer-readable program code that is configured to divide the rows that are associated with the one of the remaining columns based on whether the first value or the second value is present in the rows, to thereby obtain two sub-matrices and two corresponding branches of a tree; and

computer-readable program code that is configured to repeatedly activate the computer-readable program code that is configured to compare, the computer-readable program code that is configured to select and the computer-readable program code that is configured to divide for the columns of each of the sub matrices that are associated with the two branches of the tree to obtain remaining branches of the tree.

39. A computer program product according to claim 38 wherein the computer-readable program code that is configured to select comprises computer-readable program code that is configured to select one of the remaining columns that has a maximum score.

40. A computer program product according to claim 38 wherein the computer-readable program code that is configured to select comprises computer-readable program code that is configured to select one of the remaining columns based upon the scores and auxiliary information concerning the samples.

41. A computer program product according to claim 38 wherein the computer-readable program code that is configured to repeatedly activate comprises computer-readable program code that is configured to repeatedly activate the computer-readable program code that is configured to compare, the computer-readable program code that is configured to select and the computer-readable program code that is configured to divide rows of each sub-matrix until a predefined termination is reached.

42. A computer program product according to claim 41 wherein the predefined termination comprises at least one of the scores in the remaining columns being less than a predetermined score, the number of rows in a sub-matrix being less than a predetermined number and the tree having a predetermined depth.

43. A computer program product according to claim 38 wherein the computer-readable program code that is configured to compare a number of occurrences of the first binary value in both the column and in each of the remaining columns to define a score for each of the remaining columns comprises computer-readable program code that is configured to compare a number of occurrences of the first binary value in both the column and in each of the remaining columns using at least one of a Pearson chi-square, likelihood ratio statistic and measure of agreement metric.

44. A computer program product according to claim 35 wherein the samples are biological samples, the features are genes, the first binary value indicates that the gene is expressed in the biological sample and the second binary value indicates that the gene is not expressed in the biological sample.

46. A computer program product according to claim 45 wherein the computer-readable program code that is configured to recursively partition comprises:

computer-readable program code that is configured to identify an association between the column and each of the remaining columns to define a score for each of the remaining columns;

computer-readable program code that is configured to select one of the remaining columns based upon the scores;

computer-readable program code that is configured to divide the rows that are associated with the one of the remaining columns based on range partitions of the values in the rows to thereby obtain at least two sub-matrices and at least two corresponding branches of a tree; and

computer-readable program code that is configured to repeatedly activate the computer-readable program code that is configured to compare, the computer-readable program code that is configured to select and the computer-readable program code that is configured to divide for the columns of each of the sub matrices that are associated with the at least two branches of the tree to obtain remaining branches of the tree.

47. A computer program product according to claim 46 wherein the computer-readable program code that is configured to select comprises computer-readable program code that is configured to select one of the remaining columns that has a highest correlation coefficient with the column.

48. A computer program product according to claim 45 wherein the samples are biological samples, the features are continuous traits of the biological samples and the value indicates an amount that the biological sample that is associated with the row exhibits the continuous trait.

50. A computer program product according to claim 49 wherein the samples are biological samples and the features are discrete traits of the biological samples.

51. A computer program product according to claim 49 wherein the samples are biological samples and the features are continuous traits of the biological samples.

35. A computer program product that identifies conditional associations among a plurality of features in a plurality of samples, the computer program product comprising a computer usable storage medium having computer-readable program code embodied in the medium, the computer-readable program code comprising:

computer-readable program code that is configured to define a matrix having a plurality of rows that represent the plurality of samples and a plurality of columns that represent the plurality of features, each row-column position of the matrix having a first binary value if the sample that is associated with the row exhibits the feature that is associated with the column and a second binary value if the sample that is associated with the row does not exhibit the feature that is associated with the column; and

computer-readable program code that is configured to recursively partition each column relative to remaining ones of the columns to define a tree of conditional branches for the rows for each column.

45. A computer program product that identifies conditional associations among a plurality of features in a plurality of samples, the computer program product comprising a computer usable storage medium having computer-readable program code embodied in the medium, the computer-readable program code comprising:

computer-readable program code that is configured to define a matrix having a plurality of rows that represent the plurality of samples and a plurality of columns that represent the plurality of features, each row-column position of the matrix having a value selected from a continuous range of values that indicates an amount that the sample that is associated with the row exhibits the feature that is associated with the column; and

computer-readable program code that is configured to recursively partition each column relative to remaining ones of the columns to define a tree of conditional branches for the rows for each column.

49. A computer program product that identifies associations among a plurality of features in a plurality of samples, the computer program product comprising a computer usable storage medium having computer-readable program code embodied in the medium, the computer-readable program code comprising:

computer-readable program code that is configured to generate at least two trees of conditional branches for a corresponding at least two of the features, each tree of conditional branches indicating conditional associations for a corresponding feature relative to remaining ones of the plurality of features.