Mining Frequent Boolean Expressions: Application to Gene Expression and Regulatory Modeling

Mining Frequent Boolean Expressions: Application to Gene Expression and Regulatory Modeling

Mohammed J. Zaki (Rensselaer Polytechnic Institute, USA), Naren Ramakrishnan (Virginia Tech., USA) and Lizhuang Zhao (Microsoft Corp., USA)
Copyright: © 2010 |Pages: 29
DOI: 10.4018/jkdb.2010070105
OnDemand PDF Download:
No Current Special Offers


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.
Article Preview


A key class of problems in biological knowledge discovery pertains to modeling complex relationships between entities, such as GO category descriptions, genetic regulatory connections, and metabolic pathway networks. To effectively address these tasks, we require data mining techniques that possess the expressiveness to model arbitrary boolean connections. However, many state-of-the-art techniques are rather restrictive in the class of expressions they can mine.

For example, itemset mining (Agrawal et al., 1996) takes as input a binary-valued dataset and discovers patterns that are pure conjunctions of items. Admittedly, such techniques are useful in bioinformatics, but have limited scope. For example, given the expression levels (high or low) of genes for various cancers, we may find that cancerous tissues have high levels of genes (g1 AND g5 AND g13) OR (g10 AND g15). This might indicate that these groups of genes are co-regulated and somehow linked to cancer. These techniques can be generalized to include negations of descriptions and used to mine redescriptions (Ramakrishnan et al., 2004), that is, finding alternative ways of describing a group of genes. For instance, from yeast gene expression data, we may find that the gene highly expressed at time point 15 mins (d183), but not involved in mannose transportation (d388) or fructose metabolism (d515) or not part of external protective structure (d460), are the exact same genes also highly expressed at time point 20 mins (d184), provided they do not have unknown molecular function (d309). This redescription can be written as an equivalence of boolean expressions: d183 AND (NOT d388) AND (NOT d460) AND (NOT d515) ⇔ d184 AND (NOT d309).

We seek to generalize these approaches to mine arbitrary boolean expressions. Boolean expression mining can provide tremendous value, but there are two main challenges to contend with. The first deals with the problem of high computational complexity. With n items (or variables), there are jkdb.2010070105.m01 possible distinct-valued Boolean expressions. With n items, there are 2n distinct ways of assigning true/false values to the n terms, and for any such assignment the truth value of the expression can be set to true or false, giving the jkdb.2010070105.m02 value. These are far too many to enumerate. To make the search practical we focus on only the frequent boolean expressions. Also instead of mining all frequent boolean expressions, we focus on mining a lossless subset that retains complete frequency information, namely closed boolean expression. The second challenge relates to comprehension of the patterns, i.e., they may be complex and difficult to understand. Here we focus on mining the simplest or minimal expressions (which are in fact the minimal generators of the closed expressions) that still from a lossless representation of all possible boolean expressions.

In this paper, we present a novel framework, called BLOSOM (an anagram of the bold letters in BOOLean expression Mining over attribute Sets), the first such approach to simultaneously mine closed boolean expressions over attribute sets and their minimal generators. Our main contributions are as follows: We organize boolean expressions into four categories: (i) pure conjunctions (AND-clauses), (ii) pure disjunctions (OR-clauses), (iii) conjunctive normal form (CNF; conjunction of disjunctions), and (iv) disjunctive normal form (DNF; disjunction of conjunctions). For both CNF and DNF expressions we propose a closure operator, and we give a characterization of the minimal generators. BLOSOM employs a number of effective pruning techniques for searching over the space of boolean expressions, yielding orders of magnitude in speedup. We conducted several experiments on synthetic datasets to study the behavior of BLOSOM with respect to (w.r.t.) different input settings and parameter thresholds. We also highlight some of the patterns found using BLOSOM on real datasets from bioinformatics applications such as analysis of gene expression patterns, and boolean gene regulatory network discovery.

Complete Article List

Search this Journal:
Open Access Articles
Volume 8: 2 Issues (2018)
Volume 7: 2 Issues (2017)
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2015)
Volume 4: 2 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing