3022268
Feature selection for genetic sequence classification
MOTIVATION
Most of the existing methods for genetic sequence classification are based on a computer search for homologies in nucleotide or amino acid sequences. The standard sequence alignment programs scale very poorly as the number of sequences increases or the degree of sequence identity is <30%. Some new computationally inexpensive methods based on nucleotide or amino acid compositional analysis have been proposed, but prediction results are still unsatisfactory and depend on the features chosen to represent the sequences.


RESULTS
In this paper, a feature selection method based on the Gamma (or near-neighbour) test is proposed. If there is a continuous or smooth map from feature space to the classification target values, the Gamma test gives an estimate for the mean-squared error of the classification, despite the fact that one has no a priori knowledge of the smooth mapping. We can search a large space of possible feature combinations for a combination which gives a smallest estimated mean-squared error using a genetic algorithm. The method was used for feature selection and classification of the large subunits of rRNA according to RDP (Ribosomal Database Project) phylogenetic classes. The sequences were represented by dinucleotide frequency distribution. The nearest-neighbour criterion has been used to estimate the predictive accuracy of the classification based on the selected features. For examples discussed, we found that the classification according to the first nearest neighbour is correct for 80% of the test samples. If we consider the set of the 10 nearest neighbours, then 94% of the test samples are classified correctly.


AVAILABILITY
The principal novel component of this method is the Gamma test and this can be downloaded compiled for Unix Sun 4, Windows 95 and MS-DOS from http://www.cs.cf.ac.uk/ec/


CONTACT
s.margetts@cs.cf.ac.uk
9554976
Evolutionary Divide and Conquer (I): A Novel Genetic Approach to the TSP
Experiments with genetic algorithms using permutation operators applied to the traveling salesman problem (TSP) tend to suggest that these algorithms fail in two respects when applied to very large problems: they scale rather poorly as the number of cities n increases, and the solution quality degrades rapidly. We propose an alternative approach for genetic algorithms applied to hard combinatoric search which we call Evolutionary Divide and Conquer (EDAC). This method has potential for any search problem in which knowledge of good solutions for subproblems can be exploited to improve the solution of the problem itself. The idea is to use the genetic algorithm to explore the space of problem subdivisions rather than the space of solutions themselves. We give some preliminary results of this method applied to the geometric TSP.
14169547
Non-linear modelling and chaotic neural networks
Proposes a simple methodology to construct an iterative neural network which mimics a given chaotic time series. The methodology uses the Gamma test to identify a suitable (possibly irregular) embedding of the chaotic time series from which a one step predictive model may be constructed. This model is then iterated to produce a close approximation to the original chaotic dynamics. Having constructed such networks we show how the chaotic dynamics may be stabilised using time-delayed feedback, which is a plausible method for stabilisation in biological neural systems. Using delayed feedback control, which is activated in the presence of a stimulus, such networks can behave as an associative memory, in which the act of recognition corresponds to stabilisation onto an unstable periodic orbit. We briefly illustrate how two identical dynamically independent copies of such a chaotic iterative network may be synchronised using the delayed feedback method. Although less biologically plausible, these techniques may have interesting applications in secure communications.
11348191
A note on the Gamma test
This note describes a simple technique, the Gamma (or Near Neighbour) test, which in many cases can be used to considerably simplify the design process of constructing a smooth data model such as a neural network. The Gamma test is a data analysis routine, that (in an optimal implementation) runs in time O(MlogM)as M→∞,where Mis the number of sample data points, and which aims to estimate the best Mean Squared Error (MSError) that can be achieved by any continuous or smooth (bounded first partial derivatives) data model constructed using the data.
6839309
Five 1951 BBC broadcasts on automatic calculating machines
In May and June 1951, five leading figures of British computing - Douglas Hartree, Max Newman, Alan Turing, Frederic ("Freddie") Williams, and Maurice Wilkes - spoke about their work on BBC radio. We examine surviving texts of their broadcasts, and the speakers' principal points are summarized through quotations and commentary. The broadcasts are placed in the context of contemporary developments in computing and the particular BBC service on which they were broadcast.
207571365
An APL Approach to Presentation Graphics
Producing data in pictorial form is a type of computer graphics application known as presentation graphics. One approach that has been used for this type of graphics is a graphic support package using APL as the command language. Here discussed is the evolution of this approach up to its currently available forms.
4157117
Data Access and Integration in the ISPIDER Proteomics Grid
Grid computing has great potential for supporting the integration of complex, fast changing biological data repositories to enable distributed data analysis. One scenario where Grid computing has such potential is provided by proteomics resources which are rapidly being developed with the emergence of affordable, reliable methods to study the proteome. The protein identifications arising from these methods derive from multiple repositories which need to be integrated to enable uniform access to them. A number of technologies exist which enable these resources to be accessed in a Grid environment, but the independent development of these resources means that significant data integration challenges, such as heterogeneity and schema evolution, have to be met. This paper presents an architecture which supports the combined use of Grid data access (OGSA-DAI), Grid distributed querying (OGSA-DQP) and data integration (AutoMed) software tools to support distributed data analysis. We discuss the application of this architecture for the integration of several autonomous proteomics data resources.
9096556
A language extension for expressing constraints on data access
Controlled sharing of information is needed and desirable for many applications and is supported in operating systems by access control mechanisms. This paper shows how to extend programming languages to provide controlled sharing. The extension permits expression of access constraints on shared data. Access constraints can apply both to simple objects, and to objects that are components of larger objects, such as bank account records in a bank's data base. The constraints are stated declaratively, and can be enforced by static checking similar to type checking. The approach can be used to extend any strongly-typed language, but is particularly suitable for extending languages that support the notion of abstract data types.
206840293
Formal Specification of Security Requirements using the Theory of Normative Positions
We use a number of the examples presented in [Ting 1990] to illustrate how the formal theory of normative positions may serve as a tool for clarifying, and making precise, the specification of security requirements, particularly in regard to access control. We describe the basic features of the theory of normative positions (which has its roots in the analytical theory of law), and of the modal logics (deontic and action logics) involved in its formulation. We then indicate three levels of software we have under development, which aim to turn the analytical procedures into a practical tool. Our concluding remarks relate our discussion of Ting's examples to some particular issues in the formal specification of computer systems.