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: © 2012 |Pages: 29
DOI: 10.4018/978-1-4666-1785-8.ch008


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

Complete Chapter List

Search this Book: