K Atteson | PubMed Health

PubMed2000

Constraint structure analysis of gene expression.

A microarray experiment gives a snapshot of the state of an organism in terms of the relative abundances of its mRNA transcripts, locating the organism at a point in a high dimensional state space where each axis represents the relative expression level of a single gene. Multiple experiments generate a cloud of points in this gene expression space. We present a geometric approach to analyzing the covariational properties of such a cloud and use a dataset from Saccharomyces cerevisiae as an illustration. In particular, we use singular value decomposition to identify significant linear sub-structures in the data and analyze the contributions of both individual genes and functional classes of genes to these major directions of variation. Analyzing the publicly available yeast expression data, we show that under all experimental conditions the variation in expression is limited to a small number of linear dimensions. Projections of individual gene axes onto the significant dimensions can order the contribution of individual genes to variation in expression within an experiment. We show that no particular groups of genes characterize particular experimental conditions. Instead, the particular structure of the coordinated expression of the entire genome characterizes a particular experiment.

Gene Expression↗

PubMed1998

Calculating the exact probability of language-like patterns in biomolecular sequences.

We present algorithms for the exact computation of the probability that a random string of a certain length matches a given regular expression. These algorithms can be used to determine statistical significance in a variety of pattern searches such as motif searches and gene-finding. This work improves upon work of Kleffe and Langebacker (Kleffe & Langbecker 1990) and of Sewell and Durbin (Sewell & Durbin 1995) in several ways. First, in many cases of interest, the algorithms presented here are faster. In addition, the type of pattern considered here strictly includes those of both previous works but also allows, for instance, arbitrary length gaps. Also, the type of probability model which can be used is more general than that of Sewell and Durbin, allowing for Markov chains. The problem solved in this work is in fact in the class of NP-hard problems which are believed to be intractable. However, the problem is fixed-parameter tractable, meaning that it is tractable for small patterns. The is problem is also computationally feasible for many patterns which occur in practice. As a sample application, we consider calculating the statistical significance of most of the PROSITE patterns as in Sewell and Durbin. Whereas their method was only fast enough to exactly compute the probabilities for sequences of length 13 larger than the pattern length, we calculate these probabilities for sequences of up to length 2000. In addition, we calculate most of these probabilities using a first order Markov chain. Most of the PROSITE patterns have high significance at length 2000 under both the i.i.d. and Markov chain models. For further applications, we demonstrate the calculation of the probability of a PROSITE pattern occurring on either strand of a random DNA sequence of up to 500 kilo-bases and the probability of a simple gene model occurring in a random sequence of up to 1 megabase.

Algorithms↗