In a deterministic world, a planning agent can be certain of the consequences of its planned sequence of actions. Not so, however, in dynamic, stochastic domains where Markov decision processes are commonly used. Unfortunately these suffer from the `curse of dimensionality': if the state space is a Cartesian product of many small sets (`dimensions'), planning is exponential in the number of those dimensions. Our new technique exploits the intuitive strategy of selectively ignoring various dimensions in different parts of the state space. The resulting non-uniformity has strong implications, since the approximation is no longer Markovian, requiring the use of a modified planner. We also use a spatial and temporal proximity measure, which responds to continued planning as well as movement of the agent through the state space, to dynamically adapt the abstraction as planning progresses. We present qualitative and quantitative results across a range of experimental domains showing that an agent exploiting this novel approximation method successfully finds solutions to the planning problem using much less than the full state space. We assess and analyse the features of domains which our method can exploit.

BACKGROUND: Traditional genome alignment methods consider sequence alignment as a variation of the string edit distance problem, and perform alignment by matching characters of the two sequences. They are often computationally expensive and unable to deal with low information regions. Furthermore, they lack a well-principled objective function to measure the performance of sets of parameters. Since genomic sequences carry genetic information, this article proposes that the information content of each nucleotide in a position should be considered in sequence alignment. An information-theoretic approach for pairwise genome local alignment, namely XMAligner, is presented. Instead of comparing sequences at the character level, XMAligner considers a pair of nucleotides from two sequences to be related if their mutual information in context is significant. The information content of nucleotides in sequences is measured by a lossless compression technique. RESULTS: Experiments on both simulated data and real data show that XMAligner is superior to conventional methods especially on distantly related sequences and statistically biased data. XMAligner can align sequences of eukaryote genome size with only a modest hardware requirement. Importantly, the method has an objective function which can obviate the need to choose parameter values for high quality alignment. The alignment results from XMAligner can be integrated into a visualisation tool for viewing purpose. CONCLUSIONS: The information-theoretic approach for sequence alignment is shown to overcome the mentioned problems of conventional character matching alignment methods. The article shows that, as genomic sequences are meant to carry information, considering the information content of nucleotides is helpful for genomic sequence alignment. AVAILABILITY: Downloadable binaries, documentation and data can be found at ftp://ftp.infotech.monash.edu.au/software/DNAcompress-XM/XMAligner/.

This paper introduces a novel algorithm for biological sequence compression that makes use of both statistical properties and repetition within sequences. A panel of experts is maintained to estimate the probability distribution of the next symbol in the sequence to be encoded. Expert probabilities are combined to obtain the final distribution. The resulting information sequence provides insight for further study of the biological sequence. Each symbol is then encoded by arithmetic coding. Experiments show that our algorithm outperforms existing compressors on typical DNA and protein sequence datasets while maintaining a practical running time.

BACKGROUND: Features of a DNA sequence can be found by compressing the sequence under a suitable model; good compression implies low information content. Good DNA compression models consider repetition, differences between repeats, and base distributions. From a linear DNA sequence, a compression model can produce a linear information sequence. Linear space complexity is important when exploring long DNA sequences of the order of millions of bases. Compressing a sequence in isolation will include information on self-repetition. Whereas compressing a sequence Y in the context of another X can find what new information X gives about Y. This paper presents a methodology for performing comparative analysis to find features exposed by such models. RESULTS: We apply such a model to find features across chromosomes of Cyanidioschyzon merolae. We present a tool that provides useful linear transformations to investigate and save new sequences. Various examples illustrate the methodology, finding features for sequences alone and in different contexts. We also show how to highlight all sets of self-repetition features, in this case within Plasmodium falciparum chromosome 2. CONCLUSION: The methodology finds features that are significant and that biologists confirm. The exploration of long information sequences in linear time and space is fast and the saved results are self documenting.

