Mining Frequent Boolean Expressions
Mohammed Javeed Zaki, Naren Ramakrishnan, Lizhuang Zhao · International Journal of Knowledge Discovery in Bioinformatics · 2010
Regulatory network analysis and other bioinformatics tasks require the ability to induce and represent arbitrary boolean expressions from data sources. In this paper, the authors introduce a novel framework called BLOSOM for mining (frequent) boolean expressions over binary-valued datasets. Boolean expressions can be grouped into four categories: pure conjunctions, pure disjunctions, conjunction of disjunctions, and disjunction of conjunctions. The authors’ main focus is on mining the simplest expressions (the minimal generators), but also to propose closure operators that yield closed (or unique maximal) boolean expressions. BLOSOM efficiently mines frequent boolean expressions by utilizing a number of methodical pruning techniques. Experiments showcase the behavior of BLOSOM for different input settings and parameter thresholds. Application studies on gene expression and gene regulation patterns showcase the effectiveness of this approach.