A Clique-Based Approach to the Identification of Common Gene Association Sub-Networks


We developed a computational framework to identify common gene association sub-network. This framework combines graphical lasso model, graph product and a replicator equation based clique solver. We applied this method to find common stress responsive sub-networks from two related Deinococcus-Thermus bacterial species.

Share and Cite:

G. Zheng, A. Tesfay, X. Huang and A. Tokuta, "A Clique-Based Approach to the Identification of Common Gene Association Sub-Networks," Applied Mathematics, Vol. 4 No. 6, 2013, pp. 893-898. doi: 10.4236/am.2013.46123.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] J. Schafer and K. Strimmer, “An Empirical Bayes Approach to Inferring Large-Scale Gene Association Networks,” Bioinformatics, Vol. 21, No. 6, 2005, pp. 754764.
[2] P. Langfelder and S. Horvath, “WGCNA: An R Package for Weighted Correlation Network Analysis,” BMC Bioinformatics, Vol. 9, No. 1, 2008, p. 559. doi:10.1186/1471-2105-9-559
[3] N. Friedman, “Inferring Cellular Networks Using Probabilistic Graphical Models,” Science, Vol. 303, No. 5659, 2004, pp. 799-805. doi:10.1126/science.1094068
[4] M. K. S. Yeung, J. Tegnér and J. J. Collins, “Reverse Engineering Gene Networks Using Singular Value Decomposition and Robust Regression,” Proceedings of the National Academy of Sciences, Vol. 99, No. 9, 2002, pp. 6163-6168.
[5] C. Rangel, J. Angus, Z. Ghahramani, M. Lioumi, E. Sotheran, A. Gaiba, D. L. Wild and F. Falciani, “Modeling T-Cell Activation Using Gene Expression Profiling and State-Space Models,” Bioinformatics, Vol. 20, No. 9, 2004, pp. 1361-1372.
[6] J. Friedman, T. Hastie and R. Tibshirani, “Sparse Inverse Covariance Estimation with the Graphical Lasso,” Biostatistics, Vol. 9, No. 3, 2008, pp. 432-441.
[7] M. Pelillo, “Replicator Equations, Maximal Cliques, and Graph Isomorphism,” Neural Computation, Vol. 11, No. 8, 1999, pp. 1933-1955.
[8] R. Battiti and M. Protasi, “Reactive Local Search for the Maximum Clique Problem,” Algorithmica, Vol. 29, No. 4, 2001, pp. 610-637. doi:10.1007/s004530010074
[9] T. S. Motzkin and E. G. Straus, “Maxima for Graphs and a New Proof of a Theorem of Turán,” Canadian Journal of Mathematics, Vol. 17, 1965, pp. 533-540. doi:10.4153/CJM-1965-053-6
[10] N. Meinshausen and P. Bühlmann, “High-Dimensional Graphs and Variable Selection with the Lasso,” The Annals of Statistics, Vol. 34, No. 3, 2006, pp. 1436-1462. doi:10.1214/009053606000000281
[11] O. Banerjee, L. E. Ghaoui and A. d’Aspremont, “Model Selection through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data,” Journal of Machine Learning Research, Vol. 9, 2008, pp. 485516.
[12] A. Forsgren, P. E. Gill and M. H. Wright, “Interior Methods for Nonlinear Optimization,” SIAM Review, Vol. 44, No. 4, 2002, pp. 525-597. doi:10.1137/S0036144502414942
[13] J. Friedman, T. Hastie, H. Hofling and R. Tibshirani, “Pathwise Coordinate Optimization,” Annals of Applied Statistics, Vol. 1, No. 2, 2007, p. 302. doi:10.1214/07-AOAS131
[14] T. Wu and K. Lange, “Coordinate Descent Procedures for Lasso Regularized Regression,” Annals of Applied Statistics, Vol. 2, No. 1, 2008, pp. 224-244. doi:10.1214/07-AOAS147
[15] M. Pelillo and A. Jagota, “Feasible and Infeasible Maxima in a Quadratic Program for Maximum Clique,” Journal of Artificial Neural Network, Vol. 2, No. 4, 1996, pp. 411-420.
[16] L. E. Gibbons, D. W. Hearn and P. M. Pardalos, “A Continuous Based Heuristic for the Maximum Clique Problem,” In: D. S. Johnson and M. A. Trick, Eds., Cliques, Coloring, and Satisfiability—Second DIMACS Implementation Challenge, American Mathematical Society, 1996, pp. 103-124.
[17] P. M. Pardalos and A. T. Phillips, “A Global Optimization Approach for Solving the Maximum Clique Problem,” International Journal of Computer Mathematics, Vol. 33, No. 3-4, 1990, pp. 209-216.
[18] M. Pelillo, “Relaxation Labeling Networks for the Maximum Clique Problem,” Journal of Artificial Neural Network, Vol. 2, No. 4, 1996, pp. 313-328.
[19] I. M. Bomze, “Evolution towards the Maximum Clique,” Journal of Global Optimization, Vol. 10, No. 2, 1997, pp. 143-164. doi:10.1023/A:1008230200610
[20] D. S. Johnson and M. A. Trick, Eds., “Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge,” AMS, Providence, 1996.
[21] T. Barrett and R. Edgar, “Gene Expression Omnibus: Microarray Data Storage, Submission, Retrieval, and Analysis,” Methods in Enzymology, Vol. 411, 2006, pp. 352369. doi:10.1016/S0076-6879(06)11019-8
[22] J. D. Peterson, L. A. Umayam, T. Dickinson, E. K. Hickey and O. White, “The Comprehensive Microbial Resource,” Nucleic Acids Research, Vol. 29, No. 1, 2001, pp. 123-125.
[23] T. van der Heide and B. Poolman, “Osmoregulated ABCTransport System of Lactococcus lactis Senses Water Stress via Changes in the Physical State of the Membrane,” Proceedings of the National Academy of Sciences, Vol. 97, No. 13, 2000, pp. 7102-7106.
[24] M. Schmalisch, I. Langbein and J. Stulke, “The General Stress Protein Ctc of Bacillus subtilis Is a Ribosomal Protein,” Journal of Molecular Microbiology and Biotechnology, Vol. 4, 2002, pp. 495-501.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.