A New Hybrid Cuckoo Search Algorithm for Biclustering of Microarray Gene-Expression Data

Figures & data

Table 1. Review of related work in biclustering gene expression data.

S. No.	Algorithm	Merits	Demerits
1.	CC (Cheng and Church 2000)	The algorithm discovers biclusters with coherent values.	CC discovers one bicluster at a time, repeated application of the method on a modified matrix is needed for discovering multiple biclusters. Therefore, it results in highly overlapping gene sets.
2.	SAMBA (Tanay, Sharan, and Shamir 2009)	Significant biclusters were identified using graph theoretic approach simultaneously.	The algorithm is based on exhaustive enumeration of biclusters. Due to its high complexity, the number of rows the bicluster may have is restricted.
3.	xMOTIFs (Murali and Kasif 2003)	In order to prevent the algorithm from finding too small or too large bicluster, some constraints on their size, conservation, and maximality have been added to its formal definition.	The algorithm uses prior knowledge about the sample phenotypes.
4.	ISA (Bergmann, Ihmels, and Barkai 2003)	The method includes data normalization and the use of thresholds that determine the resolutions of the different transcription modules.	There is no evaluation of the statistical significance. Additionally, two threshold parameters should be defined.
5.	OPSM (Ben-Dor et al. 2003)	The algorithm can also be used to discover more than one bicluster in the same dataset, even when they are overlapped.	The model concerns only the order of values and thus makes the model quite restrictive.
6.	FLOC (Yang et al. 2003)	Deals with the Cheng and Church random masking issue.	Minimum overall coverage of bicluster in the dataset.
7.	BIMAX (Prelic et al. 2006)	At each step, the two partitioned matrices may have elements in common or not, allowing thus the possibility of finding overlapped biclusters.	Divide and conquer has the drawback of possibly missing good biclusters by early splits.
8.	MOEA (Mitra and Banka 2006)	The output consists of a large size of bicluster to a given threshold.	Converges slowly and consumes much time to find the best bicluster and no overlapping is carried out.
9.	SEBI (Divina and Aguilar-Ruiz 2006)	Matrix of weights is used for the control of overlapped elements among the different solutions.	Maximum similarity bicluster (MSB) works well for the special case of approximately small biclusters.
10.	MSB (Liu and Wang 2007)	(1) No discretization procedure is required, (2) Performs well for overlapping biclusters and works well for additive biclusters.	MSB works for the special case of approximately squares biclusters.
11.	RWB (Angiulli, Cesario, and Pizzuti 2008)	In order to avoid getting trapped into poor local minima, the algorithm executes random moves according to a probability given by the user.	Randomness reduces the convergence speed for large dataset. So it consumes much time to find the best bicluster.
12.	CMOPSOB (Liu et al. 2009)	Speed up the convergence to the Pareto front and also guarantee diversity of solutions.	Using PSO has the problems of dependency on initial point and parameters, difficulty in finding their optimal design parameters, and the stochastic characteristic of the final outputs.
13.	BicFinder (Ayadi et al, 2012a)	Do not require fixing a minimum or a maximum number of genes or conditions, enabling a generation of diversified biclusters.	Place the restrictive constraints on the structure of the biclustering solutions.
14.	PDNS (Ayadi et al, 2012b)	It works well for shifting and scaling pattern of expression value.	No overlapping control is carried out among the reported solutions.
15.	CoBi (Roy, Bhattacharyya, and Kalita 2013)	Particularly, it is used for grouping both positively and negatively regulated genes from microarray expression data.	It extracts small volume of biclusters for large MSR value.
16.	MBA (Ayadi, Elloumi, and Hao 2014)	It is used for grouping both positively and negatively regulated genes from microarray expression data.	It extracts small-size biclusters, and the quality of biclusters depends upon the threshold value
17.	EBACross (Maatouk et al. 2014)	Increase in the diversification of solution can be achieved by a mutation operator.	Computational cost is high on large inputs.
18.	BiBin Max (Saber and Elloumi 2015)	Fast retrieval method.	Too many parameter setting may affect the overall performance.
19.	UniBic (Wang, Li, and Robinson 2016)	Biologically meaningful trend-preserving biclusters can be detected.	It returns small volume of biclusters.
20.	SEB (Yin and Liu 2017)	Efficient and scalable in terms of the biological significance and runtime.	SEB works well for the special case of approximately small biclusters.

