INTRODUCTION:
Clustering is one of the machine learning algorithm that are applied in various fields[4,5,6]. The traditional clustering methods like k-means clustering algorithm which fails for clustering genes which are coexpressed over subset of samples[7,8]. This problem can be solved through biclustering which clusters subset of genes that are similar under subset of samples[9]. New algorithms need to be developed for addressing mining problems such as clustering, classification. Disadvantage of this approach is each dimension is reconstructed independently. So, there is loss of implicit data in multidimensional records[10]. Triclustering deals with three dimensional datasets which finds coexpressed genes under subset of experimental conditions across subset of time points or space.
A very first triclustering algorithm proposed for mining coherent clusters from three dimensional data is called “triCluster”[11]. It is the extension of the biclustering algorithm which uses heuristic approach to retrieve biclusters with mean square residue as the objective function. A time-frequency based full-space algorithm is proposed which uses a measure of functional correlation set between time course vectors of different genes[12]. Next, the tricluster algorithm is proposed that aims to retrieve groups of genes that have similar expression profiles over a subset of samples during a subset of time points. It also provides set of metrics to assess the quality of the triclusters and tested the approach on real life microarray datasets[13].
Later, “gTricluster” algorithm is introduced which extends clique search technique for three dimension data and retrieves triclusters using spearman rank correlation similarity measure[14]. The δ-TRIMAX algorithm is the extension of triCluster algorithm which extracts triclusters with mean square residue score below a threshold value δ[15]. TriGen algorithm implementing the optimization technique of genetic algorithm for extracting triclusters from temporal datasets[16]. The multi-objective optimization algorithm EMOA-δ-TRIMAX is proposed which extends δ-TRIMAX algorithm with the genetic algorithm optimization technique[17]. Common Optimization techniques like genetic algorithms are also applied in medical data mining for producing effective results[18].
Particle Swarm Optimization (PSO) is a heuristic search technique which is inspired by the swarming behaviour of biological population such as schools of fish or flock of birds[19]. Each bird or fish is represented as a single solution in the search space and it is called as particle. The PSO and its several variants have been popular because of its ease of implementation, intuitiveness and the ability to solve non linear problems. It is widely used in many branches of engineering including artificial neural networks, wireless sensor networks and many others.
MATERIALS AND METHODS:
Particle Swarm Optimization:
Particle Swarm Optimization (PSO) was introduced by Kennedy and Eberhart which is inspired from the controlled motion of swarm of birds analyzing the notion of “collective intelligence”, also known as “swarm intelligence” in biological populations[20]. The most commonly used example is the behaviour of fish school. These animals are characterized by its movement where each individual have only a limited intelligence of focussing only on its position in the swarm. It has some simple rules such as “going with the same speed of neighbours”, “moving in same direction” or “staying close to neighbours”. The global intelligence of swarm is a direct consequence of local interactions between different particles.
Initially, a random set of solutions called as initial swarm, propagates in the design space over a number of iterations. Particles adjust their flying directions based on its own flying experience and also its neighbour flying experience. It is inspired by the visualization of flocks of birds, adapting the environment and finding the food sources by implementing information sharing approach. Many revised variants of PSO have emerged with various concepts but the basic technique is population based optimizer, a number of parameters such as inertia weight and confidence factors give the simple version of PSO[21, 22].
PSO algorithm:
The steps of PSO algorithm is given as follows
Initialize a population is represented as
,
where Xi is a particle that moves within the multidimensional search space. A
particles position and velocity are its properties. The particle position represents
the candidate solution. The particle velocity is the information about
direction and varying rate. A particle in d-dimensional search space is given
as 
,
the velocity for a particle i is given as 
and
the best previously visited position of a particle is given as 
.
For each particle, evaluate the optimization fitness function in N variables and compare the particles fitness with its pbest. If the current value is better than the pbest, then set pbest to current location X in N-dimensional space.
Update each particles velocity according to the equation(1).
(1)
Where is the particle velocity of dth
component after (k+1)th update. 
is
currently the best particles solution after (k+1)th update. 
is
the global best solution of the dth component after (k+1)th update. 
and
are
the positive constants known as acceleration coefficients which controls the
movement of the particles. 
is
the inertia weight which controls the effect of previous particles velocity on
next one. 
and
are
random variables within the range [0,1].
Update each particles position according to the equation (2).
(2)
Where is the particles position after (k+1)th
update and 
is
the particles velocity after (k+1)th update. The position and the velocity of
each particle are updated consecutively for much iteration until a termination
condition is reached[23].
Loop to step 2 until stopping criterion is met which may be a good fitness function or reaching a maximum number of iterations.
Triclustering:
Traditional clustering algorithms are applied to analyze the microarray data which work in the full dimensional space. For a microarray gene expression dataset say D, clustering technique considers the value of each object in all the dimensions and groups the similar expression patterns together. Biclustering technique emerged to overcome this strict constraint in clustering. Biclustering extracts co-expressed patterns of a subset of genes under a subset of the samples or experimental conditions. Triclustering emerges an an evolution of biclustering by mining gene expression patterns across samples and time points. The clustering of similar genes that exhibit similar behaviour only under a subset of conditions over only some set of time points is known as triclustering. Figure 1 shows the three dimensional matrix with genes in one dimension, samples in next dimension and time points as the third dimension.
Figure 1: Three Dimensional Data Matrix
Objective Function:
Tricluster is given as 
where 
,
and 
. The cuboid C represents subset of genes which have similar
expression values over a subset of samples during subset of time points. The
objective function is the Mean Square Residue (MSR) of the tricluster which is
modelled as in equations (3) and (4) [24].
(3)
(4)
Where 
is the mean of genes under samples at a time point, 
is the mean of the genes over time under a sample, 
is the mean of a gene in time under the samples, 
is the mean of the genes under a sample and a time point, 
is the mean of the values of a gene at a time point under samples,
is the mean of a gene under a sample at all time points and 
is the mean value of all values in the tricluster.
Where is the mean of genes under samples at a time point, is the mean of the genes over time under a sample, is the mean of a gene in time under the samples, is the mean of the genes under a sample and a time point, is the mean of the values of a gene at a time point under samples,
is the mean of a gene under a sample at all time points and is the mean value of all values in the tricluster.
RESULTS:
Dataset Description:
PSO algorithm is implemented on three real life temporal high dimensional datasets which are obtained from Gene Expression Omnibus (GEO). Three datasets are experiments of various diseases. All the experiments are time series experiments that have the behaviour of genes under different samples across different time points.
Dataset 1:
The real life time series dataset GDS5192 is a experiment of Homo Sapiens. It holds 22158 Affymetrix human genome U133A 2.0 probe ids. Cultures of primary fibroblasts from neonatal skin treated by Egr1 and Tgfb1 were measured at 24 and 48 hours. Two biological replicates per time point were measured.
Dataset 2
This time series dataset is obtained from GEO with the accession code GDS1489 which is experiment for Mus Musculus for growth hormone treatment. It holds 12488 genes in Affymetrix Murine Genome U74A Version 2 Array. It has expression profiling of adipocytes treated with growth hormone and control for 30 mins, 4th hour and 48th hour in three independent experiments.
Dataset 3:
The temporal dataset GSE74259 is a time course experiment of Saccharomyces cerevisiae which holds 10928 genes Affymetrix Yeast Genome 2.0 Array. The cultures of BY4741 yeast were grown in non-fermentable yeast peptone glycerol ethanol at 30 degree Celsius and treated for 0, 60, 120 and 240 mins that is for two replicates.
The PSO algorithm is implemented in MATLAB version 7.14 (R2012a). The number of particles, number of iterations and inertia weight is fixed throughout for all the three datasets [19]. Table 1 shows the parameters and values considered for the PSO algorithm. Table 2 shows the average fitness function over 10 runs for all three datasets. The lower MSR value indicates that the quality of the triclusters is good. Thus, the MSR value is low for all the three datasets indicating that the extracted triclusters are with highly coexpressed genes.
Table 1: Parameters and Values considered for CS and PSO
|
Parameter |
Value |
|
Number of particles (p) |
50 |
|
Number of iterations |
20 |
|
C1 and C2 |
2.1 |
|
Inertia Weight (ω) |
0.9 |
Table 2: The Average Objective Function over 10 Runs
|
Generation |
MSR |
||
|
Dataset 1 |
Dataset 2 |
Dataset 3 |
|
|
1 |
3.90E-02 |
1.55E-01 |
2.12E-01 |
|
5 |
3.85E-02 |
1.54E-01 |
2.06E-01 |
|
10 |
3.82E-02 |
1.53E-01 |
2.05E-01 |
|
15 |
3.80E-02 |
1.51E-01 |
2.04E-01 |
|
20 |
3.77E-02 |
1.47E-01 |
2.03E-01 |
|
25 |
3.74E-02 |
1.46E-01 |
2.02E-01 |
|
30 |
3.64E-02 |
1.41E-01 |
1.99E-01 |
|
35 |
3.57E-02 |
1.09E-01 |
1.97E-01 |
|
40 |
3.48E-02 |
1.06E-01 |
1.89E-01 |
|
45 |
2.81E-02 |
1.00E-01 |
1.80E-01 |
|
50 |
2.62E-02 |
1.00E-01 |
1.79E-01 |
Each dataset have I genes, J samples and K time points which is given as input to the proposed work and it produces clusters which has i genes, j samples and k time points for which and . Figure 2, 3 and 4 shows the sample triclusters obtained from the proposed PSO algorithm for the three datasets respectively.
Figure 2: Sample Tricluster for Dataset 1
Figure 3: Sample Tricluster for Dataset 2
Figure 4: Sample Tricluster for Dataset 3
DISCUSSION:
Performance Comparison:
The performance of the proposed work with different representations is compared with other triclustering algorithms based on two validation indexes. The first measure is the Triclustering Quality Index (TQI) which is given in equation (5) [25].
(5)
Where 
is the mean squared residue of the
tricluster 
and 
is the volume of the tricluster . The volume of the ith tricluster is
defined as 
where 
, 
and 
represent the number of genes, samples
and time points of the ith tricluster. A lower TQI represents the better
quality of the triclusters.
The second measure is the Statistical Difference from Background (SDB) score which signifies whether a set of n triclusters are statistically different from the background data matrix or not [25]. The SDB score is given in the equation (6).
Where n is the total number
of triclusters extracted by the algorithm. represents the mean squared residue of
the ith tricluster and 
is the mean square residue of the jth
random tricluster having the same number of genes, samples and time points as
the ith resultant tricluster. The higher the value of the denominator denotes
the better the quality of the resultant tricluster. Hence, lower SDB score
signifies better performance of the algorithm. Table 3
shows the comparison of the performance of various algorithms in terms of SDB
and TQI indexes.
Table 3: Performance Comparison
|
Algorithm |
SDB |
Average TQI |
|
Tricluster using PSO for Dataset 1 |
0.2572 |
4.21E-09 |
|
Tricluster using PSO for Dataset 2 |
0.3323 |
3.27E-09 |
|
Tricluster using PSO for Dataset 3 |
0.2095 |
2.01E-09 |
|
δ-TRIMAX |
0.4679 |
3.08E-05 |
|
TRICLUSTER |
0.4773 |
3.35E-05 |
Biological Significance
Dataset 1
The biological significance of the genes belonging to the clusters is identified by performing Gene ontology and KEGG pathway enrichment analysis. David ontology tool which is freely available in the internet is used for the gene enrichment analysis [26]. Gene ontology analysis is performed to find the biological significance of the gene belonging to the triclusters. The genes which have lower p-value are selected representing the higher significance level. The functional process of the genes in the tricluster is identified through the functional annotation. The genes from three sample triclusters are given as input for performing functional annotation. Table 4 shows the functional annotation results for Dataset 1. According to the p-value, the genes are ordered. The functional property “Alternative Splicing” has the lowest p-value 3.0E-244 with the gene count of 8819. In the Tricluster 3, there are 4262 genes with the property “Cytoplasm” having the lower p-value 1.7E-32. In Tricluster 5, “Sequence variant” is the main function having 9566 genes with low p-value 2.6E-30.