Possibilistic Biclustering for Discovering Value-Coherent Overlapping $$\delta $$ δ -Biclusters

-Biclusters




Pradipta Maji1   and Sushmita Paul1  


(1)
Indian Statistical Institute, Kolkata, West Bengal, India

 



 

Pradipta Maji (Corresponding author)

Email: pmaji@isical.ac.in


 

Sushmita Paul

Email: sushmita_t@isical.ac.in


Abstract

The advent of DNA microarray technologies has revolutionized the experimental study of gene expression. Microarrays have been used to study different kinds of biological processes.



10.1 Introduction


The advent of DNA microarray technologies has revolutionized the experimental study of gene expression. Microarrays have been used to study different kinds of biological processes. It enables monitoring the transcription levels of many thousands of genes, while the cell undergoes specific conditions or processes [20]. The applications of such technology range from gene functional annotation and genetic network reconstruction to diagnosis of disease conditions and characterizing effects of medical treatment.

Clustering is one of the most popular approaches for analyzing gene expression data [15, 25] and has proved to be successful in many applications such as discovering gene pathway, gene classification, and function prediction [15, 20, 25]. Traditional clustering methods such as hierarchical clustering [23], $$k$$-means algorithm [22], and self organizing map [40] assume that genes in a cluster behave similarly over all the conditions. These methods produce reliable results for microarray experiments performed on homogeneous conditions. However, when the conditions of an experiment vary greatly, the assumption is no longer appropriate. In this regard, it is desirable to develop approaches that can detect those relevant conditions under which the behavior similarity between genes of a potential group exists. This leads to a promising paradigm of clustering, called biclustering.

The term biclustering [21] refers to a distinct class of clustering algorithms that performs simultaneous row–column clustering. The difference between clustering and biclustering is that clustering can be applied to either rows or columns of the data matrix separately. Biclustering, on the other hand, performs clustering in these two dimensions simultaneously. This means that clustering derives a global model while biclustering produces a local model. When clustering algorithms are used, each gene in a given gene cluster is defined using all conditions. Similarly, each condition in a condition cluster is characterized by the activity of all the genes that belong to it. However, each gene in a bicluster is selected using only a subset of the conditions and each condition in a bicluster is selected using only a subset of the genes. The goal of biclustering techniques is thus to identify subgroups of genes and subgroups of conditions, by performing simultaneous clustering of both rows and columns of gene expression matrix, instead of clustering these two dimensions separately.

Hence, unlike clustering algorithms, biclustering algorithms identify groups of genes that show similar activity patterns under a specific subset of the experimental conditions. Therefore, biclustering approach is the key technique to use when one or more of the following situations applies: (i) only a small set of the genes participates in a cellular process of interest; (ii) an interesting cellular process is active only in a subset of conditions; and (iii) a single gene may participate in multiple pathways that may or may not be coactive under all conditions. For these reasons, biclustering should identify groups of genes and conditions, obeying the following restrictions: (i) a cluster of genes should be defined with respect to only a subset of conditions; (ii) a cluster of conditions should be defined with respect to only a subset of genes; and (iii) the clusters should not be exclusive and/or exhaustive: a gene or condition should be able to belong to more than one cluster or to no cluster at all and be grouped using a subset of conditions or genes. Additionally, robustness in biclustering algorithms is especially relevant because of two additional characteristics of the systems under study. The first characteristic is the sheer complexity of gene regulation processes that require powerful analysis tools. The second characteristic is the level of noise in actual gene expression experiments that makes the use of intelligent statistical tools indispensable.