Algorithm 1. Pseudo code for SCS-NM.

Input: Number of nest n, Discovery rate of alien solutions pa, Maximum number of iteration MaxIter Output: coherent biclusters

Generate random population with n nests and each nest consists of 3 eggs (clutch). lwhile (t < MaxIter) Get a cuckoo (say i) randomly and generate a solution using Nelder–Mead Choose a nest among n (say, j) randomly; Replace worst egg in j by the new solution i; A fraction (pa) of worse nests are abandoned and new ones/solutions are built/generated Keep best solutions (or nests with quality solutions) Rank the solutions/nests and find the current best; Pass the current best to the next generation; if stagnation Sort the eggs by increasing order Partition or shuffle the egg into the nest, i.e. rank 1 goes to nest 1, rank 2 goes to nest 2, rank 3 goes to nest 3, rank 4 goes to nest 1, and so on. end while Arrange the best solution of individual nest in ascending order present the best solution of each nest.

Table 2. Dataset description.

Dataset name	Genes	Samples
Yeast Saccharomyces cerevisiae stress data	2993	173
Arabidopsis thaliana expression data	734	69
Yeast Saccharomyces cerevisiae cell-cycle data	2884	17
Rat CNS expression data	112	9

Figure 1. Plot of number of iterations versus fitness value for yeast stress data.

Figure 2. Plot of number of iterations versus fitness value for Arabidopsis thaliana data.

Figure 3. Plot of number of iterations versus fitness value for yeast cell-cycle data.

Figure 4. Plot of number of iterations versus fitness value for rat CNS data.

Table 3. Experiment results for Saccharomyces cerevisiae cell expression data.

Bicluster number	Genes	Conditions	Volume	MSR	Gene variance	CI	Fitness
BC1	1487	4	5948	181.69	1371.89	0.0305	181.69
BC4	1520	5	7600	223.45	1249.52	0.0290	223.45
BC8	1451	7	10,157	248.11	1264.74	0.0284	248.11
BC15	1473	8	11,784	261.75	1290.42	0.0222	261.75
BC5	1402	10	14,020	285.24	1364.41	0.0219	285.24

Figure 5. Plot of sample biclusters of size 8 × 5 for Arabidopsis thaliana data.

Table 4. Comparative analysis on yeast cell expression data.

Method	Average MSR	Average volume	Average number of genes	Average number of conditions	Largest volume
FLOC	187.44	1825.78	195.00	12.20	2000
DBF	114.70	1627.20	188.00	11.00	4000
CC	204.29	1576.98	167.00	12.00	4485
Single-objective GA	52.87	570.86	191.12	5.13	1408
SEBI	205.18	209.92	13.61	15.25	1394
MOEA	234.87	10,301.71	1095.43	9.29	14,828
CS	286.24	10,925.10	1281.67	7.63	14,586
CS-NM	254.45	11,963.78	1295.88	7.79	14,996
SCS-NM	229.15	12,387.44	1356.50	8.20	15,012

An italic and bold font represents significance of the proposed method.

Figure 6. Plot of proportions of biclusters significantly enriched by GO annotations on yeast cell-cycle data.

Table 5. Significant GO terms for three biclusters on Saccharomyces cerevisiae data.

Bicluster number	Number of genes	Process	Function	Component
BC1	1487	Cellular component organization (n = 685, p = 7.15 × 10^−33)	Binding activity (n = 517, p = 2.06 × 10^−9)	Nuclear part (n = 372, p = 7.89 × 10^−19)
BC4	1520	Cellular process (n = 1316, p = 3.18 × 10^−126)	Structural molecule activity (n = 294, p = 6.02 × 10^−24)	Cell part (n = 1427, p = 7.16 × 10^−110)
BC8	1451	Metabolic process (n = 1124, p = 3.22 × 10^−101)	Hydrolase activity (n = 299, p = 3.53 × 10^−29)	Intracellular part (n = 1312, p = 1.26 × 10^−93)

Figure 7. Plot of Gene Ontology biological process of yeast cell-cycle data (10 genes).

Cheng, Y., and G. M. Church. 2000. Biclustering of expression data’. Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, Menlo Park, United States, 93–103.

 Google Scholar

Tanay, A., R. Sharan, and R. Shamir. 2009. Discovering statistically significant biclusters in gene expression data. BMC Bioinformatics 18:136–44. doi:10.1093/bioinformatics/18.suppl_1.S136.

 Google Scholar

