D70 Nucleic Acids Research, 2008, Vol. 36, Database issue is available CMGSDB/. at https://bioinformatics.cs.vt.edu/cmgs/ COMPOSITIONAL DATA MINING (CDM) The basic idea in CDM is to mirror the shift-of- vocabulary as we traverse a database schema in a compo- sition of data-mining algorithms that mine the respective entities and relationships. For instance, consider a multi- ple stress environment where numerous physiological responses are occurring simultaneously. Eﬀorts to identify a set of C. elegans genes [perhaps encoding transcription factors (TFs)] to knock down (via RNAi) in order to ascertain key mechanisms of response might begin by identifying those genes whose knockdown produces phenotypes that modulate survival, and then ﬁnd one or more TFs that combinatorially control the expression of these genes. This analysis can be modeled as a chain: TFs ! genes ! phenotypes. Each step in this chain is computed using a data-mining algorithm, so that we ﬁrst mine the relationship between TFs and genes for concerted (TF, gene) sets called ‘biclusters’, then mine the relationship between genes and phenotypes to ﬁnd concerted biclusters of (gene, phenotype) pairs. The biclusters share the gene boundary leading us to investi- gate if these biclusters approximately match at the gene interface. The projection of the biclusters with an approximate match at one interface is called a ‘redescrip- tion’. Thus, CDM is a way of problem decomposition (see Ref. (3) for more details) where biclustering and redescription mining algorithms are chained in a way that mirrors the underlying ‘join-order’ path in the database schema. As illustrated in Figure 1, we mine biclusters between genes and the TFs that regulate them, mine biclusters between genes and the phenotypes that result when they are knocked down, and relate one side of the ﬁrst bicluster with one side of the second bicluster. Hence the task of integrating diverse data sources is reduced to composing data-mining patterns computed over each of the sources separately. The advantage of this formulation is that each data source can be mined individually using a biclustering algorithm that is suited for that purpose. For instance, the xMotif (4), SAMBA (5) and ISA (6) algorithms are suited for mining numeric data (e.g. such as gene expression relationships), while a priori (7) and CHARM (8) algorithms are suited for mining Boolean data (e.g. graph adjacencies). The approximate matching of biclusters is ensured using a similarity search algorithm or redescription mining approach. This problem, in various guises, has been studied by the database community; see Refs. (9) and (10) for examples. In this article, we utilize a cover-tree approach for fast computation of similar biclusters. The overlap between the sides of biclusters is qualiﬁed using the Jaccard’s coeﬃcient: the Jaccard’s coeﬃcient between two sets X and Y is the ratio: jX \ Yj=jX Yj Figure 1. Finding TFs whose knockdown induces improved desiccation tolerance in C. elegans. Two biclusters (shaded rectangles) joined at the gene interface using a redescription between their projections. Below that is the CDM schema, displaying the sequence of primitives. It is zero if the sets are disjoint and one if they are the same. In practice, we use a lax threshold on Jaccard’s coeﬃcient such as 0.5 and ensure that all similarities have a P-value signiﬁcance of at least 0.001. Speciﬁcally, we use the hypergeometric distribution to assess the likelihood of observing a given Jaccard’s threshold (given the sizes of X and Y) and use this probability to derive a P-value test. Given a database schema and two entity sets participat- ing in it, e.g. ‘TFs’ and ‘phenotypes’, we ﬁrst identify the paths between these entity sets in the underlying E/R diagram of the schema. Observe that there can be many paths, including recursive ones (e.g. ‘TFs regulate TFs which regulate other genes, contributing to phenotypes, when knocked down.’). Corresponding to each path, we instantiate a sequence of biclusterings and use the cover tree to identify redescriptions that can link them into chains. CMGSDB DATA SOURCES AND METHODS We refer to the biological entities captured in CMGSDB as ‘biots’. CMGSDB contains exhaustive data about the following biots in C. elegans: chromosomes, genes, transcripts and proteins. For genes, extensive annotations (IDs, locations, names, annotations, locus and transcripts)