The term biclustering was initially introduced by Hartigan [21] as a way to cluster rows and columns of a matrix simultaneously for finding biclusters with minimum row variance. Based on the row variance, Tibshirani et al. [43] proposed a permutation-based method to induce the optimal number of biclusters. In addition to use the row variance defined by Hartigan [21], Cho et al. [12] also used the total squared residue to quantify the homogeneity of a bicluster. Therefore, their framework is applicable for finding both constant biclusters and value-coherent biclusters. However, the term biclustering was first used by Cheng and Church in gene expression data analysis [11] and an additive biclustering model was proposed in [11], for gene expression data by introducing the residue of an element in the bicluster and the mean squared residue of a submatrix. In addition, this method adjusts that measure to reject trivial biclusters by means of row variance. Yang et al. [51] generalized this additive biclustering model to incorporate null values and proposed a probabilistic algorithm, called flexible overlapped biclustering algorithm, that can discover a set of possibly overlapping biclusters simultaneously. Getz et al. [19] presented a coupled two-way clustering algorithm that uses hierarchical clustering applied separately to each dimension and then combines both results to get final biclusters. Tang et al. [42] presented an interrelated two-way clustering algorithm that combines the results of one-way clustering on both gene and sample dimensions to produce biclusters. Obviously, the quality of biclusters produced by these methods depends on the clusters generated at each dimension.

To discover row-constant or column-constant biclusters hidden in noisy data, several approaches have been proposed such as the model proposed by Califano et al. [7], Bayesian-based approach of Sheng et al. [37], probabilistic model of Segal et al. [36], Gibbs sampling-based scheme of Wu et al. [49], plaid model of Lazzeroni and Owen [28], order preserving submatrix model of Ben-Dor et al. [1] and Liu and Wang [30], model of Murali and Kasif [33], and bipartite graph-based model of Tanay et al. [41]. To address the biclustering problem, recently several stochastic search techniques such as simulated annealing [6], evolutionary algorithm [14], and genetic algorithm [9] have also been employed. In [14], Divina and Aguilar-Ruiz proposed a biclustering method based on evolutionary algorithms that searches for biclusters following a sequential covering strategy. The main objective of this approach is to find biclusters of maximum size with mean squared residue lower than a given threshold. It also looks for biclusters with a relatively high row variance and with a low level of overlapping among biclusters. Lee et al. [29] and Sill et al. [38] used sparse singular value decomposition method to address the biclustering problem, while Sutheeworapong et al. [39] proposed a biclustering approach to analyze gene expression data with iterative optimization technique. Some other notable works are reported in [10, 35]. A survey on different biclustering algorithms for biological data analysis is reported in [31]. Also, the comparative analysis of different biclustering algorithms can be found in [17].

However, most of the algorithms reported earlier find exclusive biclusters, which is inappropriate in the biological context. Since biological processes are not independent of each other, many genes participate in multiple different processes. Each gene, therefore, should be assigned to multiple biclusters whenever biclusters are identified with processes. Hence, one of the main problems with biclustering technique is the uncertainty. Some of the sources of this uncertainty include incompleteness and vagueness in bicluster definitions of microarray data. In this background, two major soft computing techniques, namely, fuzzy sets theory [52] and rough sets theory [34], have gained popularity in modeling and propagating uncertainty. Recently, using rough sets and fuzzy sets, some biclustering algorithms have been proposed to discover value-coherent overlapping biclusters [8, 18, 44–48]. In these methods, the memberships of an entire row or column in different biclusters are computed directly to find out overlapping biclusters without considering the membership of each element or point of the gene expression data. The membership of an element is obtained either by multiplying or averaging the memberships of corresponding row and column of that element. In effect, there is no direct relation between the membership of an element and its residue value. However, the membership of each element must be dependent on its residue value directly to generate highly coherent biclusters.

In this chapter, a novel possibilistic biclustering (PBC) algorithm [13] is presented. The PBC is based on the concept of possibilistic clustering algorithm of Krishnapuram and Keller [27]. The PBC algorithm employs an iterative process to find biclusters of larger volume with stronger coherence and particularly with a high degree of overlapping. During each iteration of the PBC algorithm, the possibilistic memberships of all elements or points with respect to every bicluster are calculated and finally, the membership of an entire row or column is calculated from the memberships of the elements present in that row or column. Depending on that membership value, the biclusters are enlarged or degenerated. The main difference between the PBC method and other existing overlapping methods is that the PBC method offers an efficient way to calculate the membership of every point rather than the membership of an entire row or column, which is desirable to generate value-coherent biclusters. Also, instead of taking contribution of all rows and columns, the PBC method considers only those rows and columns whose membership values are greater than a given threshold. Based on this criterion, a novel possibilistic biclustering algorithm is presented in this chapter to discover a set of overlapping biclusters with mean squared residue lesser than a predefined threshold $$\delta $$. A mathematical analysis on the convergence property of the PBC algorithm is also reported. Some quantitative measures are presented for evaluating the quality of selected overlapping biclusters. The effectiveness of the PBC algorithm, along with a comparison with the existing algorithms, is demonstrated on yeast microarray data.