Murali, T., and S. Kasif. 2003. Extracting conserved gene expression motifs from gene expression data. Pacific Symposium on Biocomputing, Boston University, United States, 77–88.

 Google Scholar

Bergmann, S., J. Ihmels, and N. Barkai. 2003. Iterative signature algorithm for the analysis of large-scale gene expression data. Physical Review E 67:1–18. doi:10.1103/PhysRevE.67.031902.

 Web of Science ®Google Scholar

Ben-Dor, A., B. Chor, R. Karp, and Z. Yakhini. 2003. Discovering local structure in gene expression data: The order-preserving submatrix problem. Journal of Computational Biology 10:373–84. doi:10.1089/10665270360688075.

 PubMed Web of Science ®Google Scholar

Yang, J., Wang, H., Wang, W., and Yu, P. 2003, ‘Enhanced biclustering on expression data’: proceedings of the Third IEEE Symposium on BioInformatics and BioEngineering, pp. 321-327.

 Google Scholar

Prelic, A., Bleuler, S., Zimmermann, P., Buhlmann, P., Gruissem, W., and Hennig, L. 2006. A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics 22 (9):1122-1129.

 PubMed Web of Science ®Google Scholar

Mitra, S., and H. Banka. 2006. Multi-objective evolutionary biclustering of gene expression data. Pattern Recognition 39:2464–77. doi:10.1016/j.patcog.2006.03.003.

 Web of Science ®Google Scholar

Divina, F., and J. S. Aguilar-Ruiz. 2006. Biclustering of expression data with evolutionary computation. IEEE Transactions on Knowledge Data Engineering 18:590–602. doi:10.1109/TKDE.2006.74.

 Web of Science ®Google Scholar

Liu, X., and L. Wang. 2007. Computing the maximum similarity bi-clusters of gene expression data. BMC Bioinformatics 23:50–56. doi:10.1093/bioinformatics/btl560.

 Google Scholar

Angiulli, F., E. Cesario, and C. Pizzuti. 2008. Random walk biclustering for microarray data. Information Science 178 (6):1479–97. doi:10.1016/j.ins.2007.11.007.

 Web of Science ®Google Scholar

Liu, J., Z. Li, X. Hu, and Y. Chen. 2009. Biclustering of microarray data with mospo based on crowding distance. Bioinformatics 10:1–12.

 Web of Science ®Google Scholar

Ayadi, W., M. Elloumi, and J. Hao. 2012a. Pattern-driven neighborhood search for biclustering microarray data. BMC Bioinformatics 7:452–66.

 Google Scholar

Ayadi, W., M. Elloumi, and J. Hao. 2012b. BicFinder: A biclustering algorithm for microarray data analysis. Knowledge Information System 30:341–58. doi:10.1007/s10115-011-0383-7.

 Web of Science ®Google Scholar

Roy, S., D. K. Bhattacharyya, and J. K. Kalita. 2013. CoBi: Pattern based co-regulated biclustering of gene expression data. Pattern Recognition 34:1669–78. doi:10.1016/j.patrec.2013.03.018.

 Web of Science ®Google Scholar

Ayadi, W., M. Elloumi, and J. Hao. 2014. A memetic algorithm for discovering negative correlation biclusters of DNA microarray data. Neurocomputing 145:14–22. doi:10.1016/j.neucom.2014.05.074.

 Web of Science ®Google Scholar

Maatouk, O., W. Ayadi, H. Bouziri, and B. Duval. 2014. Evolutionary algorithm based on new crossover for the biclustering of gene expression data. Proceedings of the Ninth International Conference on IAPR Stockholm, Sweden, 48–59.

 Google Scholar

Saber, H. B., and M. Elloumi. 2015. Efficiently mining gene expression data via novel binary biclustering algorithms. Journal of Proteomics & Bioinformatics S9 (8). doi: 10.4172/jpb.S9-008.

 Google Scholar

Wang, Z., G. Li, and R. W. Robinson. 2016. UniBic: Sequential row-based biclustering algorithm for analysis of gene expression data’. Scientific Reports 6:23466. doi:10.1038/srep23466.

 PubMed Web of Science ®Google Scholar

Yin, L., and Y. Liu. 2017. Ensemble biclustering gene expression data based on the spectral clustering. Neural Computing and Applications 28:1–14.

 Google Scholar