BARTMAP: A viable structure for biclustering

Abstract

Clustering has been used extensively in the analysis of high-throughput messenger RNA (mRNA) expression profiling with microarrays. Furthermore, clustering has proven elemental in microRNA expression profiling, which demonstrates enormous promise in the areas of cancer diagnosis and treatment, gene function identification, therapy development and drug testing, and genetic regulatory network inference. However, such a practice is inherently limited due to the existence of many uncorrelated genes with respect to sample or condition clustering, or many unrelated samples or conditions with respect to gene clustering. Biclustering offers a solution to such problems by performing simultaneous clustering on both dimensions, or automatically integrating feature selection to clustering without any prior information, so that the relations of clusters of genes (generally, features) and clusters of samples or conditions (data objects) are established. However, the NP-complete computational complexity raises a great challenge to computational methods for identifying such local relations. Here, we propose and demonstrate that a neural-based classifier, ARTMAP, can be modified to perform biclustering in an efficient way, leading to a biclustering algorithm called Biclustering ARTMAP (BARTMAP). Experimental results on multiple human cancer data sets show that BARTMAP can achieve clustering structures with higher qualities than those achieved with other commonly used biclustering or clustering algorithms, and with fast run times.

Introduction

Clustering Bezdek (1981), Oliveira and Pedrycz (2007), Sato-Ilic and Jain (2006), Gokcay and Principe (2002), Xu and Wunsch (2005) and Xu and Wunsch (2009) has been used extensively in the analysis of high-throughput messenger RNA (mRNA) or microRNA expression profiling with microarrays, which demonstrate enormous promise in the areas of cancer diagnosis and treatment, gene function identification, therapy development and drug testing, and genetic regulatory network inference (Eisen et al., 1998, Golub et al., 1999, Jiang et al., 2004, McLachlan et al., 2004, Moreau et al., 2002, Shamir and Sharan, 2002, Xu and Wunsch, 2010, Xu and Wunsch, 2009, Xu and Wunsch, 2005). Usually, the expression levels of many genes are measured across a relatively small set of conditions or samples, and the obtained gene expression data are organized as a data matrix with rows corresponding to genes and columns corresponding to samples or conditions.

Let a gene expression data set be represented as a data matrix $E=(G,S)$, with $G=\{g_1,\dots ,g_N\}$ representing a set of $N$ genes or rows and $S=\{s_1,\dots ,s_M\}$ representing a set of $M$ samples (conditions)¹ or columns (see Table 1). An element $e_{ij}\in E$ then represents the expression level of gene $i$ under condition $j$. A gene or row cluster is a subset of rows defined on all columns, denoted as $C_{\mathrm{XS}}=(X,S)$, where $X\subseteq G$ is a subset of genes. Similarly, a sample or column cluster is a subset of columns defined across all rows, denoted as $C_{\mathrm{GY}}=(G,Y)$, where $Y\subseteq S$ is a subset of samples.

Such a data matrix and the corresponding row and column cluster definition can be generalized as a data matrix for many other applications. Such a practice, however, is inherently limited in analysis. This is because our general understanding of cellular processes elucidates that only a subset of genes is involved with a specific cellular process that becomes active only under some experimental conditions. However, microarrays generally are not specifically designed to meet the requirements of a particular experiment. Consider, for example, that in gene expression profile-based cancer diagnosis, only a subset of genes is related to some cancer type while numerous genes are considered irrelevant. In this case, the inclusion of all genes in sample clustering or all samples in gene clustering not only increases the computational burden, but could impair clustering performance due to the effect of these unrelated genes or samples, which are treated as noise.

Biclustering, first used by Cheng and Church (2000) in the community of bioinformatics, addresses this problem by performing clustering simultaneously on both row (gene) and column (sample) dimensions instead of clustering these two dimensions separately (Busygin et al., 2008, Madeira and Oliveira, 2004). In essence, biclustering can be regarded as a combination of clustering and automatic feature selection if we treat one dimension (e.g., column) as data objects and the other dimension (e.g., row) as description features. This task becomes particularly challenging without ground truth.