The structure of the rest of this chapter is as follows: Sect. 10.2 briefly introduces necessary definitions related to biclustering method. In Sect. 10.3, a new possibilistic biclustering algorithm, termed as the PBC, is presented. Some quantitative performance measures are introduced in Sect. 10.4, along with some existing measures, to evaluate the quality of selected biclusters. In Sect. 10.5, extensive experimental results of the PBC algorithm are discussed and compared to those generated by the algorithms of Cheng and Church [11], Divina and Aguilar-Ruiz [14], and Yang et el. [51]. Concluding remarks are given in Sect. 10.6.


10.2 Biclustering and Possibilistic Clustering


This section presents a brief introduction to the basic notions of possibilistic clustering and biclustering method.


10.2.1 Basics of Biclustering


Let $$G=\{g_1,\cdots ,g_i,\cdots ,g_M\}$$ and $$E=\{c_1,\cdots ,c_j,\cdots ,c_N\}$$ be the set of genes and set of experimental conditions involved in gene expression data measurement, respectively. The result can be represented by a matrix $$D$$ with the set of rows $$G$$ and set of columns $$E$$. Each element $$a_{ij} \in D$$ corresponds to the expression information of gene $$g_i$$ in experiment $$c_j$$. A bicluster of a gene expression data is defined to be a subset of genes that exhibit similar behavior under a subset of experimental conditions, and vice versa. Thus, in the gene expression data matrix $$D$$, a bicluster will appear as a submatrix of $$D$$. This submatrix is denoted by the pair ($$I,J$$), where $$|I| \le |G|$$ and $$|J| \le |E|$$. The volume of a bicluster is defined as the number of elements $$a_{ij}$$ such that $$i \in I$$ and $$j \in J$$ that will appear as a submatrix of $$D$$.

A319338_1_En_10_Fig1_HTML.gif


Fig. 10.1
Expression matrix: row and column represent gene and condition, respectively


Example 10.1

Suppose the expression matrix $$D$$ consists of $$10$$ genes and $$8$$ conditions as shown in Fig. 10.1, where the rows of the matrix represent the genes and the columns represent the conditions. Then, a bicluster defined over the matrix $$D$$ could be ({1, 3, 5}, {2, 4, 7}), thus consisting of genes $$\{g_1,g_3,g_5\}$$ and of conditions $$\{c_2,c_4,c_7\}$$. The volume of this bicluster is $$9$$. In Fig. 10.1, the elements belonging to the bicluster are highlighted.


Definition 10.1

Let ($$I_k, J_k$$) be the $$k$$th bicluster $$B_k$$, then the base of a gene$$g_i$$ is defined as [11]


$$\begin{aligned} a_{iJ_k} = \frac{1}{|J_k|}{\sum _{j \in J_k}a_{ij}}, \end{aligned}$$

(10.1)
while the base of a condition$$c_j$$ is defined as [11]


$$\begin{aligned} a_{I_kj} = \frac{1}{|I_k|}{\sum _{i \in I_k}a_{ij}}. \end{aligned}$$

(10.2)
The base of the bicluster$$B_k$$ is the mean of all entries contained in ($$I_k, J_k$$), that is,


$$\begin{aligned} a_{I_kJ_k} = \frac{1}{|I_k|.|J_k|}{\sum _{i \in I_k}\sum _{j \in J_k}a_{ij}}. \end{aligned}$$

(10.3)

