Heuristic Search of Exact Biclusters in Binary Data

Michalak, Marcin; Jaksik, Roman; Ślęzak, Dominik

doi:10.34768/amcs-2020-0013

Abstract

The biclustering of two-dimensional homogeneous data consists in finding a subset of rows and a subset of columns whose intersection provides a set of cells whose values fulfil a specified condition. Usually it is defined as equality or comparability. One of the presented approaches is based on the model of Boolean reasoning, in which finding biclusters in binary or discrete data comes down to the problem of finding prime implicants of some Boolean function. Due to the high computational complexity of this task, the application of some heuristics should be considered. In the paper, a modification of the well-known Johnson strategy for prime implicant approximation induction is presented, which is necessary for the biclustering problem. The new method is applied to artificial and biomedical datasets.

References

Busygin, S., Prokopyev, O. and Pardalos, P.M. (2008). Biclustering in data mining, Computers & Operations Research35(9): 2964–2987.10.1016/j.cor.2007.01.005
Search in Google Scholar Back to article
Chagoyen, M., Carmona-Saez, P., Shatkay, H., Carazo, J.M. and Pascual-Montano, A. (2006). Discovering semantic features in the literature: A foundation for building functional associations, BMC Bioinformatics7, Article no.41.
Search in Google Scholar Back to article
Cheng, Y. and Church, G. (2000). Biclustering of expression data, Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology, San Diego, CA, USA, Vol. 8, pp. 93–103.
Search in Google Scholar Back to article
Gusenleitner, D., Howe, E.A., Bentink, S., Quackenbush, J. and Culhane, A.C. (2012). iBBiG: Iterative binary bi-clustering of gene sets, Bioinformatics28(19): 2484–2492.10.1093/bioinformatics/bts438
Search in Google Scholar Back to article
Hartigan, J.A. (1972). Direct clustering of a data matrix, Journal of the American Statistical Association67(337): 123–129.10.1080/01621459.1972.10481214
Search in Google Scholar Back to article
Hochreiter, S., Bodenhofer, U., Heusel, M., Mayr, A., Mitterecker, A., Kasim, A., Khamiakova, T., Van Sanden, S., Lin, D., Talloen, W., Bijnens, L., Goehlmann, H. W.H., Shkedy, Z. and Clevert, D.-A. (2010). FABIA: Factor analysis for bicluster acquisition, Bioinformatics26(12): 1520–1527.10.1093/bioinformatics/btq227
Search in Google Scholar Back to article
Ignatov, D.I. and Watson, B.W. (2016). Towards a unified taxonomy of biclustering methods, Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis, Stellenbosch, South Africa, Vol. 1522, pp. 23–39.
Search in Google Scholar Back to article
Johnson, D. (1974). Approximation algorithms for combinational problems, Journal of Computer and System Sciences9(3): 256–278.10.1016/S0022-0000(74)80044-9
Search in Google Scholar Back to article
Kasim, A., Shkedy, Z., Kaiser, S., Hochreiter, S. and Talloen, W. (2016). Applied Biclustering Methods for Big and High Dimensional Data Using R, CRC Press, Taylor & Francis Group, New York, NY.10.1201/9781315373966
Search in Google Scholar Back to article
Latkowski, R. (2003). On decomposition for incomplete data, Fundamenta Informaticae54(1): 1–16.
Search in Google Scholar Back to article
Michalak, M. and Ślęzak, D. (2018). Boolean representation for exact biclustering, Fundamenta Informaticae161(3): 275–297.10.3233/FI-2018-1703
Search in Google Scholar Back to article
Michalak, M. and Ślęzak, D. (2019). On Boolean representation of continuous data biclustering, Fundamenta Informaticae167(3): 193–217.10.3233/FI-2019-1814
Search in Google Scholar Back to article
Murali, T.M. and Kasif, S. (2003). Extracting conserved gene expression motifs from gene expression data, Proceedings of the Pacific Symposium on Biocomputing, Kauai, HI, USA, pp. 77–88.
Search in Google Scholar Back to article
Orzechowski, P. and Boryczko, K. (2016). Text mining with hybrid biclustering algorithms, Proceedings of the 15th International Conference on Artificial Intelligence and Soft Computing, Zakopane, Poland, pp. 102–113.
Search in Google Scholar Back to article
Prelić, A., Bleuler, S., Zimmermann, P., Wille, A., Bühlmann, P., Gruissem, W., Hennig, L., Thiele, L. and Zitzler, E. (2006). A systematic comparison and evaluation of biclustering methods for gene expression data, Bioinformatics22(9): 1122–1129.10.1093/bioinformatics/btl06016500941
Search in Google Scholar Back to article
Rodriguez-Baena, D.S., Perez-Pulido, A.J. and Aguilar-Ruiz, J.S. (2011). A biclustering algorithm for extracting bit-patterns from binary datasets, Bioinformatics27(19): 2738–2745.10.1093/bioinformatics/btr46421824973
Search in Google Scholar Back to article
Serin, A. and Vingron, M. (2011). DeBi: Discovering differentially expressed biclusters using a frequent itemset approach, Algorithms for Molecular Biology6, Article no. 1.
Search in Google Scholar Back to article
Tanay, A., Sharan, R. and Shamir, R. (2005). Handbook of Computational Molecular Biology, Chapman & Hall/CRC Press, New York, NY.
Search in Google Scholar Back to article
Yang, J., Wang, H., Wang, W. and Yu, P. (2003). Enhanced biclustering on expression data, Proceedings of the 3rd IEEE Symposium on Bioinformatics and Bioengineering, Bethesda, MD, USA, pp. 321–327.
Search in Google Scholar Back to article

Heuristic Search of Exact Biclusters in Binary Data

Abstract

Paradigm

My account