Measuring the Quality of Shifting and Scaling Patterns in Biclusters

Measuring the Quality of Shifting and Scaling Patterns in Biclusters Beatriz Pontes1, Raúl Giráldez2, and Jesús S. Aguilar-Ruiz2 1Department of Computer Science, University of Seville Avenida Reina Mercedes s/n, 41012, Sevilla, Spain [email protected] http://www.lsi.us.es/˜bepontes/index-en.html 2School of Engineering, Pablo de Olavide University Ctra. de Utrera, km.1, 41013, Sevilla, Spain {giraldez,aguilar}@upo.es http://www.upo.es/eps/{giraldez,aguilar} Abstract. The most widespread biclustering algorithms use the Mean Squared Residue (MSR) as measure for assessing the quality of biclusters. MSR can identify correctly shifting patterns, but fails at discovering biclusters presenting scaling patterns. Virtual Error (VE) is a measure which improves the performance of MSR in this sense, since it is effective at recognizing biclusters containing shifting patters or scaling patterns as quality biclusters. However, VE presents some drawbacks when the biclusters present both kind of patterns simultaneously. In this paper, we propose a improvement of VE that can be integrated in any heuristic to discover biclusters with shifting and scaling patterns simultaneously. 1 Introduction The use of microarray techniques allows to study the activity of thousands of genes at a time, producing in this way a huge amount of data. Usually, the resulting data is organized in a matrix, called an expression matrix, where columns may represent genes and rows represent experimental conditions. An element of such expression matrix stands for the expression level of a given gene under a specific condition [3,18]. The interest in discovering knowledge from gene expression data has experimented an enormous increase with the development of microarray techniques. Biclustering [12] is becoming a popular data mining technique due to its ability to explore at the same time both dimensions of data, as opposed to clustering techniques [19], that can only use one dimension. In this sense, microarray is a suitable context for the application of biclustering techniques, since they can consider both genes and experimental conditions at extracting useful knowledge. Thus, in this context, a bicluster is a subset of genes under a subset of conditions. In particular, those biclusters where the subset of genes shows a common tendency under the subset of conditions are of special interest. In general, biclustering is much more complex than clustering [14]. In fact, finding significant biclusters in microarray data has been proven to be a NP-hard problem [17]. Cheng and Church [7] were the first in applying biclustering to gene expression data. They introduced one of the most popular biclustering algorithms that combines a greedy search heuristic for finding biclusters with a measure for assessing the quality of such biclusters. This measure, named Mean Squared Residue (MSR), has been used by many researchers who have proposed different heuristics for biclustering biological data. Aguilar et al. [2] developed an approach based on local nearness. Yang et al. [21] proposed an iterative algorithm for finding a predefined number of biclusters. Cano et al. [6] based their proposal on fuzzy technology and spectral clustering. Other approaches, such as Divina and Aguilar [10] and Bleuler et al. [4], have been based on evolutionary computation, while Bryan et al. [5] applied simulated annealing as heuristic. Recently, MSR has also been incorporated as cost function in multiobjective heuristics based on Particle Swarm Optimization [13] and Artificial Immune Systems [9]. Although MSR has been used in many proposals for finding biclusters, it nevertheless has been proven to be inefficient for finding certain types of biclusters in microarray data, especially when they present strong scaling tendencies [1]. Thus, we introduced in previous works an alternative measure named Virtual Error (VE) [15]. This measure is based on the concept of behavioural patterns, which aim at identifying common patterns between genes or conditions. VE is effective at recognizing biclusters containing shifting patters or scaling patterns as quality biclusters. However, it presents some drawbacks when both kind of patterns are presented simultaneously in the same bicluster. In this paper, we propose a novel variant of VE, called Transposed Virtual Error (VEt), that allows to find biclusters that MSR and VE do not recognize as interesting ones. This paper is organized as follows. In the next section, an description of the shifting and scaling patterns is given. We then provide a formal definition of VEtin Section 3, followed by a formal analysis in Section 4, demonstrating its strength with regard to the behavioural patterns. In Section 5 we discuss the consequences of the theorems presented in this work, providing a test of the effect of the noise on the VEt. Finally, we summarize the main conclusions in Section 6. 2 Behavioural Patterns in Gene Expression Data When all the genes of a bicluster follow a similar tendency under the set of conditions, then such a bicluster may be potentially biologically interesting. Therefore, it seems to be a good idea to develop a quality measure for biclusters based on the idea of behavioural patterns for gene expression. Aguilar [1] presented an in-depth discussion on thepossiblepatternsingene expression data. He described formally two kind of patterns: shifting and scaling patterns. They have been defined using numerical relations among the values in a bicluster. Several works based their principle in the pattern concept in order to mine the data. Xu et al [20] propose a biclustering algorithm for mining shifting and scaling coregulation patterns on gene expression data. Nevertheless, they do not provide a quality measure, but use a model-based heuristic instead. Furthermore, they are only able to identify global shifting and scaling patterns, while local ones seem to be more interesting since they depict the general situation [1] Let Bbe a bicluster made up of Iexperimental conditions and Jgenes. Each element in Bis represented by bij ∈B. This way, the bicluster Bfollows a perfect shifting pattern if its values can be obtained by adding a constant-condition number βito a typical value for each gene (πj). βiis said to be the shifting coefficient for condition i. In this case, the expression values in the bicluster fulfil the following equation: bij =πj+βi(1) Similarly, a bicluster follows a perfect scaling pattern changing the additive value in the former equation by a multiplicative one. This new term αiis called the scaling coefficient, and represents a constant value for each condition. The following equation defines whether a bicluster follows a perfect scaling pattern or not: bij =πj×αi(2) Shifting and scaling patterns may be put together in a new kind of pattern called combined pattern. In fact, it is the most probable situation when working with real genetic data. In this situation, the expression values can be obtained using both coefficients, shifting and scaling coefficients. The equation that must be fulfilled by the values in this case can be represented by merging 1 and 2: bij =πj×αi+βi(3) Figure 1 shows an example of a bicluster obtaining from synthetic data. This is a typical visualization of bicluster, where conditions are represented in the x-axis, the values of gene expression are represented in the y-axis and each line is a gene. As we can see, there are four genes gj(with 1≤j≤4) and five conditions ci(with 1≤i≤5). This bicluster contains both shifting and scaling patterns. The matrices below describe the factor decomposition of the numerical values. Havingalookatfigure1wecouldsaythatgenesg1,g3and g4present a similar behaviour across the conditions, although g4has a different tendency between the last two conditions. On the contrary, the tendency of gene g2varies from the other genes, since its behaviour is always increasing across all the conditions. Gene g2is difficult to be associated to a perfect pattern visually because its shifting coefficients βiare closed to the product πj×αi. Therefore, identifying biclusters with both shifting and scaling patterns might be a difficult task due to the complexity inherent in equation 3. 0 50 100 150 200 250 300 350 Expression Value Conditions c 1 c 2 c 3 c 4 c 5 g 1 g 2 g 3 g 4 B= ⎛ ⎜ ⎜ ⎜ ⎝ 95 56 110 149 152 74 182 260 104 78 114 140 185 94 220 311 208 143 233 298 ⎞ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎝ 25 ×3 + 20 12 ×3 + 20 30 ×3 + 20 43 ×3+20 25 ×6+2 12×6+2 30×6+2 43×6+2 25 ×2 + 54 12 ×2 + 54 30 ×2 + 54 43 ×2+54 25 ×7 + 10 12 ×7 + 10 30 ×7 + 10 43 ×7+10 25 ×5 + 83 12 ×5 + 83 30 ×5 + 83 43 ×5+83 ⎞ ⎟ ⎟ ⎟ ⎠ π1π2π3π4 {πj}={25 12 30 43} α1α2α3α4α5 {αi}={362 7 5} β1β2β3β4β5 {βi}={20 2 54 10 83} Fig. 1. Bicluster containing perfect shifting and scaling patterns 3 Transposed Virtual Error Virtual Error (VE) had been designed as an evaluation measure for biclusters [15]. VE is based on the concepts of shifting and scaling patterns and is capable of identifying both kind of patterns within biclusters, although not simultaneously. This way, VE improves MSR effectiveness, since the last one can only recognize shifting patterns. The basic idea behind VE is to measure the extent to which the genes in a bicluster are similar to the general tendency. The general tendency is represented by a Virtual Gene which is created taking into account the values for every gene across the experimental conditions, but trying to capture the general behaviour with independence of the concrete numerical values. VE will have a lower value for those biclusters in which its genes are closer to the virtual gene. This is due to the fact that VE computes the numerical differences between each standardized gene and the standardized virtual gene. Therefore, the better a bicluster is, the lower its VE value will be. Furthermore, it is obvious that VE will always be greater or equal than zero. VE has been used in various evolutionary algorithms in order to find one hundred biclusters in several gene expression matrices [15,11]. These two previous works have allowed us finding interesting biclusters that could not have been obtained using MSR alone. Furthermore, the VE value for biclusters with perfect shifting and scaling patterns seems to be very close to zero [16] (magnitude of 10−15). Nevertheless, VE cannot be proven to recognize both kind of patterns simultaneously. In this work, we present an enhanced version of VE, named VEt,fromTransposed Virtual Error. We analytically prove that VEtis zero for those biclusters with perfect shifting and scaling patterns. This variation of VE has been motivated by [8], where several numeric transformations have been applied to the data in order to detect both kind of patterns. VEtis computed similarly to VE but considering the transposed bicluster. The idea here would be to create a Virtual Condition, instead of a virtual gene, and measure the differences between the standardized values for every condition and the standardized virtual condition. In the following, we explain how to create the virtual condition for a certain bicluster B, in order to compute VEtafterwards. Definition 1 (Virtual Condition). Given a bicluster Bwith Iconditions and Jgenes, we define its virtual condition as a collection of Jelements ρj,eachof them defined as the mean of the jth column: ρj=i∈Ibij I,wherebij ∈B,1≤ i≤Iand 1≤j≤J. This way, each element of the virtual condition represents a meaningful value for all the conditions, regarding each gene. Once the virtual condition has been created, the next task would consist of quantifying the way in which all the experimental conditions in the bicluster are similar to it. In order to perform an appropriate comparison, we first carry out a standardization of the virtual condition and of every experimental condition in the bicluster. This standardization allows us to capture the differences among the tendencies, with independence of the numerical values. Definition 2 (Standardization). We define the standardized bicluster ˆ Bfrom bicluster Bas a new bicluster in which its elements ˆ bij are defined by ˆ bij =bij −μci σci , where σciand μcirepresent the standard deviation and the arithmetic average of all the expression values for condition i, respectively. It has already been said that the virtual condition needs also to be standardized. Equation 4 shows how the values of the standardized virtual condition are obtained, where ρjrefers to the virtual condition value for gene j, while μρand σρrefer to the average and the deviation of the values of the virtual condition, respectively. ˆρj=ρj−μρ σρ (4) Definition 3 (Transposed Virtual Error). Given a bicluster B,andthevirtual condition ρ, Transposed Virtual Error (VEt) can be defined as the mean of the numerical differences between each standardized condition and the values of the standardized virtual condition for each gene: VE t(B)= 1 I·J i=I  i=1 j=J  j=1 (ˆ bij −ˆρj)(5) Next, we present three theorems and their proofs that demonstrate the strength of VEtwith regard to the shifting and scaling patterns. 4Analysis This section includes formal proofs that bear out the hypothesis that VEtis zero for those biclusters with perfect shifting and scaling patterns, either separately or simultaneously. Theorem 1. A bicluster presenting a perfect shifting pattern has VEtequal to zero. Proof. Let Bbe a bicluster with a perfect shifting pattern, then it is possible to refer to its elements as bij =πj+βi. Applying two simple arithmetic properties1, the mean and the deviation for each condition cican be expressed by: μci=μπ+βi;σci=σπ where μπand σπrepresent the mean and the deviation of the πvalues, respectively. Using these results we obtain the standardizes values for bij : ˆ bij =bij −μci σci =πj+βi−μπ−βi σπ =πj−μπ σπ Combining the former properties1it is easy to express the mean and standard deviation for the virtual condition as: μρ=μπ+μβ;σρ=σπ Finally, the standardized values for the virtual condition are the following: ˆρj=ρj−μρ σρ =πj+μβ−μπ−μβ σπ =πj−μπ σπ =ˆ bij As it can be seen above, the standardized virtual condition is equal to all the real conditions after being standardized. Therefore, VEthas been proven to be zero for those biclusters with perfect shifting patterns.  Theorem 2. A bicluster presenting a perfect scaling pattern has VEtequal to zero. Proof. Let Bbe a bicluster following a perfect scaling pattern, then its elements can be expressed by bij =πj×αi. Following the same reasoning that in the former proof, the mean and deviation of each condition ciare: μci=αi×μπ;σci=αi×σπ From these results we obtain the standardized values for bij : ˆ bij =bij −μci σci =πj×αi−αi×μπ αi×σπ =πj−μπ σπ Next we obtain the mean and deviation for the values of the virtual condition: μρ=μπ×μα;σρ=μα×σπ 1Being f(x)=g(x)×c1+c2, the properties related to the arithmetic mean (μf(x)) and the standard deviation (σf(x))off(x)are the following: μf(x)=μg(x)×c1+c2 and σf(x)=σg(x)×c1. And finally the standardized values for the virtual condition are: ˆρj=ρj−μρ σρ =πj×μα−μπ×μα μα×σπ =πj−μπ σπ =ˆ bij As in the previous proof, we obtain that the standardized values for the virtual condition are equal to de standardized values for all the real experimental conditions. As a consequence, VEtwill be zero for every bicluster with a perfect scaling pattern.  Theorem 3. A bicluster presenting a perfect combined pattern (shifting and scaling) has VEtequal to zero. Proof. If Bcontains a perfect combined pattern, its values can be represented by bij =πj×αi+βi. Using the same arithmetic properties as in the former proves, the mean and deviation for each condition ciare: μci=αi×μπ+βi;σci=αi×σπ And the standardized values for bij can be expressed as: ˆ bij =bij −μci σci =πj×αi+βi−αi×μπ+βi αi×σπ =πj−μπ σπ The mean and deviation for the virtual condition are the following: μρ=μπ×μα+μβ;σρ=μα×σπ And the standardized values for the virtual condition: ˆρj=ρj−μρ σρ =πj×μα+μβ−μπ×μα−μβ μα×σπ =πj−μπ σπ =ˆ bij Again, the standardized values for the virtual condition match up with the standardized values for the original conditions. Therefore, VEtwill also be zero for those biclusters following a perfect shifting and scaling pattern.  These results confirm that VEtis the first measure up to the date capable of recognizing combined patterns in gene expression data. While MSR is only capable of detecting shifting patterns, and VE cannot recognize both kind of patterns simultaneously, VEthas been proven to go beyond the other two measures. 5 Discussion In this section, we discuss the use of VEtfor bicluster evaluation. In particular, we study the value of VEtfor those biclusters in which the presence of patterns is not perfect. That is, when the tendency of the data in a bicluster is similar to a perfect pattern but does not completely match with the equation 3. In order to check the behaviour of VEtwhenever a bicluster does not follow a perfect pattern, we add an additive term εij to the combined pattern equation. The meaning of this new term corresponds to the error made by the assumption that the bicluster can be represented by a perfect pattern. bij =πj×αi+βi+εij (6) It is possible therefore to study the variations produced to VEtdepending on the values of εij . Nevertheless, it is not so simple due to the huge amount of situations depending on the distribution and the magnitude of the εij values in the data matrix. In two specific situations the value of VEtwill not be affected when the errors could be included in the former equation 6. These two cases correspond to those in which εij values are either a constant or constants per conditions (rows). In both cases it is possible to eliminate the term εij from the equation, since it can be considered to be a part of βi. Nevertheless, the cases in which εij cannot not be included in the perfect pattern equation are very difficult to study analytically. For this reason, we have performed a test to check the tendency of the VEtvalues with regard to the error values. This test consist of the addition of random errors to a synthetic bicluster with perfect shifting and scaling patterns. The original bicluster is the one shown in Fig. 1. Specifically, we have generated 100 synthetic biclusters adding random errors to the bicluster in the figure, and we have repeated this process 200 different times, varying the amplitude of the errors from one time to another. We start adding negative errors in the range of [−10,0],andobtain 100 different biclusters. Then we decrease the amplitude by 0.1and repeat the process (range [−9.90,0]). Once the amplitude of the errors has reached the zero value, we start again generating biclusters with positive errors, increasing the amplitude from 0.1up to 10. The whole process produced 100 sets of 100 biclusters with negative errors and 100 sets of 100 biclusters with positive errors (built using the same strategy as for negative). Therefore, the random errors have been drawn from an uniform distribution corresponding to the ranges. Note that the type of the error values is a double type. This introduces more diversity in the distribution of the error data. Within the process, we evaluate each produced bicluster using the three measures: MSR, VE and VEt. Then we obtain the mean of each measure for each group of 100 biclusters of the same range of errors. This data has been represented in Figs. 2, 3 and 4, where the x-axis represents the mean of the error for each amplitude (this value matches up with the value in the middle of the range of errors) and the y-axis corresponds to the mean of the specific measure for each figure. From Fig. 2 it is possible to observe that VEtpresents a linear decreasing tendency in relation to the amount of error in a bicluster. In other words, the similar a bicluster is to a perfect pattern, the lower its VEtvalue will be, and Fig. 2. VEtbehaviour in biclusters with errors Fig. 3. VE behaviour in biclusters with errors Fig. 4. MSR behaviour in biclusters with errors