Note that in the above definitions, $$a_{iJ_k}$$ and $$a_{I_kj}$$ correspond to the means of the $$i$$th row and $$j$$th column of the bicluster ($$I_k, J_k$$), respectively.


Definition 10.2

The residue of an entry $$a_{ij}$$ of a bicluster ($$I_k, J_k$$) is given by


$$\begin{aligned} r_{ij} = (a_{ij} - a_{iJ_k} - a_{I_kj} + a_{I_kJ_k}). \end{aligned}$$

(10.4)
In order to quantify the difference between the actual value and expected value of an entry predicted from the corresponding gene base, condition base, and bicluster base, the concept of residue is used. The residue is an indicator of the degree of coherence of an element with respect to the remaining ones in the bicluster, given the tendency of the relevant gene and the relevant condition. The lower the residue, the stronger the coherence.


Definition 10.3

The mean squared residue of a bicluster ($$I_k,J_k$$) is defined as follows [11]:


$$\begin{aligned} H_k= \frac{1}{|I_k|.|J_k|}{\sum _{i \in I_k}\sum _{j \in J_k}r^{2}_{ij}}. \end{aligned}$$

(10.5)
The mean squared residue is the variance of the set of all elements in the bicluster, plus the mean row variance and the mean column variance. The lower the mean squared residue, the stronger the coherence exhibited by the bicluster, and the better the quality of the bicluster. If a bicluster has a mean squared residue lower than a given threshold $$\delta $$, then the bicluster is termed as a $$\delta $$-bicluster.


Definition 10.4

Let ($$I_k, J_k$$) be a bicluster, then the row variance of ($$I_k, J_k$$) is defined as follows:


$$\begin{aligned} \mathrm{VAR}_{I_kJ_k} =\frac{1}{|I_k|.|J_k|}{\sum _{i \in I_k}\sum _{j \in J_k}(a_{ij}-a_{iJ_k})^2}. \end{aligned}$$

(10.6)
The row variance may be referred to be relatively large to reject trivial bicluster. By using row variance as an accompanying score, one wants to guarantee that the bicluster captures genes exhibiting fluctuating yet coherent trends under some set of conditions.


10.2.2 Possibilistic Clustering


One of the most widely used prototype-based fuzzy partitional clustering algorithms is fuzzy $$c$$-means [4]. It offers the opportunity to deal with the data that belongs to more than one cluster at the same time. It assigns memberships to an object which are inversely related to the relative distance of the object to cluster prototypes. Also, it can deal with the uncertainties arising from overlapping cluster boundaries.

However, the fuzzy $$c$$-means may be inaccurate in a noisy environment [27] as the resulting membership values do not always correspond well to the degrees of belonging of the data. In real data analysis, noise and outliers are unavoidable. Hence, to reduce this weakness, and to produce memberships that have a good explanation of the degrees of belonging for the data, Krishnapuram and Keller [27] proposed the possibilistic $$c$$-means algorithm that uses a possibilistic type of membership function to describe the degree of belonging. It partitions a set of objects $$X$$ into $$c$$ clusters by minimizing the objective function


$$\begin{aligned} J = \sum _{i=1}^{c} \sum _{j=1}^{n} (\nu _{ij})^m||x_j-v_i||^2 + \sum _{i=1}^{c} \eta _i \sum _{j=1}^{n} (1-\nu _{ij})^m \end{aligned}$$

(10.7)
where $$\eta _i$$ represents the scale parameter, $$m$$ is a weighting exponent called the fuzzifier, $$\nu =[\nu _{ij}]_{c~\times ~n}$$ is the membership matrix, and the value of $$\nu _{ij}$$ depends only on the similarity between the object $$x_j$$ and the centroid $$v_i$$. The resulting partition of the data can be interpreted as a possibilistic partition, and the membership values may be interpreted as degrees of possibility of the objects belonging to the classes, that is, the compatibilities of the objects with the centroids. A brief description of both fuzzy $$c$$-means and possibilistic $$c$$-means algorithms is available in Chap  8.


10.3 Possibilistic Biclustering Algorithm


