BACKGROUND: Cis-regulatory modules (CRMs) are short stretches of DNA that help regulate gene expression in higher eukaryotes. They have been found up to 1 megabase away from the genes they regulate and can be located upstream, downstream, and even within their target genes. Due to the difficulty of finding CRMs using biological and computational techniques, even well-studied regulatory systems may contain CRMs that have not yet been discovered. RESULTS: We present a simple, efficient method (HexDiff) based only on hexamer frequencies of known CRMs and non-CRM sequence to predict novel CRMs in regulatory systems. On a data set of 16 gap and pair-rule genes containing 52 known CRMs, predictions made by HexDiff had a higher correlation with the known CRMs than several existing CRM prediction algorithms: Ahab, Cluster Buster, MSCAN, MCAST, and LWF. After combining the results of the different algorithms, 10 putative CRMs were identified and are strong candidates for future study. The hexamers used by HexDiff to distinguish between CRMs and non-CRM sequence were also analyzed and were shown to be enriched in regulatory elements. CONCLUSION: HexDiff provides an efficient and effective means for finding new CRMs based on known CRMs, rather than known binding sites.

MOTIVATION: Over-represented k-mers in genomic DNA regions are often of particular biological interest. For example, over-represented k-mers in co-regulated families of genes are associated with the DNA binding sites of transcription factors. To measure over-representation, we introduce a statistical background model based on single-mismatches, and apply it to the pooled 500 bp ORF Upstream Regions (USRs) of yeast. More importantly, we investigate the context and spatial distribution of over-represented k-mers in yeast USRs. RESULTS: Single and double-stranded spatial distributions of most over-represented k-mers are highly non-random, and predominantly cluster into a small number of classes that are robust with respect to over-representation measures. Specifically, we show that the three most common distribution patterns can be related to DNA structure, function, and evolution and correspond to: (a) homologous ORF clusters associated with sharply localized distributions; (b) regulatory elements associated with a symmetric broad hill-shaped distribution in the 50-200 bp USR; and (c) runs of As, Ts, and ATs associated with a broad hill-shaped distribution also in the 50-200 bp USR, with extreme structural properties. Analysis of over-representation, homology, localization, and DNA structure are essential components of a general data-mining approach to finding biologically important k-mers in raw genomic DNA and understanding the 'lexicon' of regulatory regions.

MOTIVATION: Computer-assisted methods are essential for the analysis of biosequences. Gene activity is regulated in part by the binding of regulatory molecules (transcription factors) to combinations of short motifs. The goal of our analysis is the development of algorithms to identify regulatory motifs and to predict the activity of combinations of those motifs. APPROACH: Our research begins with a new motif-finding method, using multiple objective functions and an improved stochastic iterative sampling strategy. Combinatorial motif analysis is accomplished by constructive induction that analyzes potential motif combinations. The hypothesis is generated by applying standard inductive learning algorithms. RESULTS: Tests using 10 previously identified regulons from budding yeast and 14 artificial families of sequences demonstrated the effectiveness of the new motif-finding method. Motif combination and classification approaches were used in the analysis of a sample DNA array data set derived from genome-wide gene expression analysis. AVAILABILITY: Programs will be available as executable files upon request. CONTACT: [email protected] [email protected]

One goal of Artificial Intelligence is to develop and understand computational mechanisms for solving difficult real-world problems. Unfortunately, domains traditionally used in general problem-solving research lack important characteristics of real-world domains, making it difficult to apply the techniques developed. Most classic AI domains require satisfying a set of Boolean constraints. Real-world problems require finding a solution that meets a set of Boolean constraints and performs well on a set of real-valued constraints. In addition, most classic domains are static while domains from the real world change. In this paper we demonstrate that SteppingStone, a general learning problem solver, is capable of solving problems with these characteristics. SteppingStone heuristically decomposes a problem into simpler subproblems, and then learns to deal with the interactions that arise between the subproblems. In lieu of an agreed upon metric for problem difficulty, we choose significant problems that are difficult for both people and programs as good candidates for evaluating progress. Consequently we adopt the domain of logic synthesis from VLSI design to demonstrate SteppingStone’s capabilities.

Instance‐based representations have been applied to numerous classification tasks with some success. Most of these applications involved predicting a symbolic class based on observed attributes. This paper presents an instance‐based method for predicting a numeric value based on observed attributes. We prove that, given enough instances, if the numeric values are generated by continuous functions with bounded slope, then the predicted values are accurate approximations of the actual values. We demonstrate the utility of this approach by comparing it with a standard approach for value prediction. The instance‐based approach requires neither ad hoc parameters nor background knowledge.

An examination of the character of naturally intelligent systems and artificially intelligent systems yields many qualitative differences. This short essay explores the possibility that these qualitative differences may be the reason for the limitations of current AI systems.

We develop a theory for the analysis of binary-valued digital pictures, particularly blobs and arcs, on a fairly large class of nonuniform as well as uniform mosaics. These so-called "acute mosaics" can represent a wide variety of schemes for digitizing images in machine vision systems. These mosaics can also represent a variety of retinas in human and animal visual systems. We prove the existence of minimum-perimeter-polygon (MPP) representations of digitized blobs on arbitrary mosaics and the uniqueness of MPP's in acute mosaics. We introduce the concept of "relative convexity," and show its relation to the MPP. We show that the MPP reflects the concavities of the digitized blob. We describe and prove the validity of simple tests for cellular convexity and cellular straightness. We present and prove the validity of an algorithm for computing the MPP of so-called "normal complexes" (a broad class of digitized blobs) on an acute mosaic.