MSL: A Measure to Evaluate Three-dimensional Patterns in Gene Expression Data

121Evolutionary Bioinformatics 2015:11 Introduction Microarray technology is highly used in biological research environments due to its ability to monitor, for a great gene collection, the RNA concentration levels, thus enabling the study of genetic functions of species.1 Bioinformatics and data mining have developed a vast number of computational tools that allow us to analyze data obtained using this technology and to find new knowledge that is hidden from human eyesight.2,3 One of the most studied approaches is pattern search in gene expression data. The genes exhibiting high correlation among their expression levels could be involved in similar regulatory processes.4 The relationship between correlation and functionality has been proved in several studies as in the study by D’haeseleer et al.5 Clustering techniques are suitable for performing pattern search by creating groups of genes that exhibit similar expression patterns.6 Traditional clustering algorithms analyze the whole microarray dimensional space grouping genes taking into account all experimental conditions.7 However, the activity of genes could only appear under a particular set of experimental conditions, exhibiting local patterns. Discovering these local patterns can be key to discover gene pathways, which could be hard to discover in other ways. For this reason, the paradigm of clustering techniques must be modified to methods that allow local pattern discovery in gene expression data.8 Biclustering9 addresses this problem by relaxing the conditions and by allowing assessment only under a subset of the conditions of the experiment, and it has proved to be successful in finding gene patterns.10,11 If a third dimension is added to the dataset besides genes and conditions, such as time, clustering and biclustering result insufficient. There is a lot of interest in temporal experiments because they allow an in-depth analysis of molecular processes in which the time evolution is important, for example, cell cycles, development at the molecular level, or evolution of diseases.12 In this sense, triclustering appears as a technique going one step further by grouping genes under particular conditions and under particular time points,13 thus being capable of managing three-dimensional (3D) data. Therefore, triclustering is suitable for the analysis of microarray experiments where several samples are taken at different time points.14 This is of great interest since it allows for a deep analysis of biological processes where temporary development is important. Both biclustering and triclustering attack NP-hard problems.15 Therefore, algorithms based on heuristics are well suited to manage this kind of problem. In this sense, defining an appropriate quality measure for triclusters is an important and essential challenge.16 In this work, we propose a quality measure called Multi Slope Measure (MSL), which measures the quality of a tricluster based on the similarity among the angles of the slopes formed by each profile formed by the genes, conditions, and times of the tricluster. MSL: A Measure to Evaluate Three-dimensional Patterns in Gene Expression Data David Gutiérrez-avilés and cristina rubio-Escudero Department of Computer Science, University of Seville, Seville, Spain. Abstr Act: Microarray technology is highly used in biological research environments due to its ability to monitor the RNA concentration levels. The analysis of the data generated represents a computational challenge due to the characteristics of these data. Clustering techniques are widely applied to create groups of genes that exhibit a similar behavior. Biclustering relaxes the constraints for grouping, allowing genes to be evaluated only under a subset of the conditions. Triclustering appears for the analysis of longitudinal experiments in which the genes are evaluated under certain conditions at several time points. These triclusters provide hidden information in the form of behavior patterns from temporal experiments with microarrays relating subsets of genes, experimental conditions, and time points. We present an evaluation measure for triclusters called Multi Slope Measure, based on the similarity among the angles of the slopes formed by each profile formed by the genes, conditions, and times of the tricluster. Keywords: triclustering, angular comparison, genetic algorithms, fitness function, microarrays, time series CiTATion: Gutiérrez-avilés and rubio-Escudero. msl: a measure to Evaluate threedimensional Patterns in Gene Expression Data. Evolutionary Bioinformatics 2015:11 121–135 doi: 10.4137/EBo.s25822. RECEivED: march 11, 2015. RESubMiTTED: may 13, 2015. ACCEPTED foR PubLiCATion: may 21, 2015. ACADEMiC EDiToR: Jike cui, associate Editor TYPE: original research funDinG: The authors want to acknowledge the financial support given by the Spanish ministry of science and technology with project tin2011-28956-c02-02 and Junta de Andalucía with project TIC-7528. The authors confirm that the funder had no influence over the study design, content of the article, or selection of this journal. CoMPETinG inTERESTS: Authors disclose no potential conflicts of interest. CoRRESPonDEnCE: [email protected]s, [email protected] CoPYRiGhT: © the authors, publisher and licensee libertas academica limited. this is an open-access article distributed under the terms of the creative commons cc-By-nc 3.0 license. Paper subject to independent expert blind peer review by minimum of two reviewers. all editorial decisions made by independent academic editor. upon submission manuscript was subject to anti-plagiarism scanning. Prior to publication all authors have given signed confirmation of agreement to article publication and compliance with all applicable ethical and legal requirements, including the accuracy of author and contributor information, disclosure of competing interests and funding sources, compliance with ethical requirements relating to human and animal study participants, and compliance with any copyright requirements of third parties. this journal is a member of the committee on Publication Ethics (coPE). Published by libertas academica. learn more about this journal. Gutiérrez-Avilés and Rubio-Escudero 122 Evolutionary Bioinformatics 2015:11 We show the results obtained applying the MSL measure embedded in the TriGen Algorithm,17 an algorithm based on an evolutionary heuristic, genetic algorithms. The datasets used are a synthetic dataset and three real experiment datasets: the yeast cell cycle–regulated genes,18 mouse degeneration of retinal cells,14 and human transcription factor oncogene OTX2 silencing effect on D425 medulloblastoma cell line.19 The results have been validated by three different methods. First, by analyzing the correlation among the genes, conditions, and times in each tricluster using two different correlation measures (Pearson20 and Spearman21). Second, by a graphic validation of the patterns extracted based on the graphic representation (see Graphic Representation subsection), and third we have provided functional annotations for the genes extracted from the Gene Ontology (GO) project.22 The results obtained have been compared to two previously defined quality measures, MSR3D23 and LSL,24 showing improvement in the performance of the measure (see Results and Discussion section). The rest of the article is structured as follows. A review of the latest related works can be found in State of the Art section. Methods section describes the MSL measure as well as a brief description of Triclustering, the graphic representation applied, and the TriGen algorithm. In the Results and Discussion section, we show the results and discussion of applying TriGen to the synthetic and real datasets. The last section shows the conclusions. state of the Art This section is to provide a general overview of recent works in the field of gene expression temporal data. In particular, for those works related to the application of triclustering, we focus on the measures applied to evaluate the triclusters. We first present the authors’ previous contributions to this field. In our study,23 we described MSR3D, an adaptation of the Mean Square Residue (MSR)9 to the 3D space, so that a third factor, time in this case, can be taken into account. MSR3D measures the homogeneity of a tricluster in the relation of each value of the tricluster, with the average of all genes, average of all conditions, average of all times, average of all genes and conditions, average of all genes and times, average of all conditions and times, and average of all genes, conditions, and times in the tricluster. We also have presented LSL in our recent study,24 which measures the quality of a tricluster based on the similarity among the slopes of the angles formed by the least square lines from each of the profiles formed by the genes, conditions, and times of the tricluster. LSL has obtained better results than MSR3D applied to the same datasets along with the TriGen algorithm.24 Regarding other authors’ contributions, in 2005, Zhao and Zaki25 introduced the triCluster algorithm to extract patterns in 3D gene expression data. They presented a measure to assess triclusters’s quality based on the symmetry property. This allows for very efficient cluster mining since clusters are searched over the dimensions with the least cardinality. g-triCluster, an extended and generalized version of Zhao and Zaki’s proposal, was published one year later.26 The authors claimed that the symmetry property is not suitable for all patterns present in biological data and proposed the Spearman rank correlation21 as a more appropriate tricluster evaluation measure. An evolutionary computation proposal was made by Liu et al.27 The fitness function defined is a multiobjective measure that tries to optimize three conflicting objectives: clusters size, homogeneity, and gene-dimension variance of the 3D cluster. LagMiner was introduced by Xu et al.28 to find timelagged 3D clusters, what allows in turn to find regulatory relationships among genes. It is based on a novel 3D cluster model called S2 D3 Cluster. They evaluated their triclusters on homogeneity, regulation, minimum gene number, sample subspace size, and time periods length. Wang et al.29 proposed a new algorithm called ts-cluster basing their definition for coherent triclusters also on finding regulatory relationships among genes. For that purpose, time shifting is also considered among time points in the evaluated triclusters. A new strategy to mine 3D clusters in real-valued data was introduced by Sim et al.30 The authors defined the Correlated 3D Subspace Clusters (CSCs), where the values in each cluster must have high co-occurrences and those co-occurrences are not by chance. They measure the clusters based on the correlation information measure, which takes into account both prerequisites. Hu and Bhatnagar presented an approach focusing on the concept of Low-Variance 3-Cluster,31 which obeys the constraint of a low-variance distribution of cell values. The work by Liu et al.32 was focused on finding Temporal Dependency Association Rules, which relate patterns of behavior among genes. The rules obtained are to represent regulated relations among genes. Finally, a brief survey on triclustering applied to gene expression time series was published in 2011.13 There are three main features that a triclustering algorithm can perform. According to Mahanta et al.13, these features are temporal coherence that makes reference to the ability of the algorithm to capture the coherence of different genes in a single time point across samples while generating the final triclusters and the ability to find triclusters with nonconsecutive time points and tricluster with a specific type of pattern (shifting, scaling, delayed). g-triCluster,26 Moga3c,27 LagMiner,28 ts-cluster,29 and Temporal Dependency Association Rules32 perform the temporal coherence feature and only Tricluster25 and Moga3c27 perform finding triclusters containing nonconsecutive time points. Tricluster25 finds scaling patterns, LagMiner28 finds shifting and scaling patterns and ts-cluster29 MSL: 3D patterns from gene expression. 123Evolutionary Bioinformatics 2015:11 focuses on time-delayed patterns; the rest do not focus on finding a specific type of pattern. Another feature examined is the algorithm type distinguishing between deterministic (Tricluster25, g-triCluster26) and nondeterministic (Moga3c27) approaches. Methods In this section, we describe our proposal, the tricluster quality measure called MSL that is based on tricluster’s angular features. We will analyze all MSL principles and fundamentals and how it has been developed. This section is structured as follows: Triclustering subsection describes the triclustering procedure as an evolution of its well-known predecessor biclustering. In the subsection Graphic Representation, we introduce the graphic representation, which is key for understanding the MSL measure. Then, in the subsection MSL Measure, we analyze the core of our work, the MSL measure. Finally, in the TriGen Algorith subsection, we briefly describe the TriGen algorithm. triclustering. Clustering techniques are applied to analyze gene expression data from microarray experiments. The dataset obtained from the experiment, D, contains genes and experimental conditions and clustering aims at finding subgroups of genes that share a behavior pattern according to their expression level. Biclustering appears as an evolution of clustering due to its ability to mine subgroups of genes and conditions from the data set D, where the genes exhibit highly correlated patterns of behavior under certain experimental conditions.9 Triclustering emerges as an evolution of biclustering, taking into account the temporary evolution of genes under particular experimental conditions. In this way, from a dataset D obtained from a microarray experiment, which contains genes GD, conditions CD, and time points TD, we define triclustering as a technique that finds triclusters TRI1,…,TRIn from D, where a tricluster TRI is formally defined as TRI = G × C × T, where G ⊆ GD, C ⊆ CD, and T ⊆ TD,17 ie, a subset of genes that contains information related to the behavior of some genes from dataset G under conditions C at times T. Figure 1 shows a tricluster with genes as rows, conditions as columns, and time as depth. Graphic representation. In order to explain the MSL measure, we define the graphic representation of a tricluster TRIxop, with x, o, and p being either genes G, experimental conditions C, or time points T, so that the x elements in TRIxop will be on X axis and o elements in TRIxop will be the outlines represented in as many panels as p elements in TRIxop indicates, as can be seen in Figure 2. To visually analyze the behavior patterns of a tricluster TRI, we always consider three graphical views: • TRIgct (x = G, o = C, p = T): one panel for each time, genes on the X axis, the expression levels on the Y axis, and the lines of conditions as the outline. • TRIgtc (x = G, o = T, p = C): one panel for each condition, genes on the X axis, the expression levels on the Y axis, and the time lines as the outline. • TRItgc (x = T, o = G, p = C): one panel for each condition, times on the X axis, the expression levels on the Y axis, and the genes as the outline. With TRIgct and TRIgtc, we can analyze how each gene expression level varies throughout conditions and times, respectively. TRItgc represents how each gene varies throughout time for each condition. MsL measure. After analyzing the graphic representation of a tricluster, we describe our proposal: the Multi Slope Measure (MSL). MSL measures the differences among the angles formed by every series traced on each of three graphic representations taking into account TRIgct, TRIgtc, and TRItgc (subsection Graphic Representation). MSL takes into account the influence of neighboring time points. We can observe an example of TRItgc view of TRI = G {g1, g4, g7, g10}, C {c2, c5, c8}, T {t0, t2, t11} in Figure 3. We can see how each outline or gene forms a set of angles (two for this particular example) defined by each time point in the X axis for every panel or experimental condition. To calculate the MSL measure of a tricluster, we first pe r f o rm th e m ul tian g ular co m p a ris o n t erm ca l cula ti o n . Th e multiangular comparison operation of a graphic representation xop from a tricluster TRI is defined in Equation 1a. We define ACmulti of a tricluster’s graphic representation TRIxop as the average of the differences ∆ of angles vectors avopε ang set (Equation 1b) of all outlines o for each panel p (Vmc in Equation 1c) and its equivalent for the rest of the panels (Hmc in Equation 1d), with Nmc being the number Conditions Times Genes figure 1. tricluster representation. Gutiérrez-Avilés and Rubio-Escudero 124 Evolutionary Bioinformatics 2015:11 of differences made (Equation 1e). An angle vector of an outline o in a panel p is defined as a set of angles that are formed by the outline o taking into account every data point in the X axis (Equation 1f), each outline will have Number of X axis ticks – 1 angles as you can see in Figure 3. The difference ∆ between two angles vector avA and avB is defined as the average of the MAX – MIN (MAX being the maximum and MIN the minimum of two angles avA(i) and avB(i)) of each component (or angle) i of avA and avB (Equation 1g). AC TRIVH N multixop mc mc mc () =+ (1a) angset av av av av av av op op op op op op UT AN = {} 11 21 31 12 12 ,,,,,,,…… ( 1 b ) Vavav mc op next op angset =∆ () () ∑, (1c) Havav mc op onextp angset =∆ () () ∑, (1d) N op op mc =+− () |||| || ||2 2 ** (1e) av aa op ix xx iAX =∀ − ε ,,… 1 (1f) ∆ () = ∑ () () () − () () () av av MAXaviav iMIN av iavi AB iavavABAB AB , ,, , ε |||avAB, (1g) The ACmulti term is based on several operations with avop angle vectors. These elements have been obtained based on concept of series (Equation 2a) so that a series Sop of a outline o for a panel p is a set of pair of values from the x axis (xi) and expression levels (elj) that form the outline. For each series Sop, the alpha angle α xi is calculated as the spin of the arctangent of the slope of the line formed by (xi, eli) and (xnext(i), elnext(i)) points (Equation 2b). The spin operation of an angle showed in Equation 2c is the positive equivalent of this angle if it is negative. Sxel xel op AX L =< >< > {} 00 ,,,,… (2a) α x next ii next ii ispin xx el el =− −                   () () arctan (2b) elL el0 el1el0 el1 el0 el1 elj elL elj elL elj elL elj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . el0 el1 . . . . . . . . . . . . . . ... ... . oUT o0 o1 or oUT o0 o1 or oUT o0 o1 or oUT o0 o1 or x0x1x1xAX ...... x0x1x1xAX ... ... x0x1x1xAX ...... x0x1x1xAX p0p1pspAN figure 2. Graphic representation of a tricluster. c2 g4 g1 g7 g10 g4 g1 g7 g10 g4 g1 g7 g10 αg αc2 g7 αc2 g4 c5c8 t0t2t11 t0t2t11 t0t2t11 βgαg αc5 g7 αc5 g4 αc5 g1 βgαc8 g10 βc8 g10 βc5 g7αc8 g7 βc8 g7 βc5 g4 αc8 g4βc8 g4 βc5 g1αc8 g1βc8 g1 βc2 g7 βc2 g4 c2 10 c2 10 c5 10 c5 10 figure 3. angles for TRItgc graphic view. MSL: 3D patterns from gene expression. 125Evolutionary Bioinformatics 2015:11 spin if xx xx ii ii () * αα αα =<⇒=+02π (2c) To conclude, the MSL measure of a tricluster TRI (Equation 3) is the average of the angular comparison of the three graphic representations of the tricluster. Following Figure 3, we show an example of ACmulti(TRItgc ) calculation in Figure 4. First, we arrange the example tricluster TRI so that for each condition (panel) we obtain a table with one row per gene (outline) and one column per time point (X axis). Second, in order to get each avgc (Equation 1f) of angset (Equation 1b), we use Equation 2b from Sgc series and obtain all angles α xi of avgc vectors, and third, we use Equations 1c and 1d for Vmc and Hmc calculations, respectively, going through the av set in horizontal and vertical direction. Finally, we use Equation 1a to obtain the ACmulti(TRItgc) value. We will have to repeat this process twice more, once for each graphic representation TRIgct and TRIgtc, to obtain the MSL measure according to Equation 3. MSLTRI AC TRIACTRI AC TRI multigct multigtc multit () = ()   + () + 1 3 ggc () (3) triGen algorithm. In this section, we present the TriGen (Triclustering-Genetic based) algorithm,17 where the MSL measure has been embedded in order to test its effectiveness. TriGen applies a bio-inspired paradigm of an evolutionary heuristic, genetic algorithms, in such a way that finds a set of triclusters from gene expression datasets where the time is also a component taken into account in the experiment. This method mimics the process of natural selection by creating an initial population of individuals representing solutions that p1 = c2 x1 = t0 1 s 10 515 30 42 100 40 45 85 30 50 20 10 15 35 45 80 20 20 10 10 40 45 70 35 55 80 30 50 70 50 70 30 40 70 80 2 s3 s 1 s2 s3 s 1 s2 s3 s o1 = g1 o2 = g4 o3 = g7 o4 = g10 Hmc = 17.01 ACmulti (TRItgc) = 1.97 Vmc = 42.37 avg avg avg avg o1 = g1 o2 = g4 o3 = g7 o4 = g10 o1 = g1 o2 = g4 o3 = g7 o4 = g10 x2 = t2x3 = t11 x1 = t0x2 = t2x3 = t11 x1 = t0x2 = t2x3 = t11 p2 = c5p3 = c8 = {1.37, 1.5} = {4.9, 5.03} = {1.47, 4.81} = {4.9, 1.47} = {0, 1.47} = {1.47, 4.9} = {4.81, 1.5} = {4.81, 1.37} = {1.47, 4.81} = {1.37, 4.81} = {1.37, 1.37} = {4.81, 0} avg c21 c81 avg c2 4 avgc5 4c8 4 c8 7 c810 avg c2 10 avg c2 7 = 1.78 ∆ (avg , avg ) c21 c2 7 = 3.38 ∆ (avg , avg ) c21 c2 4 = 1.83 ∆ (avg , avg ) c24 c2 7 = 3.53 ∆ (avg , avg ) c27 c2 10 = 1.7 ∆ (avg , avg ) c24 c2 10 = 1.78 ∆ (avg , avg ) c21 c2 10 = 0.06 ∆ (avg , avg ) c51 c5 4 = 3.43 ∆ (avg , avg ) c51 c5 7 = 3.37 ∆ (avg , avg ) c54 c5 7 = 2.45 ∆ (avg , avg ) c51 c5 10 = 2.42 ∆ (avg , avg ) c54 c5 10 = 2.45 ∆ (avg , avg ) c57 c5 10 = 2.4 ∆ (avg , avg ) c81 c8 4 = 0.09 ∆ (avg , avg ) c21 c2 1= 3.32 ∆ (avg , avg ) c24 c5 4 = 1.76 ∆ (avg , avg ) c24 c8 4 = 1.78 ∆ (avg , avg ) c54 c8 4 = 2.4 ∆ (avg , avg ) c510 c8 10 = 1.7 ∆ (avg , avg ) c210 c8 10 = 0.7 ∆ (avg , avg ) c210 c5 10 = 0.78 ∆ (avg , avg ) c21 c8 1 = 0.68 ∆ (avg , avg ) c51 c8 1 = 1.87 ∆ (avg , avg ) c27 c8 7 = 0.09 ∆ (avg , avg ) c57 c8 7 = 1.78 ∆ (avg , avg ) c27 c8 7 = 4.12 ∆ (avg , avg ) c81 c8 7 = 1.71 ∆ (avg , avg ) c84 c8 7 = 1.76 ∆ (avg , avg ) c84 c8 10 = 4.07 ∆ (avg , avg ) c81 c8 10 = 0.04 ∆ (avg , avg ) c87 c8 10 avg c51 avg c5 7 avg c5 10 figure 4. ACmulti(TRItgc) example. Gutiérrez-Avilés and Rubio-Escudero 126 Evolutionary Bioinformatics 2015:11 1. Input: The TriGen algorithm has two input arguments: • D: A dataset containing the gene expression values from a microarray experiment containing genes DG, experimental conditions DC, and times DT . Therefore, each cell [i, j, k] from D where i ∈ DG, j ∈ DC, and k ∈ DT , represents the expression level of the gene i under the experimental condition j at time k. • P: Set of parameters to execute the algorithm as described in Table 1. These parameters control the number of solutions or triclusters to find (N), the number of generations to execute (G), the number of individuals in the population (I), and the randomness factor they are generated with the initial population (Ale) as well as weights for the selection and mutation operators (Sel and Mut), weights to control the effect of the MSL measure (wf), the size of the triclusters (wg, wc, wt), and weights to control the overlap among solutions (wog, woc, wot). The parameters have been chosen after an exhaustive experimentation with all possible ranks of values. Each of the parameters has effect on the triclusters found: size, overlapping, exploration versus exploitation of the algorithm, etc. We now describe the effects of each of the parameters. In the execution of TriGen, each parameter is associated to a genetic operator, that is, G controls the whole evolutionary process so an increase in the number of generations implies a greater number of recombination of individuals. Therefore, an excessive increase in G may favor exploitation versus exploration in excess and the algorithm may return solutions that fall into a local minimum. I and Ale control the initial population creation, and when the number of individuals I is increased, a larger search space for the solutions is created so that an excessive increase can create a scatter search effect, and therefore, not return good quality are crossed and mutated for a number of generations, with the best individuals in the population being finally selected. The MSL measure has been applied as the fitness function to assess the quality of the triclusters or solutions in the population. The flowchart of the TriGen algorithm can be seen in Figure 5. We now define the most important elements of the algorithm such as inputs, outputs, codification of individuals, and genetic operators. Table 1. TriGen algorithm parameters. PARAMETER DESCRiPTion Nnumber of triclusters extracted Gnumber of generations Inumber of individuals in the population Ale randomness rate Sel selection rate Mut mutation probability wfWeight for MSL measure wgWeight for the number of genes wcWeight for the number of conditions wtWeight for the number of times wogWeight for the overlap among genes wocWeight for the overlap among conditions wotWeight for the overlap among times D, P Initial population Evaluation Selection Crossover Mutation Processed generations < G Update SOL Solutions found < N Get best TRI SOL figure 5. TriGen algorithm flowchart. MSL: 3D patterns from gene expression. 127Evolutionary Bioinformatics 2015:11 solutions; an increase of the randomness rate Ale in the initial population has to be combined with the overlap control to make sure that a wide area of the space of solutions is initially covered. Sel controls the selection mechanism, and as a result, the crossover and a high Sel creates individuals with a low level of genetic recombination, favoring exploitation versus exploration, and if the parameter is increased in excess, the algorithm may fall into a local minimum. On the contrary, a high probability of mutation Mut favors exploration versus exploitation, and if increased in excess, we will end up with solutions in many areas of the search space but with low quality levels. w and wo combined with wf control the fitness function; w weights control the number of items in the solutions, an increase of these weights involves favoring solutions with more volume; the increase of wo weights leads to little or nonoverlapped solutions, an excessive increase can lead to the loss of interesting solutions. The content under Genetic Operators in the subsection TriGen Algorithm explains all operators and how a parameter variation affects the execution of TriGen. 2. Output: The TriGen algorithm’s output will be a set of N triclusters, formally SOL = {TRI1, TRI2,…, TRIN}. Each TRIi ε SOL is composed of a subset of genes TRIG, conditions TRIC, and times TRIT from the input dataset D and has the best score in its population when evaluated under the MSL measure. 3. Codification of individuals: Each individual in the evolutionary process of the TriGen algorithm represents a tricluster, which is a potential solution. Therefore, an individual is represented as a subset of genes Gggg ii iF =< > 1,,,, 2 … a subset of conditions Cccc ii iQ =< > 12 ,,,… , and a subset of time points Tttt ii iw =< > 12 ,,,.… The genes, conditions, and times subsets are extracted from the input dataset D. The algorithm selects time points as part of the tricluster but always keeping their order. All genetic operators are applied to each individual in the population, in each of these three subsets. 4. Overlapping control: We have designed an overlapping control mechanism to avoid overlapping among the tricluster solutions obtained. It is called Data Hierarchy and consists in maintaining the number of occurrences of genes, conditions, and time points of dataset D in each tricluster solution from less to most visited in such a way that, as we will explain in Initial Population in the subsection TriGen Algorithm, the initial population creation uses this structure to initialize population with the minimum overlapping. This Data Hierarchy is updated at every generation a new tricluster solution is selected. 5. Genetic operators: a. Initial population: With the initial population method, I individuals are generated attending to the Ale randomness parameter. An Ale percent of individuals are created at random by two methods: half of the individuals are purely randomly generated, this is, a random subset of genes TRIG, conditions TRIC, and times TRIT are chosen from D and the other half is also randomly created but controlling that the values for the genes TRIG are contiguous, the values for the conditions TRIC are contiguous and the times TRIT are contiguous as well. The rest of the individuals are randomly created, but taking into account the previously created individuals to control overlapping of solutions according to Data Hierarchy structure (Overlapping Control in the subsection TriGen Algorithm). b. Fitness function: Our proposed measure has been included as the genetic algorithm’s fitness function FF(TRI) along with the size and the overlapping control. As can be seen in Equation 4, MSL has been combined with six other factors as a weighted average. Three of these factors 1|| || 1|| || −− TRI D TRI D G G C C , , and 1|| || −TRI D T T measure the number of genes, conditions, and times of TRI (|TRIG, C, T|) relative to the dataset’s size (|DG, C, T|). MSL is a minimizing fitness function, and we have to set 1 minus each amount proportion in order to favor TRI with greater sizes when wg, wc, or wt are increased. The other three members RTRI SOL TRISOL RTRI SOL TRISOL G G C C , *,, * () () |||||||| , and RTRI SOL TRISOL T T , * () |||| measure the repeated genes, conditions, or times elements of TRI in the set of already found solutions SOL (RG, C, T(TRI, SOL)) proportionally calculated supposing all of genes, conditions, or times are repeated in SOL (|TRIG, C, T|*|SOL|) in order to favor TRI with less overlapping when wog, woc, or wot are increased. Finally, the main member MSLTRI () 2π measures MSL (TRI) proportionally calculated to its maximum value 2π in order to favor TRI with smaller MSL when wf is increased. A default configuration for wf, wg, wc, wt, wog, woc, and wot consists in fixing wf to 0.8 and distributing 0.2 among wg, wc, wt, wog, woc, and wot. FF TRIwwwwwo wo w wMSLTRI wTRI fgct gct fg G () =++++ ++ () +− 1 21|| * {* * π||| 1|| || 1|| || D wTRI DwTRI D wo G c C C g T T     + −     +−     +** gg G G g C C t RTRI SOL TRISOL wo RTRI SOL TRISOL wo *, **, * () + () + |||| |||| ** , *} RTRI SOL TRISOL T T () |||| (4) Gutiérrez-Avilés and Rubio-Escudero 128 Evolutionary Bioinformatics 2015:11 c. Selection: Three groups of individuals are randomly selected sorted from lowest to highest according to the fitness function, and then a random selection from the three groups is made. The Sel parameter indicates how many of these individuals will pass to the next generation. The rest of the individuals until completing the next population (I – #Selected individuals) will be created based on the crossover operator. d. Crossover: To complete the next generation, we create new individuals with this operator as follows: two individuals (parents, A and B) are combined to create two new individuals (offsprings, child1 and child2). The parents are randomly chosen. Their genetic materials are combined by a random one-point cross in the genes TRIG, conditions TRIC, and time TRIT and mixing the coordinates in both children.17 e. Mutation: An individual can be mutated according to a probability of mutation, Mut. The mutation probability is verified for every individual, and if it is satisfactory, one out of nine possible actions is taken. These actions are add a new random gene to TRIG, add a new condition to TRIC, or add a new time point to TRIT , by removing a random gene, condition, or time, or by changing a random gene or condition for another that is randomly chosen. The election of these actions is also random. For the case of addition of a new gene, condition, or time, the operator checks whether the new member is already in the individual or not. results and discussion In this section, we show the results obtained by application of MSL as a fitness function embedded in the TriGen algorithm17 (see the subsection TriGen Algorithm). MSL has been applied to four different datasets: one synthetically generated dataset and three real datasets. The real datasets are obtained from experiments with the yeast cell cycle (Saccharomyces cerevisiae),18 an experiment with mice (Mus musculus) called GDS451014 and data from experiments with humans (Homo sapiens) called GDS4472.19 The last two data sets have been retrieved from Gene Expression Omnibus,33 a database repository of high-throughput gene expression data. All biological experiments examine the behavior of genes under conditions at certain times. For the analysis of the triclusters obtained as the result of the experiments, we have developed a three-step process based on providing information related to correlation among expression values, the graphic properties of the representation of the values, and biological validation. The correlation validation is based on the Pearson and Filon20 and Spearman21 coefficients. For every tricluster, we calculate the average of the correlation coefficients between each combination of gene, condition, and time for all genes. For instance, for a tricluster with four genes {1, 4, 8, 10}, two conditions {3 and 7}, and three times {1, 3 and 5}, we provide the Pearsons and Spearmans correlation coefficient average for values at the eight possible combinations, each having three time points: Vg=1, c=3, Vg=1, c=7, Vg=4, c=3, Vg=4, c=7, Vg=8, c=3, Vg=8, c=7, Vg=10, c=3, and Vg=10, c=7. The graphic properties of the representation are shown as described in the subsection Graphic Representation as a way to visually check how the gene patterns behave. Finally, for the biological validation, we will show the GO terms22 related to the triclusters. We present a GO analysis table in which we include the most representative terms extracted by the Ontologizer software,34 each term associated to a P-value that denotes the relevance level of the term. In this type of studies, P-values are considered as relevant below 0.05 and are better when closer to 0. Regarding the GO project, it is a major bioinformatics initiative with the aim of standardizing the representation of gene and gene product attributes across species and databases. The project provides an ontology of terms for describing gene product characteristics and gene product annotation data. The ontology covers three domains: cellular component, the parts of a cell or its extracellular environment; molecular function, the elemental activities of a gene product at the molecular level, such as binding or catalysis; and biological process, operations, or sets of molecular events with a defined beginning and end, pertinent to the functioning of integrated living units: cells, tissues, organs, and organisms. We have compared the results obtained to those from Gutiérrez-Avilés and Rubio-Escudero,23 where the fitness function was the MSR3D measure and also to the results in Gutiérrez-Avilés and Rubio-Escudero,24 where the fitness function was the LSL measure. The comparison has been made in terms of correlation and GO analysis. For each real experiment, we have compared the maximum, minimum, and mean Pearson’s and Spearman’s correlation index and the maximum, minimum, and mean P-value for each solution considered. All experiments were executed on a multiprocessor machine with 64 processors, Intel Xeon E7-4820 2.00 GHz with 8-GB RAM memory. We have used Java to implement TriGen algorithm (and other ad hoc developments) and an R framework to create graphics and get dataset resources from GEO.33 We now analyze the results obtained in each of the four experiments. synthetic experiments. Synthetic data are widely used not only for testing the performance of microarray analyzing techniques14 but also in more general data mining publications.35 It has the advantage that the process that generated the data is well known and so one is able to judge the success or failure of the algorithm.36 In this work, we have used an application designed by ourselves to generate the synthetic data used in this experiment. We have executed the TriGen algorithm with the MSL MSL: 3D patterns from gene expression. 129Evolutionary Bioinformatics 2015:11 measure over a synthetic dataset composed of 4,000 genes, 30 experimental conditions, and 20 time points whose expression levels were randomly generated by a cryptographic secure standard library Math3 provided by Apache Commons.37 In this dataset, we inserted 10 triclusters composed of 150 genes, 6 experimental conditions, and 4 time points, whose expression levels form a constant behavior pattern. These triclusters are located in random positions in the dataset. To see the behavior of the MSL measure applied along with TriGen and also with the aim of analyzing the effect of the value of the parameters in the solutions, we have made executions setting N to 200 and varying other control para meters as follows: G ε {100, 200}, I ε {50, 100}, Sel ε {0.5}, Mut ε {0.2, 0.3}, Ale ε {0.3, 0.5}, wg ε {0.03, 0.05, 0}, wc ε {0, 0.01}, wt ε {0,0.01}, wog ε {0.04, 0.05}, woc ε {0,0.03}, and wot ε {0,0.03} (see Input in the TriGen Algorithm subsection for a detailed description of these parameters). The algorithm has been capable of finding between 94% and 100% of the inserted triclusters. There were no false positives or false negatives found. The application of the MSR3D along with the TriGen algorithm in the study by Gutiérrez-Avilés and Rubio-Escudero23 was capable of finding 91% to 95% and LSL24 obtained a matching ratio between 93% and 97% of the triclusters, so we can see in slight improvement when applying the MSL measure. yeast elutriation experiments. For this experiment, we have applied the TriGen algorithm with MSL measure to the yeast (Saccharomyces cerevisiae) cell cycle problem,18 specifically the Elutriation experiment. The yeast cell cycle analysis project’s goal is to identify all genes whose mRNA levels are regulated by the cell cycle. The resources used are public and available in http://genome-www.stanford.edu/cellcycle/. Data have been normalized as part of the preprocessing. We have created a dataset Delu3D from the elutriation experiment with 7,744 genes, 13 experimental conditions, and 14 time points. Experimental conditions correspond to different statistical measures of the Cy3 and Cy5 channels while time points represent different moments of taking measures from 0 to 390 minutes. The parameter configuration used for this experiment is shown in Table 2. We set G and I values in order to obtain a default exploration of the solution space and Ale, Sel, and Mut provide us with a high random factor in population generation, low elitism in the next generation promotion, and high mutation factor, respectively. We favor solutions with a high number of genes setting wg to 0.05 and solutions with high variability in genes, conditions, and times thanks to wog, woc, and wot set to 0.05. These configurations have been obtained as a result of a deep experimental study on the Delu3D dataset. Regarding the correlation analysis, we can observe in Table 3 show Pearson and Spearman’s values vary between [0.95, 0.97] and [0.98, 1], respectively, which implies a high correlation between genes series for every experimental condition through time points. These high values confirm us that the quality of the triclusters obtained from these experiments is very high in terms of correlation. We can see the graphic representation of tricluster TRI11 in Figure 6. Only one out of the 20 triclusters obtained has been represented for legibility reasons. We can observe how TRI11 Table 2. TriGen algorithm control parameters for yeast cell cycle dataset. PARAMETER vALuES n20 G150 i200 ale 0.9 sel 0.4 mut 0.9 wf0.8 wg0.05 wc0 wt0 wog0.05 woc0.05 wot0.05 Table 3. correlation results for triclusters from the yeast cell cycle dataset. TRIsol PEARSon SPEARMAn TRI10.97 0.98 TRI20.97 0.99 TRI30.96 0.99 TRI40.96 0.98 TRI50.97 0.99 TRI60.96 0.99 TRI70.96 0.99 TRI80.96 0.98 TRI90.96 0.98 TRI10 0.96 0.99 TRI11 0.96 0.99 TRI12 0.95 0.98 TRI13 0.96 0.98 TRI14 0.96 0.98 TRI15 0.97 1 TRI16 0.96 0.98 TRI17 0.96 0.98 TRI18 0.96 0.99 TRI19 0.96 0.99 TRI20 0.96 0.98