In this section, a new possibilistic biclustering (PBC) algorithm, proposed by Das and Maji [13], is presented, incorporating the concept of possibilistic clustering algorithm of Krishnapuram and Keller [27] into biclustering framework. The integration of the possibilistic membership of fuzzy sets and biclustering algorithm makes the PBC algorithm effective for generating value-coherent overlapping biclusters with mean squared residue lower than a predefined threshold.


10.3.1 Objective Function


The PBC algorithm partitions a set of elements or points $$\{a_{ij}\}$$ of a gene expression data $$D$$ into $$K$$ biclusters by minimizing the following objective function


$$\begin{aligned} \overline{J}= \sum _{k=1}^K \sum _{i \in I_k} \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m r_{kij}^2+ \sum _{k=1}^K {\fancyscript{H}}_k \sum _{i \in I_k} \sum _{j \in J_k} (1- {\fancyscript{U}}_{kij} )^m \end{aligned}$$

(10.8)
where $${\fancyscript{U}}_{kij} \in [0,1]$$ represents the possibilistic membership of the element or point $$a_{ij} \in D$$ into the $$k$$th bicluster $$B_k$$ represented as ($$I_k,J_k$$), $$m \in [1, \infty )$$ is the fuzzifier, and $$K$$ is the total number of biclusters. The term $$r_{kij}$$ is the residue of the element $$a_{ij}$$ in the $$k$$th bicluster, which has the similar expression as that in (10.4) and is given by


$$\begin{aligned} r_{kij}=(a_{ij}-a_{iJ_k}-a_{I_kj}+a_{I_kJ_k}) \end{aligned}$$

(10.9)
where $$a_{iJ_k}$$, $$a_{I_kj}$$, and $$a_{I_kJ_k}$$ represent the means or bases of the $$i$$th gene, $$j$$th condition, and $$k$$th bicluster, respectively. Hence, the first term $$({\fancyscript{U}}_{kij}^m r_{kij}^2)$$ of (10.8) is the fuzzy squared residue of the element $$a_{ij}$$ in the $$k$$th bicluster. Note that the term $$(1-{\fancyscript{U}}_{kij})^m$$ in (10.8) is monotone decreasing function of $${\fancyscript{U}}_{kij}$$. This forces $${\fancyscript{U}}_{kij}$$ to be as large as possible to avoid the trivial solutions.

The parameter $${\fancyscript{H}}_k$$ determines the residue value for which the membership value of a point or element becomes 0.5. Hence, it needs to be chosen depending on the desired bandwidth of the possibility (membership) distribution for each bicluster. This value could be the same for all biclusters if all biclusters are expected to be similar. In general, it is desirable that $${\fancyscript{H}}_k$$ relates to the overall size and shape of bicluster $$B_k$$. Also, it is to be noted that $${\fancyscript{H}}_k$$ determines the relative degree to which the second term in the objective function of (10.8) is important compared with the first. If the two terms are to be weighted roughly equally, then $${\fancyscript{H}}_k$$ should be of the order of $$r_{kij}^2$$. In this work, the following definition is used:


$$\begin{aligned} {\fancyscript{H}}_k=P.\frac{\displaystyle \sum _{i \in I_k} \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m r_{kij}^2}{\displaystyle \sum _{i \in I_k} \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m}. \end{aligned}$$

(10.10)
This choice makes $${\fancyscript{H}}_k$$ proportional to the fuzzy mean squared residue of bicluster $$B_k$$. The denominator of $${\fancyscript{H}}_k$$ represents the fuzzy cardinality of bicluster $$B_k$$. Typically, $$P$$ is chosen to be 1.

Solving the objective function of (10.8) with respect to $${\fancyscript{U}}_{kij}$$, we get the possibilistic membership of an element $$a_{ij} \in D$$ into $$k$$th bicluster that follows next:


$$\begin{aligned} {\fancyscript{U}}_{kij}=\frac{1}{\displaystyle 1+\left( \frac{r_{kij}^2}{\fancyscript{H}_k}\right) ^{\frac{1}{m-1}}}. \end{aligned}$$