Gene regulatory networks influence development and evolution in living organism. The advent of microarray technology has challenged computer scientists to develop better algorithms for modeling the underlying regulatory relationship in between the genes. Recently, a fuzzy logic model has been proposed to search microarray datasets for activator/repressor regulatory relationship. We improve this model for searching regulatory triplets by means of predicting changes in expression level of the target over interval time points based on input expression level, and comparing them with actual changes. This method eliminates possible false predictions from the classical fuzzy model thereby allowing a wider search space for inferring regulatory relationship. We also introduce a novel pre-processing technique using fuzzy logic that can group genes having similar changes in expression profile over all available intervals in the microarray data. This technique eliminates redundant computation performed by the proposed model. Saccharomyces cerevisiae data was applied to the model and 548 activator/repressor regulatory triplets were inferred from the data. These improvements will increase feasibility of using fuzzy logic for understanding the relationship between genes using microarray technology.

The analysis of high-throughput experimental data, such as microarray gene expression data, is currently seen as a promising way of finding regulatory relationships between genes. Network inference algorithms are powerful computational tools for identifying putative causal interactions among variables from observed data. In this paper, we propose a network reconstruction technique to predict not only the structure but also the direction and sign of regulation using a genetic algorithm (GA). The networks consisting of nodes (genes), directed edges (gene-gene interactions) and dynamics of regulation are assigned scores using the presented causal model based on partial correlation. The highest scoring network best fits the expression data. As GAs are stochastic, the algorithm is repeated several times and the final network is reconstructed by combining the most significant connections identified from the high scoring networks. The presented technique is applied to the well known Saccharomyces cerevisiae microarray dataset and the reconstructed network is observed to be consistent with the results found in literature

A population of sequences is called non-random if there is a statistical model and an associated compression algorithm that allows members of the population to be compressed, on average. Any available statistical model of a population should be incorporated into algorithms for alignment of the sequences and doing so changes the rank order of possible alignments in general. The model should also be used in deciding if a resulting approximate match between two sequences is significant or not. It is shown how to do this for two plausible interpretations involving pairs of sequences that might or might not be related. Efficient alignment algorithms are described for quite general statistical models of sequences. The new alignment algorithms are more sensitive to what might be termed 'features' of the sequences. A natural significance test is shown to he rarely fooled by apparent similarities between two sequences that are merely typical of all or most members of the population, even unrelated members.

The paper presents our language C++-with-Ease, a superset of C++ with primitives for process creation and communication. The work adopts the semantics of the Ease parallel primitives, as defined by S.E. Zenith (1990), within the object oriented paradigm. The result is a general purpose, high level, imperative parallel programming language that allows the simple expression of parallel algorithms within a type-safe implementation. Our language implementation is best suited to homogeneous parallel MIMD machines, independent of architecture, but also runs under threads packages. C++-with-Ease addresses efficiency for message copying and provides extensions to allow the passing of arbitrary messages in a natural fashion within the paradigm. The implementation and associated message protocols are discussed.

C-with-Ease is a superset of C, with primitives borrowed from Ease for process creation and communication. All communication is via distributed data structures called contexts. We present an efficient implementation of C-with-Ease for the Fujitsu AP1000, a distributed memory, message passing multiprocessor. We use two of the three AP1000 communication networks: the torus net for point to point communication and the broadcast net to maintain a global view of processor allocation.

Restriction site mapping programs construct maps by generating permutations of fragments and checking for consistency. Unfortunately many consistent maps often are obtained within the experimental error bounds, even though there is only one actual map. A particularly efficient algorithm is presented that aims to minimize error bounds between restriction sites. The method is generalized for linear and circular maps. The time complexity is derived and execution times are given for multiple enzymes and a range of error bounds.

Abstract Since the inception of pipes in the UNIX operating system, the standard UNIX command interpreters, or shells, have supported processes connected only in linear arrangements. This paper explains why linear pipe structures are too restrictive and how the standard UNIX shells have dictated the interface strategy of new commands. A new command interpreter is presented that supports general directed process graphs. Processes and files are considered simply as nodes and pipes as arcs in a process graph.