Recent advances in DNA sequencing technology have caused an exponential growth of publicly available genomic sequence data. A particularly voluminous, frequently used static data set are whole genome alignments. The first lossless compression algorithm for such data sets based on well-established statistical evolutionary models and prediction techniques from lossless binary image compression is introduced. The compression rate is improved by a factor of 1.6 compared to the currently used Lempel-Ziv (LZ) compression.

Rapid development of DNA sequencing technologies exponentially increases the amount of publicly available genomic data. Whole genome multiple sequence alignments represent a particularly voluminous, frequently downloaded static dataset. In this work we propose an asymmetric source coding scheme for such alignments using evolutionary prediction in combination with lossless black and white image compression. Compared to the Lempel-Ziv algorithm used so far the compression rates are almost halved.

Modeling the joint expression patterns of genes is a challenging task due to the large number of genes simultaneously studied, relative to the amount of microarray data available. To model the joint expression profiles of genes using a small number of observations, we use Ising models to approximate the joint expression profiles. This approach naturally lends itself to the study of gene interactions and has a close connection to clustering techniques, which we use to reconstruct E. coli gene interaction pathways from microarray data. In addition, we note that extending available partial network topology information can be done using very few microarray samples-logarithmic in the number of genes.

MOTIVATION: The problem of reverse engineering the dynamics of gene expression profiles is of focal importance in systems biology. Due to noise and the inherent lack of sufficiently large datasets generated via high-throughput measurements, known reconstruction frameworks based on dynamical systems models fail to provide adequate settings for network analysis. This motivates the study of new approaches that produce stochastic lists of explanations for the observed network dynamics that can be efficiently inferred from small sample sets and in the presence of errors. RESULTS: We introduce a novel algebraic modeling framework, termed stochastic polynomial dynamical systems (SPDSs) that can capture the dynamics of regulatory networks based on microarray expression data. Here, we refer to dynamics of the network as the trajectories of gene expression profiles over time. The model assumes that the expression data is quantized in a manner that allows for imposing a finite field structure on the observations, and the existence of polynomial update functions for each gene in the network. The underlying reverse engineering algorithm is based on ideas borrowed from coding theory, and in particular, list-decoding methods for so called Reed-Muller codes. The list-decoding method was tested on synthetic data and on microarray expression measurements from the M(3D) database, corresponding to a subnetwork of the Escherichia coli SOS repair system, as well as on the complete transcription factor network, available at RegulonDB. The results show that SPDSs constructed via list-decoders significantly outperform other algebraic reverse engineering methods, and that they also provide good guidelines for estimating the influence of genes on the dynamics of the network. AVAILABILITY: Software codes for list-decoding algorithms suitable for direct application to quantized expression data will be publicly available at the authors' web-pages.

We propose a novel algebraic method for reverse engineering the dynamics of gene regulatory networks of known topology, based on list-decoding and iterative model refinement algorithms. The crux of our approach is to describe the update functions for gene expressions in terms of polynomials over finite fields, or more precisely, codewords of Reed-Muller (RM) codes. In this setting, errors, missing data points, and small sample sizes of the measurements are accounted for via list-decoding of RM codes. We test the performance of the new method both on synthetic data and a regulatory sub-net of the E. coli gene control network responsible for DNA repair. The expression profiles used in the study are obtained through data fusion techniques over the many microbe microarray database. The list-decoding approach offers significant performance improvements over previously known algebraic methods, such as those based on Grobner bases techniques.

We provide an overview of known modeling approaches for gene regulatory networks, and introduce a new framework for analyzing such networks as probabilistic polynomial dynamical systems. In the latter context, we describe how list decoding methods for Reed-Muller codes can be used to cope with small DNA microarray sample set problems and measurement noise. We also describe possible future research directions at the interface of systems biology and coding theory, pertaining to probabilistic dynamical systems with memory and probabilistic factor graphs with local list-decoding components.

BACKGROUND: Comparative genomics aims to detect signals of evolutionary conservation as an indicator of functional constraint. Surprisingly, results of the ENCODE project revealed that about half of the experimentally verified functional elements found in non-coding DNA were classified as unconstrained by computational predictions. Following this observation, it has been hypothesized that this may be partly explained by biased estimates on neutral evolutionary rates used by existing sequence conservation metrics. All methods we are aware of rely on a comparison with the neutral rate and conservation is estimated by measuring the deviation of a particular genomic region from this rate. Consequently, it is a reasonable assumption that inaccurate neutral rate estimates may lead to biased conservation and constraint estimates. RESULTS: We propose a conservation signal that is produced by local Maximum Likelihood estimation of evolutionary parameters using an optimized sliding window and present a Kullback-Leibler projection that allows multiple different estimated parameters to be transformed into a conservation measure. This conservation measure does not rely on assumptions about neutral evolutionary substitution rates and little a priori assumptions on the properties of the conserved regions are imposed. We show the accuracy of our approach (KuLCons) on synthetic data and compare it to the scores generated by state-of-the-art methods (phastCons, GERP, SCONE) in an ENCODE region. We find that KuLCons is most often in agreement with the conservation/constraint signatures detected by GERP and SCONE while qualitatively very different patterns from phastCons are observed. Opposed to standard methods KuLCons can be extended to more complex evolutionary models, e.g. taking insertion and deletion events into account and corresponding results show that scores obtained under this model can diverge significantly from scores using the simpler model. CONCLUSION: Our results suggest that discriminating among the different degrees of conservation is possible without making assumptions about neutral rates. We find, however, that it cannot be expected to discover considerably different constraint regions than GERP and SCONE. Consequently, we conclude that the reported discrepancies between experimentally verified functional and computationally identified constraint elements are likely not to be explained by biased neutral rate estimates.

We consider the problem of estimating the parameters of a convolutional encoder from noisy data observations, i.e. when encoded bits are received with errors. Reverse engineering of a channel encoder has applications in cryptanalysis when attacking communication systems and also in DNA sequence analysis, when looking for possible error correcting codes in genomes. We present a new iterative, probabilistic algorithm based on the Expectation Maximization (EM) algorithm. We use the concept of log-likelihood ratio (LLR) algebra which will greatly simplify the derivation and interpretation of our final algorithm. We show results indicating the necessary data length and allowed channel error rate for reliable estimation.