(10.11)
Hence, in each iteration, the updated value of $${\fancyscript{U}}_{kij}$$ depends only on the residue $$r_{kij}$$ of the element $$a_{ij}$$ with respect to the $$k$$th bicluster $$B_k$$. If the value of $$r_{kij}$$ is zero, then the membership of that point with respect to the $$k$$th bicluster is 1.0. If the value of $$r_{kij}$$ is greater than zero, then the membership value of that point is less than 1.0 and 0.0 when $$r_{kij} \rightarrow \infty $$. Hence, $$0.0 \le {\fancyscript{U}}_{kij} \le 1.0$$.

After computing the membership of each point $$a_{ij} \in D$$ with respect to all biclusters, the memberships of all rows and columns are computed with respect to all biclusters. If the $$k$$th bicluster $$B_k$$ has $$|I_k|$$ rows and $$|J_k|$$ columns, then the membership of the $$i$$th row in the $$k$$th bicluster $$B_k$$ is defined as follows:


$$\begin{aligned} {\fancyscript{U}}_{kiJ}=\left[ \frac{1}{|J_k|}\sum _{j \in J_k} {\fancyscript{U}}_{kij}^m \right] ^{\frac{1}{m}} \end{aligned}$$

(10.12)
and the membership of the $$j$$th column in the $$k$$th bicluster is


$$\begin{aligned} {\fancyscript{U}}_{kIj}=\left[ \frac{1}{|I_k|}\sum _{i \in I_k} {\fancyscript{U}}_{kij}^m \right] ^{\frac{1}{m}}. \end{aligned}$$

(10.13)
In each iteration, if the maximum membership value of the $$i$$th row (respectively, $$j$$th column) is greater than a threshold $$\xi $$ and if the difference between the maximum membership and the membership with respect to a particular bicluster of that row (respectively, column), which is greater than $$\xi $$, is less than a threshold $$\eta $$, then this row (respectively, column) will be selected for insertion into that particular bicluster. In this way, all rows and columns are examined with respect to all biclusters and are inserted successfully into the biclusters. Hence, the rows and columns, which are inserted in this process, have the membership values greater than $$\xi $$. Here, the threshold $$\xi $$ is used to generate highly coherent biclusters. On the other hand, if the membership of a row or column is very high in some biclusters, then the row or column is inserted into only those biclusters. This is adjusted using the predefined threshold $$\eta $$.

After all insertion, the mean squared residue of each bicluster is computed and compared with a given threshold $$\delta $$. If the mean squared residue value of the $$k$$th bicluster $$B_k$$ is greater than $$\delta $$, then the row or column with least membership value in that bicluster is deleted and the process is repeated until the value becomes less than $$\delta $$. In this way, the PBC algorithm generate highly coherent overlapping biclusters with lower mean squared residue value.


10.3.2 Bicluster Means


In each iteration, the means or bases of the $$i$$th gene, $$j$$th condition, and $$k$$th bicluster are calculated to compute the mean squared residue of each bicluster based on the possibilistic membership values of all rows and columns in different biclusters. The means or bases of the $$i$$th gene, $$j$$th condition, and $$k$$th bicluster for the PBC algorithm are obtained by solving (10.8) with respect to $$a_{iJ_k}$$, $$a_{I_kj}$$, and $$a_{I_kJ_k}$$, respectively:


$$\begin{aligned} a_{iJ_k}=\frac{1}{|J_k|{\fancyscript{U}}_{kiJ}^m} \left\{ \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m (a_{ij} - a_{I_kj}) \right\} +a_{I_kJ_k} \end{aligned}$$

(10.14)



$$\begin{aligned} a_{I_kj}=\frac{1}{|I_k|{\fancyscript{U}}_{kIj}^m} \left\{ \sum _{i \in I_k} {\fancyscript{U}}_{kij}^m (a_{ij} - a_{iJ_k}) \right\} +a_{I_kJ_k} \end{aligned}$$

(10.15)



$$\begin{aligned} a_{I_kJ_k}=\frac{\displaystyle \sum _{i \in I_k} {\fancyscript{U}}_{kiJ}^ma_{iJ_k}}{\displaystyle \sum _{i \in I_k} {\fancyscript{U}}_{kiJ}^m} +\frac{\displaystyle \sum _{j \in J_k} {\fancyscript{U}}_{kIj}^ma_{I_kj}}{\displaystyle \sum _{j \in J_k} {\fancyscript{U}}_{kIj}^m} -\frac{\displaystyle \sum _{i \in I_k}\sum _{j \in J_k}{\fancyscript{U}}_{kij}^ma_{ij}}{\displaystyle \sum _{i \in I_k} \sum _{j \in J_k}{\fancyscript{U}}_{kij}^m}. \end{aligned}$$

(10.16)
Hence, the base of the $$i$$th gene $$a_{iJ_k}$$ in the $$k$$th bicluster $$B_k$$ depends on the means of all conditions present in that bicluster as well as the base of that bicluster. Similarly, the base of the $$j$$th condition $$a_{I_kj}$$ in the $$B_k$$ bicluster depends on the means of all genes present in the $$B_k$$ and the base of $$B_k$$.


10.3.3 Convergence Condition


In this subsection, a mathematical analysis on the convergence property of the PBC algorithm is presented. In the PBC algorithm, the means or bases of the $$i$$th gene, $$j$$th condition, and $$k$$th bicluster are calculated using (10.14), (10.15), and (10.16), respectively. However, these three equations can be written as


$$\begin{aligned} \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m \cdot a_{iJ_k}= \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m (a_{ij} - a_{I_kj}+a_{I_kJ_k}) \end{aligned}$$

(10.17)



$$\begin{aligned} \sum _{i \in I_k} {\fancyscript{U}}_{kij}^m \cdot a_{I_kj}= \sum _{i \in I_k} {\fancyscript{U}}_{kij}^m (a_{ij} - a_{iJ_k}+a_{I_kJ_k}) \end{aligned}$$

(10.18)



$$\begin{aligned} \sum _{i \in I_k} \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m \cdot a_{I_kJ_k}= \sum _{i \in I_k} \sum _{j \in J_k} {\fancyscript{U}}_{kij}^m (a_{iJ_k}+a_{I_kj} -a_{ij}) \end{aligned}$$

(10.19)
Hence, (10.17) represents a set of linear equations in terms of $$a_{iJ_k}$$ if $${\fancyscript{U}}_{kij}$$, $$a_{I_kj}$$, and $$a_{I_kJ_k}$$ are kept constant. Similarly, (10.18) and (10.19) represent a set of linear equations in terms of $$a_{I_kj}$$ and $$a_{I_kJ_k}$$, respectively. A simple way to analyze the convergence property of the algorithm is to view (10.14), (10.15), and (10.16) as the Gauss-Seidel iterations for solving the set of linear equations. The Gauss-Seidel algorithm is guaranteed to converge if the matrix representing each equation is diagonally dominant [24]. This is a sufficient condition, not a necessary one. The iteration may or may not converge if the matrix is not diagonally dominant [24]. The matrix corresponding to (10.14) is given by:


$$\begin{aligned} \tilde{\mathrm {A}}=\left[ \begin{array}{ccccc} \tilde{a}_1 &{} 0 &{} \cdots &{} \cdots &{} 0 \\ 0 &{} \tilde{a}_2 &{} 0 &{} \cdots &{} 0 \\ \cdots &{} \cdots &{} \cdots &{} \cdots &{} \cdots \\ 0 &{} 0 &{} \cdots &{} \cdots &{} \tilde{a}_{I_k} \\ \end{array} \right] ;~ ~\tilde{a}_i=\sum _{j \in J_k} {\fancyscript{U}}_{kij}^m \end{aligned}$$

(10.20)
Similarly, the matrices corresponding to (10.15) and (10.16) are given by


