15680189
Feature construction with Inductive Logic Programming: A Study of Quantitative Predictions of Biological Activity Aided by Structural Attributes
Recently, computer programs developed within the field of Inductive Logic Programming (ILP) have received some attention for their ability to construct restricted first-order logic solutions using problem-specific background knowledge. Prominent applications of such programs have been concerned with determining “structure-activity” relationships in the areas of molecular biology and chemistry. Typically the task here is to predict the “activity” of a compound (for example, toxicity), from its chemical structure. A summary of the research in the area is: (a) ILP programs have largely been restricted to qualitative predictions of activity (“high”, “low” etc.); (b) When appropriate attributes are available, ILP programs have equivalent predictivity to standard quantitative analysis techniques like linear regression. However ILP programs usually perform better when such attributes are unavailable; and (c) By using structural information as background knowledge, an ILP program can provide comprehensible explanations for biological activity. This paper examines the use of ILP programs as a method of “discovering” new attributes. These attributes could then be used by methods like linear regression, thus allowing for quantitative predictions while retaining the ability to use structural information as background knowledge. Using structure-activity tasks as a test-bed, the utility of ILP programs in constructing new features was evaluated by examining the prediction of biological activity using linear regression, with and without the aid of ILP learnt logical attributes. In three out of the five data sets examined the addition of ILP attributes produced statistically better results. In addition six important structural features that have escaped the attention of the expert chemists were discovered. The method used here to construct new attributes is not specific to the problem of predicting biological activity, and the results obtained suggest a wider role for ILP programs in aiding the process of scientific discovery.
6269772
PM - protein music
We present the program PM for the analysis of protein sequence information using audification. Audification is the technique of using the sense of hearing to analyse data (Jackson, 1993). The advantage of audification over visualisation in data analysis is that sound has the property that when different notes are played together they can still be individually heard: in vision colours blend to form new colours. This distinction can be very useful when studying multivariate data. The one dimensional structure of DNA maps naturally onto musical sequences (Hayashi and Munakata, 1984; Ohno and Ohno, 1986). The mapping algorithm in PM is designed to translate coding sequences into sound in a way that is more harmonious and more open to analysis than previous methods. The PM algorithm uses the DNA nucleotide sequence to form the musical top line, and the properties of the translated amino-acids to form the bass line. The notes are in the scale of C Major and there are three beats to the bar. Each codon corresponds to a bar of music and the notes are played on the beat in order of nucleotide sequence. The mapping of the top line to musical notes is as follows: A4 submediant E3 mediant C3 tonic G3 dominant The mapping of the bass line to notes is more complicated and is based on the designation of aminoacid physico-chemical properties of Taylor (1983). Each of the properties has a note assigned to it. The mapping is as follows: polar hydrophobic charged positive aliphatic aromatic tiny
13898721
An Automated ILP Server in the Field of Bioinformatics
The identification of evolutionary related (homologous) proteins is a key problem in molecular biology. Here we present a inductive logic programming based method, Homology Induction (HI), which acts as a filter for existing sequence similarity searches to improve their performance in the detection of remote protein homologies. HI performs a PSI-BLAST search to generate positive, negative, and uncertain examples, and collects descriptions of these examples. It then learns rules to discriminate the positive and negative examples. The rules are used to filter the uncertain examples in the "twilight zone". HI uses a multitable database of 51,430,710 pre-fabricated facts from a variety of biological sources, and the inductive logic programming system Aleph to induce rules. Hi was tested on an independent set of protein sequences with equal or less than 40 per cent sequence similarity (PDB40D). ROC analysis is performed showing that HI can significantly improve existing similarity searches. The method is automated and can be used via a web/mail interface.
9141928
Quantitative structure-activity relationships by neural networks and inductive logic programming. II. The inhibition of dihydrofolate reductase by triazines
SummaryOne of the largest available data sets for developing a quantitative structure-activity relationship (QSAR) — the inhibition of dihydrofolate reductase (DHFR) by 2,4-diamino-6,6-dimethyl-5-phenyl-dihydrotriazine derivatives — has been used for a sixfold cross-validation trial of neural networks, inductive logic programming (ILP) and linear regression. No statistically significant difference was found between the predictive capabilities of the methods. However, the representation of molecules by attributes, which is integral to the ILP approach, provides understandable rules about drug-receptor interactions.
18628984
Quantitative structure-activity relationships by neural networks and inductive logic programming. I. The inhibition of dihydrofolate reductase by pyrimidines
SummaryNeural networks and inductive logic programming (ILP) have been compared to linear regression for modelling the QSAR of the inhibition of E. coli dihydrofolate reductase (DHFR) by 2,4-diamino-5-(substitured benzyl)pyrimidines, and, in the subsequent paper [Hirst, J.D., King, R.D. and Sternberg, M.J.E., J. Comput.-Aided Mol. Design, 8 (1994) 421], the inhibition of rodent DHFR by 2,4-diamino-6,6-dimethyl-5-phenyl-dihydrotriazines. Cross-validation trials provide a statistically rigorous assessment of the predictive capabilities of the methods, with training and testing data selected randomly and all the methods developed using identical training data. For the ILP analysis, molecules are represented by attributes other than Hansch parameters. Neural networks and ILP perform better than linear regression using the attribute representation, but the difference is not statistically significant. The major benefit from the ILP analysis is the formulation of understandable rules relating the activity of the inhibitors to their chemical structure.
594009
An Assessment of ILP-Assisted Models for Toxicology and the PTE-3 Experiment
The Predictive Toxicology Evaluation (or PTE) Challenge provided Machine Learning techniques with the opportunity to compete against specialised techniques for toxicology prediction. Toxicity models that used findings from ILP programs have performed creditably in the PTE-2 experiment proposed under this challenge. We report here on an assessment of such models along scales of: (1) quantitative performance, in comparison to models developed with expert collaboration; and (2) potential explanatory value for toxicology. Results appear to suggest the following: (a) across of range of class distributions and error costs, some explicit models constructed with ILP-assistance appear closer to optimal than most expert-assisted ones. Given the paucity of test-data, this is to be interpreted cautiously; (b) a combined use of propositional and ILP techniques appears to yield models that contain unusual combinations of structural and biological features; and (c) significant effort was required to interpret the output, strongly indicating the need to invest greater effort in transforming the output into a "toxicologist-friendly" form. Based on the lessons learnt from these results, we propose a new predictive toxicology evaluation experiment - PTE-3 - which will address some important shortcomings of the previous study.
16104731
A Dichotomic Search Algorithm for Mining and Learning in Domain-Specific Logics
Many application domains make use of specific data structures such as sequences and graphs to represent knowledge. These data structures are ill-fitted to the standard representations used in machine learning and data-mining algorithms: propositional representations are not expressive enough, and first order ones are not efficient enough. In order to efficiently represent and reason on these data structures, and the complex patterns that are related to them, we use domain-specific logics. We show these logics can be built by the composition of logical components that model elementary data structures. The standard strategies of top-down and bottom-up search are ill-suited to some of these logics, and lack flexibility. We therefore introduce a dichotomic search strategy, that is analogous to a dichotomic search in an ordered array. We prove this provides more flexibility in the search, while retaining completeness and non-redundancy. We present a novel algorithm for learning using domain specific logics and dichotomic search, and analyse its complexity. We also describe two applications which illustrates the search for motifs in sequences; where these motifs have arbitrary length and length-constrained gaps. In the first application sequences represent the trains of the East-West challenge; in the second application they represent the secondary structure of Yeast proteins for the discrimination of their biological functions.
15579646
BLID: An Application of Logical Information Systems to Bioinformatics
BLID (Bio-Logical Intelligent Database) is a bioinformatic system designed to help biologists extract new knowledge from raw genome data by providing high-level facilities for both data browsing and analysis. We describe BLID’s novel data browsing system which is based on the idea of Logical Information Systems. This enables combined querying and navigation of data in BLID (extracted from public bioinformatic repositories). The browsing language is a logic especially designed for bioinformatics. It currently includes sequence motifs, taxonomies, and macromolecule structures, and it is designed to be easily extensible, as it is composed of reusable components. Navigation is tightly combined with this logic, and assists users in browsing a genome through a form of human-computer dialog.
15503339
Generating data integration mediators that use materialization
This paper presents a framework for data integration that is based on using “Squirrel integration mediators” that use materialization to support integrated views over multiple databases. These mediators generalize techniques from active databases to provide incremental propagation of updates to the materialized views. A framework based on “View Decomposition Plans” for optimizing the support of materialized integrated views is introduced. The paper describes the Squirrel mediator generator currently under development, which can generate the mediators based on high-level specifications.The integration of information by Squirrel mediators is expressed primarily through an extended version of a standard query language, that can refer to data from multiple information sources. In addition to materializing an integrated view of data, these mediators can monitor conditions that span multiple sources. The Squirrel framework also provides efficient support for the problem of “object matching”, that is, determining when object representations (e.g., OIDs) in different databases correspond to the same object-in-the-world, even if a universal key is not available.To establish a context for the research, the paper presents a taxonomy that surveys a broad variety of approaches to supporting and maintaining integrated views.
7168849
Constraint-based hypertext for argumentation
In this paper we describe a hypertext system we are developing for the support of reasoned argumentation: the EUCLID project. We use the project to address two general problems arising with hypertext: the problems of controlling user/document interaction, and the problem of controlling the screen. We suggest that guiding users' interaction with hypertext is difficult because of the unique form of discourse that hypertext represents, and that structuring user/document interaction can be achieved through specializing to a particular type of material and designing the hypertext system to respect the particular discourse structure characteristic of that material. EUCLID's design is tuned to the structure of reasoned discourse. The problem of screen management in EUCLID is a serious one, because our presentation of complex arguments requires mapping the complex logical relations between parts of realistic arguments onto complex spatial relations between items in the display. We describe a general system we are developing which provides this high degree of control for hypertext screen management. This system represents a constraint-based approach to hypertext, in which the items from the underlying database that are to be displayed may each contribute a number of constraints on the layout; a general constraint-satisfier then computes a screen layout that simultaneously satisfies these constraints. Each time an item is to be added to or deleted from the screen, the constraint set is adjusted and the screen layout is recomputed; thus the spatial relationships on the screen provide at all times a veridical representation of the underlying relations between displayed database items. This kind of strong screen control is demanded by hypertext applications which, like ours, are fine grained: the number of nodes and links being displayed number in the hundreds.
17042004
Case study on statistically estimating minimum makespan for flow line scheduling problems
Abstract Lower bounds are typically used to evaluate the performance of heuristics for solving combinatorial minimization problems. In the absence of tight analytical lower bounds, optimal objective-function values may be estimated statistically. In this paper, extreme value theory is used to construct confidence-interval estimates of the minimum makespan achievable when scheduling nonsimilar groups of jobs on a two-stage flow line. Experimental results based on randomly sampled solutions to each of 180 randomly generated test problems revealed that (i) least-squares parameter estimators outperformed standard analytical estimators for the Weibull approximation to the distribution of the sample minimum makespan; (ii) to evaluate each Weibull fit reliably, both the Anderson–Darling and Kolmogorov–Smirnov goodness-of-fit tests should be used; and (iii) applying a local improvement procedure to a large sample of randomly generated initial solutions improved the probability that the resulting Weibull fit yielded a confidence interval covering the minimum makespan.