Note that the feature selection in biclustering is different from the feature selection that we usually consider in supervised classification. This difference lies in the fact that biclustering selects different subsets of features for different clusters of data objects, while standard feature selection chooses a subset of features from the candidate pool for all data objects. As such, the local relationship between subsets of genes and subsets of samples or conditions is identified with biclustering. Biclustering indicates gene groups that display similar patterns across a set of conditions (important to gene functional annotation and coregulated gene identification DiMaggio et al., 2008a, Lazzeroni and Owen, 2002, Li et al., 2009, Madeira et al., 2010, Segal et al., 2001, Tanay et al., 2002) or gene groups that are related to certain cancer types (for cancer classification discovery and diagnosis Getz et al., 2003, Kluger et al., 2003, Murali and Kasif, 2003, Tang and Zhang, 2005, Tchagang et al., 2008). In contrast, clustering focuses on uncovering global relationships between genes and samples or conditions. In fields other than bioinformatics, biclustering is also known as subspace clustering, co-clustering, or block clustering, among other names Busygin et al. (2008), Kriegel, Kröger, and Zimek (2009) and Madeira and Oliveira (2004). See the informative survey paper Kriegel et al. (2009).

Specifically, let $I\subseteq G$ and $J\subseteq S$ be subsets of the rows and columns for the gene expression data matrix $E;E_{IJ}=(I,J)$ is then the submatrix with rows $I$ and columns $J$. A bicluster corresponds to such a submatrix that exhibits certain homogeneity. The goal of a biclustering algorithm, then, is to identify a set of biclusters with pairs of row and column subsets. The complexity of the biclustering problem has been shown to be NP-complete (Madeira and Oliveira, 2004, Peeters, 2003), which leads to many heuristics falling into the five major categories summarized in Table 2 according to Madeira and Oliveira (2004). For example, Cheng and Church (2000) used the mean squared residue to measure the coherence of the rows and columns in a bicluster, which is defined as,

$$H(I,J)=\frac{1}{\left|I\right|\left|J\right|}\sum _{i\in I,j\in J}{(e_{ij}-\overline{e_{iJ}}-\overline{e_{Ij}}+\overline{e_{IJ}})}^2\text{,}$$

where $\overline{e_{iJ}}$ is the mean of the $i$th row, $\overline{e_{Ij}}$ is the mean of the $j$th column, and $\overline{e_{IJ}}$ is the mean of the bicluster. A submatrix $E_{IJ}$ is called a $\delta$-bicluster if $H(I,J)\le \delta$ for some $\delta \ge 0$. Possible ways to find the largest $\delta$-biclusters, which should also have relatively high row variance Cheng and Church (2000), include the evolutionary algorithm (Divina & Aguilar-Ruiz, 2006), multi-objective particle swarm optimization (Liu, Li, Hu, & Chen, 2009), and other greedy iterative search approaches, such as the FLOC (FLexible Overlapped biClustering) algorithm (Yang, Wang, Wang, & Yu, 2003). Lazzeroni and Owen (2002) developed a plaid model treating the matrix as the sum of additive layers. This model was further extended to combine external grouping information and to generate biclusters of profiles of repeated measures (Turner, Bailey, Krzanowski, & Hemingway, 2005). Gu and Liu (2007) proposed a Bayesian biclustering model with a Gibbs sampling procedure for statistical inference. DiMaggio et al. (2008b) considered modeling biclustering as either a network flow problem or a traveling salesman problem. A systematic comparison of five greedy search-based biclustering algorithms, together with a reference method (Bimax), was presented in Prelić et al. (2006).