$$\begin{aligned} \tilde{\mathrm {B}}=\left[ \begin{array}{ccccc} \tilde{b}_1 &{} 0 &{} \cdots &{} \cdots &{} 0 \\ 0 &{} \tilde{b}_2 &{} 0 &{} \cdots &{} 0 \\ \cdots &{} \cdots &{} \cdots &{} \cdots &{} \cdots \\ 0 &{} 0 &{} \cdots &{} \cdots &{} \tilde{b}_{J_k} \\ \end{array} \right] ;~ ~\tilde{b}_j=\sum _{i \in I_k} {\fancyscript{U}}_{kij}^m \end{aligned}$$

(10.21)



$$\begin{aligned} \tilde{\mathrm {C}}=\left[ \begin{array}{ccccc} \tilde{c}_1 &{} 0 &{} \cdots &{} \cdots &{} 0 \\ 0 &{} \tilde{c}_2 &{} 0 &{} \cdots &{} 0 \\ \cdots &{} \cdots &{} \cdots &{} \cdots &{} \cdots \\ 0 &{} 0 &{} \cdots &{} \cdots &{} \tilde{c}_{K} \\ \end{array} \right] ;~ ~\tilde{c}_k=\sum _{i \in I_k} \sum _{j \in J_k}{\fancyscript{U}}_{kij}^m \end{aligned}$$

(10.22)
For $$\tilde{\mathrm {A}}$$, $$\tilde{\mathrm {B}}$$, and $$\tilde{\mathrm {C}}$$ to be diagonally dominant, we must have


$$\begin{aligned} \tilde{a}_i \ge 0; \qquad \tilde{b}_j \ge 0; \qquad \tilde{c}_k \ge 0. \end{aligned}$$

(10.23)
This is the sufficient condition for matrices $$\tilde{\mathrm {A}}$$, $$\tilde{\mathrm {B}}$$, and $$\tilde{\mathrm {C}}$$ to be diagonally dominant. Under this condition, the iteration would converge if (10.14–10.16) are, repetitively, applied with $${\fancyscript{U}}_{kij}$$ kept constant. In practice, (10.11–10.13) and (10.14–10.16) are applied alternatively in the iterations. The condition in (10.23) is still correct according to Bezdek’s convergence theorem of fuzzy $$c$$-means algorithm [2, 3] and Yan’s convergence analysis of the fuzzy curve-tracing algorithm [50]. All three matrices $$\tilde{\mathrm {A}}$$, $$\tilde{\mathrm {B}}$$, and $$\tilde{\mathrm {C}}$$ are also the Hessian (second order derivative) of $$\overline{J}$$ with respect to $$a_{iJ_k}$$, $$a_{I_kj}$$, and $$a_{I_kJ_k}$$. As all three matrices $$\tilde{\mathrm {A}}$$, $$\tilde{\mathrm {B}}$$, and $$\tilde{\mathrm {C}}$$ are diagonally dominant, all their eigenvalues are positive. Also, the Hessian of $$\overline{J}$$ with respect to $${\fancyscript{U}}_{kij}$$ can be easily shown to be diagonal matrix and are positive definite. Thus, according to the theorem derived by Bezdek [2, 3] and the analysis done by Yan [50], it can be concluded that the PBC algorithm converges, at least along a subsequence, to a local optimum solution as long as the condition in (10.23) is satisfied. Intuitively, the objective function $$\overline{J}$$ reduces in all steps corresponding to (10.11–10.13) and (10.14–10.16), so the compound procedure makes the function $$\overline{J}$$ descent strictly.

Only gold members can continue reading. Log In or Register to continue

Related posts:

  1. Rough Sets for Insilico Identification of Differentially Expressed miRNAs
  2. Fuzzy Measures and Weighted Co-Occurrence Matrix for Segmentation of Brain MR Images
  3. Mutual Information Based Supervised Attribute Clustering for Microarray Sample Classification
  4. f-Information Measures for Selection of Discriminative Genes from Microarray Data

Stay updated, free articles. Join our Telegram channel
Tags:
May 25, 2017 | Posted by in GENERAL & FAMILY MEDICINE | Comments Off on Possibilistic Biclustering for Discovering Value-Coherent Overlapping $$\delta $$ δ -Biclusters

Full access? Get Clinical Tree
Get Clinical Tree app for offline access