Discovering significant and interpretable patterns from multifactorial DNA microarray data with poor replication.

Motivation: Multivariate analyses are advantageous for the simultaneous testing of the separate and combined effects of many variables and of their interactions. In factorial designs with many factors and/or levels, however, sufficient replication is often prohibitively costly. Furthermore, complicated statements are often required for the biological interpretation of the higher-order interactions determined by standard statistical techniques like analysis of variance.

Results: Because we are usually interested in finding factor-specific effects or their interactions, we assumed that the observed expression profile of a gene is a manifestation of an underlying factor-specific generative pattern (FSGP) combined with noise. Thus, a genetic algorithm was created to find the nearest FSGP for each expression profile. We then measured the distance between each profile and the corresponding nearest FSGP. Permutation testing for the distance measures successfully identified those genes with statistically significant profiles, thus yielding straightforward biological interpretations. Association networks of genes, drugs, and cell lines were created as tripartite graphs, representing significant and interpretable relations, by using a microarray experiment of gastric-cancer cell lines with a factorial design and no replication. The proposed method may benefit the combined analysis of heterogeneous expression data from the growing public repositories.

Keyword: gene expression, DNA microarray, pattern recognition, genetic algorithm, gastric cancer

Availability: http://www.snubi.org/software/FSGP/
Contact: juhan@snu.ac.kr

Journal of Biomedical Informatics 2004:37;260-268

Situation: 

• Multivariate analyses are advantageous in testing the separate and combined effects of many variables and their interactions at the same time. 
• Nine gastric-cancer cell lines are treated by six anti-chemotherapeutic drugs. 
• Microarray experiments were performed applying the classical two-dye technique before and after the treatments. 
• Now we have 54 (= 6 * 9) arrays (experiments) done.

Problem: 

• Formally, the experimental design is a multifactorial one with two factors with nine-and-six levels.
• In factorial designs with many factors and/or levels, however, enough replication is often prohibitively costly. 
• Furthermore, complicated statements are often required for the biological interpretation of the higher-order interactions determined by the standard statistical techniques such as analysis of variance.
• Because we have no replication, the problem of extracting significant change is non-trivial by the traditional statistical method such as analysis of variance (ANOVA).

Assuming underlying generative pattern.

• Each observation can be regarded as the manifestation of underlying (factor-specific) generative functions (or FSGP, purple boxes) with noise. 
• For example, the observation is generated by the combination of C4 and T2 (purple boxes), which force the expression levels under influence (i.e. with boxes) up to 9s (maximum value) and others down to 0s (minimum value), with imposed noise, which creates variable values around.

  (i.e. range of the values: 0 ~ 9)

Defining factor-specific generative pattern and pattern distance:

• We define FSGP, which is a combination of factor specific generative functions, and the pattern distance as follows.

• The pattern distance is defined as (a kind of) Hamming distance between expression profile and its nearest FSGP. In the binary space, where expression level is dichotomized to zero (i.e. non-changed and depicted as blank cells) or one (i.e. significantly changed and depicted as dark cells), pattern distance equals simply to the number of mismatches. 

Therefore, the pattern distance between a two-factor profile C_ij and the nearest FSGP, C’_ij, equals å|C_ij – C’_ij| . 

More general N-dimensional pattern distance of C_k1,...,kn equals å|C_k1,...,kn – C’_k1,...,kn |. 　

Genetic Algorithm to find the nearest factor-specific generative pattern of an observation:

• Given an observation, which is an n-dimensional matrix, the algorithm try to find the nearest generative pattern, which can be represented by a classical fixed-length chromosome format. 
• An example showing that the problem of finding the nearest factor-specific generative pattern is a combinatorial problem. The observation can be represented either by the parsimonious P((),(1,2,3,4)) with pattern distance 0 or P((1,2,3,4,5,6,7,8,9),(1,2,3,4)) with pattern distnace 18. Thus the nearest factor specific generative pattern is P((),(1,2,3,4)), which can be searched by the genetic algorithm below.

#An example of this  6 * 9 pattern 

• This code was tested on Python 2.2 on Linux and MS-Windows platform
      Python code can be downloaded here :

Determining significance: 

• Now we have distance measures (i.e., pattern distance) for thousands of probes, we can apply permutation testing to acquire FDR (False Discovery Rate) for each pattern.

Evaluation of FSGP

• For the 37 genes (Table 1 in the paper) determined significant by FSGP, we performed an exhaustive search for the 2^(6+9) FSGP space.
• It is demonstrated that the GA implementation has successfully found the nearest FSGP's for all the 37 significant genes.
• As discussed in the manuscript, one limitation of GA approach is that when there are more than 1 best answers (or ties) it just declares one of them. (Please see the 2nd, 28th and 32th row of the table.)
• See the data table, histograms and the frequency table.
• 

Contact information: juhan@snu.ac.kr

powered by SNUBI