Problems of Boolean Reasoning Based Biclustering Parallelization

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.

Authors:

• Marcin Michalak

Keywords:

• Boolean reasoning
• biclustering
• parallelization
• prime implicant.

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).