Comparison of constructions of irregular Gallager codes

The low-density parity check codes whose performance is closest to the Shannon limit are `Gallager codes' based on irregular graphs. We compare alternative methods for constructing these graphs and present two results. First, we find a `super-Poisson' construction which gives a small improvement in empirical performance over a random construction. Second, whereas Gallager codes normally take N2 time to encode, we investigate constructions of regular and irregular Gallager codes that allow more rapid encoding and have smaller memory requirements in the encoder. We find that these `fast encoding' Gallager codes have equally good performance.

Streaming covariance selection with applications to adaptive querying in sensor networks

Sensor networks can be naturally represented as graphical models, where the edge set encodes the presence of sparsity in the correlation structure between sensors. Such graphical representations can be valuable for information mining purposes as well as for optimizing bandwidth and battery usage with minimal loss of estimation accuracy. We use a computationally efficient technique for estimating sparse graphical models which fits a sparse linear regression locally at each node of the graph via the Lasso estimator. Using a recently suggested online, temporally adaptive implementation of the Lasso, we propose an algorithm for streaming graphical model selection over sensor networks. With battery consumption minimization applications in mind, we use this algorithm as the basis of an adaptive querying scheme. We discuss implementation issues in the context of environmental monitoring using sensor networks, where the objective is short-term forecasting of local wind direction. The algorithm is tested against real UK weather data and conclusions are drawn about certain tradeoffs inherent in decentralized sensor networks data analysis. © 2010 The Author. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.

New tools for self-organised pattern formation

Position-dependent gene expression is a critical aspect of the development and behaviour of multicellular organisms. It requires a complex series of interactions to occur between different cell types in addition to intracellular signalling cascades. We used Escherichia coli to study the properties of an artificial signalling system at the interface between two expanding cell populations. We genetically engineered one population to produce a diffusible acyl-homoserine lactone (AHL) signal, and another population to respond to it. Our experiments demonstrate how such a signal can be used to reproducibly generate simple visible patterns with high accuracy in swimming agar. The producing and responding cassettes of two such signalling systems can be linked to produce a symmetric interface for bidirectional communication that can be used to visualise molecular logic. Intracellular feedback between these two cassettes would then create a framework for self-organised patterning of higher complexity. Adapting the experiments of Basu et al. (Basu et al., 2005) using cell motility, rather than a differential response to AHL concentrations as a way to define zones of response, we noted how the interaction of sender and receiver cell populations on a swimming plate could lead to complex pattern formation. Equipping highly motile strains such as E. coli MC1000 with AHL-mediated auto-inducing systems based on Vibrio fischeri luxI/luxR and Pseudomonas aeruginosa lasI/lasR cassettes would allow the amplification of a response to an AHL signal and its propagation. We designed and synthesised codon-optimised auto-inducing luxI/R and lasI/R cassettes as optimal gene expression is crucial for the generation of robust patterns. We still have to complete and test the entire genetic circuitry, although by modelling the system we were able to demonstrate its feasibility. © 2007 The Institution of Engineering and Technology.