Ross D. King1,2, Andreas Karwath1, Amanda Clare1, Luc Dehaspe3

(1) Department of Computer Science, University of Wales, Aberystwyth, Penglais, Aberystwyth, Ceredigion, SY23 3DB, Wales, U.K.

(3) PharmaDM, Celestijnenlaan 200A, B-3001, Belgium

(2) Author to whom correspondence should be sent.

A. Einstein

This paper is a manifesto. It argues that:

• Science is experiencing an unprecedented "explosion" in the amount of available data.
• Traditional data analysis methods cannot deal with this increased quantity of data.
• There is therefore an urgent need to automate the process of refining scientific data into scientific knowledge.
• Inductive logic programming (ILP) is the data analysis framework best suited for this task.

We describe an example of using ILP to analyse a large and complex bioinformatic database which produced unexpected and interesting scientific results. We then point a possible way forward to integrating machine learning with scientific databases to form intelligent inductive databases.

Perhaps the most characteristic feature of science at the start of the third millennium is the "data explosion" (Reichart, 1999). From particle-physics to ecology, from neurology to astronomy, almost all the experimental sciences are experiencing an unprecedented increase in the amount and complexity of available data. Scientific databases with Terabytes (1012 bytes) of data are now common place, and soon Petabyte (1015bytes) database will be so. In some fields plans are already underway to deal with Exabytes (1018 bytes) and Yottabytes (1021 bytes) of data. To take a number of high profile cases:

• In physics, the new CERN Large Hadron Collider (LHC) is expected to generate ~100 Petabytes of data over its 15 year lifetime.
• In Geology, the US Geological survey is midway through photographing the entire US from the air at high resolution. This will form a ~12 Terabyte database.
• In Biology, transcriptome (microarray) data from gene knockouts of the human genome is expected to generate ~1 Petabyte of raw data - this data is also extremely complicated, as it has semantic links with many other biological databases.

These databases are made possible by increasingly sophisticated instrumentation, and by ever more powerful information technology. They represent a great achievement for science, and within them lies an abundance of new scientific knowledge. However, full analysis of such databases presents huge difficulties, and it is obvious that traditional approaches to scientific data analysis will not be sufficient. New more automated data analysis methods are essential to refine the vast quantities of scientific data into communicable scientific knowledge.

1.2 Scientific Discovery

The branch of Artificial Intelligence devoted to developing algorithms for acquiring scientific knowledge is known as "scientific discovery". Work has proceeded in this area for over thirty years and much has been achieved (e.g. Buchanan et al., 1969; Langley et al., 1987; Sleeman et al., 1989; Gordon et al., 1995; King et al., 1996; Valdes-Perez, 1999). However, the field has not made a significant impact on science generally. There have been no great scientific discoveries directly attributable to machine intelligence.

Why do scientific discovery programs not rival scientists in the way that the chess playing programs rival chess Grand masters? We believe the answer is that chess is an isolated world where, despite the almost limitless complications possible, everything that is relevant to the game is described in the rules. In contrast, scientific problems cannot be so easily isolated from general reasoning where human excel. To be successful scientific discovery programs do not need to know about everything - "Cabbages and Kings" (Boden, 1977); but they do need access to large amounts of background knowledge about the scientific field they are applied to. Humans still have the decisive edge over scientific discovery programs because scientific knowledge is difficult to encode, and we do not have a good theory of relevance. However, as the focus of science moves towards problems involving very large and complex datasets, the balance of advantage must shift towards machine intelligence.

We believe that first-order predicate logic should be the basis for representing knowledge in scientific discovery programs as it has the best understood semantics and inference mechanisms (Russell & Norvig, 1995). Propositional logic is too weak to be generally used on scientific problems: it cannot represent much of our background knowledge about scientific problems, nor can it represent scientific theories in the concise way scientists expect. Similarly, we consider that it is computationally intractable to learn scientific theories in higher-order, temporal logics etc., especially when large databases are involved (however, see Bowers et al., 2000).

