Recovering all generalized order-preserving submatrices: new exact formulations and algorithms. (English) Zbl 1390.90400

Summary: Cluster analysis of gene expression data is a popular and successful way of elucidating underlying biological processes. Typically, cluster analysis methods seek to group genes that are differentially expressed across experimental conditions. However, real biological processes often involve only a subset of genes and are activated in only a subset of environmental or temporal conditions. To address this limitation, A. Ben-Dor et al. [“Discovering local structure in gene expression data: the order-preserving submatrix problem”, J. Comput. Biol. 10, 3–4, 373–384 (2003; doi:10.1089/10665270360688075)] developed an approach to identify order-preserving submatrices (OPSMs) in which the expression levels of included genes induce the sample linear ordering of experiments. In addition to gene expression analysis, OPSMs have application to recommender systems and target marketing. While the problem of finding the largest OPSM is \(\mathcal {NP}\)-hard, there have been significant advances in both exact and approximate algorithms in recent years. Building upon these developments, we provide two exact mathematical programming formulations that generalize the OPSM formulation by allowing for the reverse linear ordering, known as the generalized OPSM pattern, or GOPSM. Our formulations incorporate a constraint that provides a margin of safety against detecting spurious GOPSMs. Finally, we provide two novel algorithms to recover, for any given level of significance, all GOPSMs from a given data matrix, by iteratively solving mathematical programming formulations to global optimality. We demonstrate the computational performance and accuracy of our algorithms on real gene expression data sets showing the capability of our developments.


90C10 Integer programming
90C90 Applications of mathematical programming


Full Text: DOI


[1] Ben-Dor, A; Chor, B; Karp, R; Yakhini, Z, Discovering local structure in gene expression data: the order-preserving submatrix problem, Journal of Computational Biology, 10, 373-384, (2003)
[2] Busygin, S; Prokopyev, O; Pardalos, PM, Biclustering in data mining, Computers & Operations Research, 35, 2964-2987, (2008) · Zbl 1144.68309
[3] Causton, HC; Ren, B; Koh, SS; Harbison, CT; Kanin, E; Jennings, EG; Lee, TI; True, HL; Lander, ES; Young, RA, Remodeling of yeast genome expression in response to environmental changes, Molecular Biology of the Cell, 12, 323-337, (2001)
[4] Chui, C. K., Kao, B., Yip, K. Y., & Lee, S.D. (2008). Mining order-preserving submatrices from data with repeated measurements. In The 8th IEEE international conference on data mining (ICDM) (pp. 133-142). IEEE.
[5] Cooper, SJ; Trinklein, ND; Anton, ED; Nguyen, L; Myers, RM, Comprehensive analysis of transcriptional promoter structure and function in 1
[6] Fang, Q; Ng, W; Feng, J; Li, Y, Mining bucket order-preserving submatrices in gene expression data, IEEE Transactions on Knowledge and Data Engineering, 24, 2218-2231, (2012)
[7] Fang, Q; Ng, W; Feng, J; Li, Y, Mining order-preserving submatrices from probabilistic matrices, ACM Transactions on Database Systems, 39, 1-43, (2014) · Zbl 1321.68244
[8] Gao, B. J., Griffith, O. L., Ester, M., & Jones, S. J. (2006). Discovering significant OPSM subspace clusters in massive gene expression data. In Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 922-928). New York, NY, Philadelphia, PA: ACM.
[9] Gao, BJ; Griffith, OL; Ester, M; Xiong, H; Zhao, Q; Jones, SJ, On the deep order-preserving submatrix problem: A best effort approach, IEEE Transactions on Knowledge and Data Engineering, 24, 309-325, (2012)
[10] Griffith, O. L., Gao, B. J., Bilenky, M., Prychyna, Y., Ester, M., & Jones, S. J. (2009). KiWi: A scalable subspace clustering algorithm for gene expression analysis. In Proceedings of the 3rd international conference on bioinformatics and biomedical engineering (iCBBE) (pp. 1-9). IEEE.
[11] Hochbaum, DS; Levin, A, Approximation algorithms for a minimization variant of the order-preserving submatrices and for biclustering problems, ACM Transactions on Algorithms, 9, 1-12, (2013) · Zbl 1301.68273
[12] Humrich, J., Gartner, T., & Garriga, G. C. (2011). A fixed parameter tractable integer program for finding the maximum order preserving submatrix. In The 11th international conference on data mining (ICDM) (pp. 1098-1103). IEEE.
[13] IBM. (2015). IBM ILOG CPLEX 12.5.1 user’s manual. IBM ILOG CPLEX Division, Incline Village, NV. · Zbl 1144.68309
[14] King, JY; Ferrara, R; Tabibiazar, R; Spin, JM; Chen, MM; Kuchinsky, A; Vailaya, A; Kincaid, R; Tsalenko, A; Deng, DXF; etal., Pathway analysis of coronary atherosclerosis, Physiological Genomics, 23, 103-118, (2005)
[15] Madeira, SC; Oliveira, AL, Biclustering algorithms for biological data analysis: A survey, IEEE Transactions on Computational Biology and Bioinformatics, 1, 24-45, (2004)
[16] Spellman, PT; Sherlock, G; Zhang, MQ; Iyer, VR; Anders, K; Eisen, MB; Brown, PO; Botstein, D; Futcher, B, Comprehensive identification of cell cycle-regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization, Molecular Biology of the Cell, 9, 3273-3297, (1998)
[17] Trapp, AC; Prokopyev, OA, Solving the order-preserving submatrix problem via integer programming, INFORMS Journal on Computing, 22, 387-400, (2010) · Zbl 1243.90151
[18] Yip, KY; Kao, B; Zhu, X; Chui, CK; Lee, SD; Cheung, DW, Mining order-preserving submatrices from data with repeated measurements, IEEE Transactions on Knowledge and Data Engineering, 25, 1587-1600, (2013)
[19] Zhang, M., Wang, & W., Liu, J. (2008). Mining approximate order preserving clusters in the presence of noise. In IEEE 24th international conference on data engineering (ICDE) (pp. 160-168). IEEE.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.