Problems of Boolean Reasoning Based Biclustering Parallelization

Authors: Marcin Michalak

Abstract:

Biclustering is the way of two-dimensional data analysis. For several years it became possible to express such issue in terms of Boolean reasoning, for processing continuous, discrete and binary data. The mathematical backgrounds of such approach — proved ability of induction of exact and inclusion–maximal biclusters fulfilling assumed criteria — are strong advantages of the method. Unfortunately, the core of the method has quite high computational complexity. In the paper the basics of Boolean reasoning approach for biclustering are presented. In such context the problems of computation parallelization are risen.

Keywords: Boolean reasoning, biclustering, parallelization, prime implicant.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.3669176

References:

[1] J. A. Hartigan, “Direct Clustering of a Data Matrix,” Journal of the American Statistical Association, vol. 67, no. 337, pp. 123–129, 1972.
[2] M. Michalak and D. ´ Sle¸zak, “Boolean Representation for Exact Biclustering,” Fundamenta Informaticae, vol. 161, no. 3, pp. 275–297, 2018.
[3] ——, “On Boolean Representation of Continuous Data Biclustering,” Fundamenta Informaticae, vol. 167, no. 3, pp. 193–217, 2019.
[4] M. Michalak, “Induction of Centre–Based Biclusters in Terms of Boolean Reasoning,” Advances in Intelligent Systems and Computing, 2019 (to appear).
[5] Y. Cheng and G. Church, “Biclustering of Expression Data,” Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, vol. 8, pp. 93–103, 2000.
[6] J. Yang, H. Wang, W. Wang, and P. Yu, “Enhanced Biclustering on Expression Data,” in Proceedings of the Third IEEE Symposium on Bioinformatics and Bioengineering, 2003, pp. 321–327.
[7] T. M. Murali and S. Kasif, “Extracting Conserved Gene Expression Motifs from Gene Expression Data,” in Proceedings of Pacific Symposium on Biocomputing, 2003, pp. 77–88.
[8] A. Preli´c, S. Bleuler, P. Zimmermann, A. Wille, P. B¨uhlmann, W. Gruissem, L. Hennig, L. Thiele, and E. Zitzler, “A Systematic Comparison and Evaluation of Biclustering Methods for Gene Expression Data,” Bioinformatics, vol. 22, no. 9, pp. 1122–1129, 2006.
[9] S. Hochreiter, U. Bodenhofer, M. Heusel, A. Mayr, A. Mitterecker, A. Kasim, T. Khamiakova, S. Van Sanden, D. Lin, W. Talloen, L. Bijnens, H. W. H. Goehlmann, Z. Shkedy, and D.-A. Clevert, “FABIA: Factor Analysis for Bicluster Acquisition,” Bioinformatics, vol. 26, no. 12, pp. 1520–1527, 2010.
[10] A. Kasim, Z. Shkedy, S. Kaiser, S. Hochreiter, and W. Talloen, Applied Biclustering Methods for Big and High Dimensional Data using R. CRC Press, Taylor & Francis Group, 2016.
[11] D. I. Ignatov and B. W. Watson, “Towards a Unified Taxonomy of Biclustering Methods,” in Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis, vol. 1522, 2016, pp. 23–39.
[12] A. Serin and M. Vingron, “DeBi: Discovering Differentially Expressed Biclusters using a Frequent Itemset Approach,” Algorithms for Molecular Biology, vol. 6, no. 1, 2011.
[13] M. Michalak, R. Jaksik, and D. ´ Sle¸zak, “Heuristic Search of Exact Biclusters in Binary Data,” International Journal of Applied Mathematics and Computer Science, 2019 (to appear).