Machine learning and data mining methods that employ first-order predicate logic to represent background knowledge and theories come from the field of Inductive Logic Programming (ILP) (Muggleton, 1990; Muggleton, 1992; Lavrac & Dzeroski, 1994). ILP is a relatively new and highly promising branch of machine intelligence. ILP has shown its value in many scientific problems in chemistry (e.g. King, et al., 1992; King, et al., 1996; Dehaspe, et al., 1998; Helma et al., 1998; Finn et al., 1998; King & Srinivasan, 1999; Dzeroski et al., 1999) and molecular biology (Muggleton, et al., 1992; King, et al., 1994; Sternberg et al., 1994; Turcotte et al., 2000) where it has found solutions not accessible to standard statistical, neural network, or genetic algorithms. The theories produced by ILP have also been generally more comprehensible than those using propositional methods.

In this second part of this paper we describe an example application of ILP to an important problem in functional genomics which illustrates how machine intelligence can be used to glean scientific knowledge from a large database.

Molecular Biology is currently experiencing a data explosion. The sequencing of the first draft of the 3 billion bases of human genome is now complete (http://www.sanger.ac.uk/HGP/), and the genomes of around 20 micro-organisms have now been completely sequenced (http://www-fp.mcs.anl.gov/~gaasterland/ genome.html; Blattner, F. R. et al., 1997; Cole, et al., 1998; Goffeau, et al. 1996) as have those of the multicellular animals Caenorhabditis elegans (C. elegans Sequencing Consortium, 1998) and Drosophila melanogaster (Adams et al. (2000). The data from these sequencing projects is revolutionising biology. Perhaps the most important discovery from the sequenced genomes is that the functions of only 40-60% of the predicted genes are known with any confidence. For example in Saccharomyces cerevisiae, one of the most intensely studied organisms, of the ~6,000 predicted protein-encoding genes (Goffeau, et al. 1996), the function of only ~60% can be assigned with any confidence. The new science of functional genomics (Hieter & Boguski, 1997; Bussey, 1997; Bork et al., 1998; Brent, 1999; Kell & King, 2000) is dedicated to determining the function of the genes of unassigned function, and to further detailing the function of genes with purported function.

Functional genomics needs better ways of being able to accurately predict a newly sequenced protein’s function from its sequence. Currently this is done by using sequence similarity methods to find a similar (homologous) protein in the database that has a labelled function (Pearson & Lipman, 1988; Altschul, et al., 1997). The function of the new sequence is then inferred to be the same as the homologous protein as it has been conserved over evolution. It is a kind of nearest-neighbour type inference (in sequence space).

We have developed a complementary approach to sequence similarity methods for predicting a protein’s function from sequence (King, et al., 2000). This approach is based on learning symbolic rules to predict a protein’s functional class. To test this approach we selected the Mycobacterium tuberculosis genome. This bacteria is the causative agent of tuberculosis which kills ~2 million people each year, and concern about the growing epidemic has led the World Health Organisation to declare tuberculosis a global emergency http://www.who.int/inf-fs/en/fact104.html. The genome of M. tuberculosis has been recently sequenced and has over 4 million base pairs, and 3,924 identified genes (Cole, et al., 1998). After sequencing the genome was annotated and a database of proteins of identified function formed http://www.sanger.ac.uk/Projects/M_tuberculosis/gene_list_full.shtm (15/03/1999). This database contains details of all the proteins in M. tuberculosis of known function from experiment, as well as those with predicted function from sequence similarity searches. These assignments of function were organised in a strict hierarchy, where each higher level in the tree is more general than the level below it, and the leaf nodes are the individual functions of proteins - this is typical of current genome annotation. A subsection of the function hierarchy is shown in Figure 1. A typical protein in the genome is L-fuculose phosphate aldolase (Rv0727c fucA), its top-level class assignment is "Small-molecule metabolism", its second-level class is "Degradation", and its third-level class is "Carbon compounds". (Note that there are errors in annotation of function (Brenner, 1999), and proteins may have more than one function which adds "noise" to the assignments). The organisation of functions into classes allows generalisation of the sequences over these classes using machine learning.

To describe the sequences for generalisation we first formed a datalog database (Ullman, 1988) containing all the data we could find on these sequences. The most commonly used technique to gain information about a sequence is to run a sequence similarity search, and this was used as the starting point in forming descriptions. The basic data structure in the deductive database is the result of a PSI-BLAST sequence similarity search (Altschul, et al., 1997). For each protein in the genome we formed an expressive description based on: the frequency of singlets and pairs of residues in the protein; the phylogeny ("family tree") of the organism from which each homologous protein was obtained - from SWISS-PROT (Bairoch A. & Apweiler (2000) (a standard protein database); SWISS-PROT protein keywords from homologous proteins; the length and molecular weight of the protein; and its predicted secondary structure (Ouali & King, 2000). In total 5,895,649 datalog facts were generated. Such a database is clearly too large to analyse manually.

We used the ILP data mining program Warmr (Dehaspe, et al., 1998) to identify frequent patterns (conjunctive queries) in the database. Warmr is a general purpose data mining algorithm that can discover knowledge in structured data, where patterns reflect the one-to-many and many-to-many relationships of several tables. This is not possible with standard data mining programs. Warmr uses the efficient levelwise method known from the Apriori algorithm (Fayyad, et al., 1996). This allows it to be used on very large databases. The Warmr levelwise search algorithm (Mannila & Toivonen, 1997) is based on a breadth-first search of the pattern space. This space is ordered by the generality of patterns. The levelwise method searches this space one level at a time, starting from the most general patterns. The method iterates between candidate generation and candidate evaluation phases: in candidate generation, the lattice structure is used for pruning non-frequent patterns from the next level; in the candidate evaluation phase, frequencies of candidates are computed with respect to the database. Pruning is based on the monotonicity of specificity with respect to frequency - if a pattern is not frequent then none of its specialisation can be frequent. The application of Warmr can be considered as a way of identifying the most important structure in a database. In the M. tuberculosis database Warmr discovered ~18,000 frequent queries. These frequent patterns were converted into 18,000 Boolean (indicator) attributes for propositional rule learning, where an attribute gets value 1 for a specific gene if the corresponding query succeeds for that gene, and 0 if the query fails. The propositional machine learning algorithms C4.5 and C5 (Quinlan, 1993) were used to induce rules that predict function from these attributes. Good rules were selected on a validation set, and the unbiased accuracy of these rules estimated on a test set. Rules were selected to balance accuracy with unidentified gene coverage. The prediction rules were then applied to genes that have not been assigned a function to predict their functions.

It was possible to find good rules that predict function from sequence at all levels of the functional hierarchies, as shown in Table 1. The test accuracy of these rules is far higher than possible by chance. Of the genes originally of unassigned function class, the rules predicted 985 (65%) to have a function at one or more levels of the hierarchy. The rule learning data, the rules, and the predictions, are given at: http://www.aber.ac.uk/~dcswww/Research/bio/ProteinFunction/. We illustrate the value of the rules by describing rule TB_C50_1_26 shown in Figure 2.

The most important scientific result of this work was the unexpected discovery that it was possible to predict a protein’s function in the absence of homology to a protein of known function. To demonstrate this we carried out all-against-all sequence similarity searches using PSI-BLAST for those proteins correctly predicted by each rule. If all the proteins could be linked together by PSI-BLAST e-values < 10 (a very liberal definition) then the proteins were considered homologous. It was found that many of the predictive rules were more general than possible using sequence homology. Rules were found to correctly predict the function of sets of proteins that are not homologous to each other in the test set, and to correctly predict the function of proteins that are not homologous to any in the training data (Table 1). We speculate that such rules are caused by convergent evolution causing forcing proteins with similar function to resemble each other, or horizontal evolution has transferred functional related groups of protein into the organisms.

We are working on extending our work on M. tuberculosis by developing an intelligent database (ID) for its functional genomics data. The ID will be designed to add scientific value to the underlying data. The rough design of the ID is given in Figure 3. The database will:

To populate the database, data will be collected through our existing research links to the functional genomics projects for M. tuberculosis, and from primary bioinformatic databases. The basic data will be stored in a standard relational database management system. The background biological knowledge necessary for deduction will be stored in a connected module with the deduction engine. One important element that is missing from the use of logic programs to represent scientific knowledge is a way of representing uncertainty (Russell & Norvig, 1995). How best to do this is unclear, but we favour Bayesian probabilistic methods. Probability theory is often considered to be grounded on propositional logic (Jaynes, 1994), and until recently little work has been done combing logic programs with probabilities. However, there has been a recent upsurge of research in this area (e.g. Muggleton, 2000; Kersting & DeRaedt, 2000).

Induction will be carried out using conventional (propositional) data mining and Inductive Logic Programming (ILP). The ILP data mining will be connected with the background knowledge and deductive engine. A small section of the planned structure of data and background knowledge of ID is shown in Figure 4. The results of the induction will be stored with the basic data in the relational database - as in an inductive database (Mannila, 1997). The ID will be made accessible to the Scientific community using a variety of standard methods, including Web Browsers, ODBC, XML, CORBA, etc.

The aim of the Intelligent Database is to directly integrate scientific databases and scientific discovery tools to provide scientists with a tool which can help automate science. We believe that such Intelligent Databases are essential to analyse the large amounts of new scientific data that is being generated and to refine this data into scientific knowledge.

We would like to thank Ugis Sarkans of the EBI and Nigel Hardy of the Department of Computer Science, University of Wales, Aberystwyth.

Level 1 Level 3 Level 4

Number of rules found 25 20 3

Rules predicting more than one homology class 19 8 1

Average test accuracy 62% 62% 76%

Table 1 The number of rules found are those selected on the validation set. A rule predicts more than one homology class if there is more than one sequence similarity cluster in the correct test predictions. A rule predicts a new homology class if there is a sequence similarity cluster in the test predictions that has no members in the training data. Average test accuracy is the accuracy of the predictions on the test proteins of assigned function (if conflicts occur, the prediction with the highest a priori probability is chosen). Default test accuracy is the accuracy that could be achieved by always selecting the most populous class. "New functions assigned" is the number of ORFs of unassigned function predicted.

Figure 1. An example subset of the genes functional hierarchy in M. tuberculosis. The gene L-fuculose phosphate aldolase is in the Level 3 class "carbon compounds". This example has only three out of four possible classification levels.

If

Figure 2. This top-level rule is 85% (11/13) accurate on the test set (the probability of this result occurring by chance is estimated at 1.2x10-5 as the class Macromolecule metabolism covers ~25% of examples). The rule correctly predicts the following proteins (rpsG (S7), rpsI (S9), rpsL (S12), rpsT (S20), rplJ (L10), rplP (L16), rplS (L19), rplX (L24), rpmE (L31), rpmJ (L36), infC (IF-3)). These proteins are all involved in protein translation. When the training data are included the rule covers 46 out of the 58 proteins known to be involved in ribosomal protein synthesis and modification. The rule predicts the function of fifteen genes of unknown function. It is also consistent with protein chemistry, as lysine is positively charged which is desirable for interaction with negatively charged RNA. The choice of lysine over arginine for the positively charged residue may be connected with the high GC content of the M. tuberculosis genome - lysine is coded by the codons AAA and AAG; while arg is coded by CGU, CGC, CGA, CGG; and his by CAT and CAC.

Figure 3. Design of the proposed Intelligent Database

Figure 4. Description of part of background knowledge in M. tuberculosis intelligent database.