Early cancer diagnosis is critical for prolonging human life. As aforementioned, biclustering overcomes the disadvantage of clustering in dealing with unrelated genes and focuses only on the cancer type-related genes, thus providing a more effective method of cancer classification and diagnosis. Biclustering algorithms that are used for this purpose include the interrelated two-way clustering (ITWC) algorithm (Tang & Zhang, 2005), the coupled two-way clustering (CTWC) algorithm (Getz et al., 2003), xMOTIF (Murali & Kasif, 2003), Binary State Pattern Clustering (BSPC) (Beattie & Robinson, 2006), the qualitative biclustering algorithm (QUBIC) (Li et al., 2009), the spectral biclustering algorithm (Kluger et al., 2003), the double conjugated clustering (DCC) algorithm (Busygin, Jacobsen, & Kramer, 2002), and fuzzy adaptive subspace iteration-based two-way clustering (FASIC) (Shaik & Yeasin, 2009), among others. For example, ITWC generates biclusters by combining clustering results from each dimension of the data matrix in an iterative way (Tang & Zhang, 2005). Within each iteration, a set of gene clusters is first created using standard clustering algorithms, e.g., $K$-means or self-organizing maps, followed by the independent clustering of the sample dimension based on each gene cluster. The clustering results from the previous steps are then combined, and heterogeneous groups, which are pairs of columns that do not share gene features used for clustering, are identified. Finally, the genes are sorted in descending order of the cosine distance. Only the first one third of sorted genes is kept so that a reduced gene set is obtained for each heterogeneous group. The above steps are then repeated using the reduced gene set until some stopping conditions are satisfied.

CTWC uses hierarchical clustering with the Euclidean distance (Getz et al., 2003), while DCC relies on self-organizing maps with the dot product for similarity (Busygin et al., 2002). FASIC adopts the concept of the fuzzy set theory and applies the fuzzy-adaptive subspace iteration algorithm to generate gene clusters under a progressive clustering framework. Those clusters are then scored to generate $p$-values indicating the significance of the differential expression (Shaik & Yeasin, 2009). Tchagang et al. demonstrated the effectiveness of biclustering for detecting and diagnosing ovarian cancer (Tchagang et al., 2008). Mitra et al. showed a biclustering application for microRNA expression profile-based cancer classification of multiple types, including melanoma, ovarian, renal, colon, leukemia, and so on (Mitra, Bandyopadhyay, Maulik, & Zhang, 2010).

Here, we present BARTMAP (Biclustering ARTMAP) to perform biclustering on gene expression data, particularly for cancer classification discovery, although BARTMAP can be used to other types of data that have high dimensionalities, e.g., document clustering. BARTMAP is adapted to and modified from a neural-based classifier, Fuzzy ARTMAP (Carpenter, Grossberg, Markuzon, Reynolds, & Rosen, 1992), for supervised classification. Fuzzy ARTMAP, together with its other variants, such as Ellipsoid ARTMAP (Anagnostopoulos & Georgiopoulos, 2001) and default ARTMAP (Carpenter, 2003), already have shown great effectiveness in gene expression data analysis and other biomedical applications (Xu et al., 2007, Xu et al., 2009). Similar to Fuzzy ARTMAP, BARTMAP is based on Adaptive Resonance Theory (ART) (Carpenter and Grossberg, 1987, Grossberg, 1976). ART is a learning theory that hypothesizes that resonance in neural circuits can trigger fast learning; it was developed as a solution to the plasticity-stability dilemma.

BARTMAP displays many attractive characteristics that are also inherent and general in the ART family. First, BARTMAP scales very well with large-scale data analysis while maintaining efficiency. As the computational complexity for its ART modules is $O(NlogN)$ or $O\left(N\right)$ for one-pass variant (Mulder & Wunsch, 2003), the overall computational cost for BARTMAP is relatively low. Each ART module can dynamically and adaptively generate clusters without the requirement of specifying the number of clusters in advance as is required in many other commonly used clustering algorithms, such as $K$-means and self-organizing feature maps. Furthermore, BARTMAP is an exemplar-based, transparent learning model. During its learning, the architecture summarizes data via the use of exemplars in order to accomplish its learning objective. This ability contrasts with other, opaque neural network architectures for which it is generally difficult to explain why an input produces a particular output. Another important feature of BARTMAP is its ability to detect atypical patterns during its learning. The detection of such patterns is accomplished via the employment of a match-based criterion that decides to which degree a particular pattern matches the characteristics of an already-formed category in BARTMAP. Finally, BARTMAP is far simpler to implement than, for example, backpropagation for feed-forward neural networks and the training algorithm of support vector machines.

The remainder of this paper is organized as follows. Section 2 begins with a description of Fuzzy ART and Fuzzy ARTMAP, followed by how BARTMAP performs biclustering. The experimental data, design, and results are presented and discussed in Section 3. We conclude the paper in Section 4.