Comparison of Parallelization Techniques for Boolean Reasoning-Based Binary Biclustering

Biclustering is a two-dimensional data analysis paradigm that aims to identify subsets of rows and columns in a data matrix whose intersection forms a submatrix satisfying predefined properties. In the case of binary data, a bicluster is typically defined as a submatrix containing exclusively ones or exclusively zeros. Numerous approaches to binary biclustering have been proposed over the last several decades. Among them, a distinctive line of research relies on Boolean reasoning, transforming the biclustering task into the problem of finding prime implicants of a data-dependent Boolean function. From a theoretical perspective, it has been shown that every prime implicant of the data-dependent Boolean function corresponds to an inclusion–maximal bicluster in the original dataset, and vice versa. Here, inclusion maximality means that no additional row or column can be added without violating the bicluster property. For discrete datasets, the corresponding Boolean function can be represented in Conjunctive Normal Form (CNF), where clauses contain up to three variables, reducing the general biclustering problem to an instance of the 3-SAT problem. Furthermore, the computational complexity of discrete-data biclustering can be reduced to the analysis of binary matrices. In this case, the associated Boolean functions consist of clauses containing at most two literals, yielding monotone 2-CNF formulas. This paper focuses on improving the efficiency of computations required to derive a disjunctive normal form (DNF) representation composed exclusively of prime implicants. Since the extraction of prime implicants constitutes the computational core of the Boolean biclustering framework, accelerating this process directly enhances the scalability and practical applicability of biclustering methods based on Boolean reasoning.