Communications of the ACM

Communications of the ACM

Scientific Knowledge Discovery Using Inductive Logic Programming

By Stephen Muggleton
Communications of the ACM, November 1999, Vol. 42 No. 11, Pages 42-46
10.1145/319382.319390
Comments

Scientific knowledge discovery tasks can be carried out using inductive logic programming (ILP). The results I review here have been published in leading scientific journals and are among the strongest examples of semiautomated scientific discovery in the AI literature. Other discovery areas of ILP include linguistic features in natural language data and patterns in highway traffic data.

Meanwhile, the pharmaceutical industry is increasingly overwhelmed by large volumes of scientific data generated internally as a side effect of screening tests and combinatorial chemistry, and externally from such sources as the human genome project. On the other hand, the industry is predominantly knowledge-driven. For example, knowledge is needed in computational chemistry for pharmacophore identification, as well as for determining biological function using sequence analysis.

From a computer science point of view, the knowledge requirements in this industry give greater emphasis on "knowing that," or declarative or descriptive knowledge, than "knowing how," or procedural or prescriptive knowledge. Mathematical logic has always been the preferred representation for declarative knowledge; thus, knowledge discovery techniques are required for generating logical formulae from data. ILP provides such an approach [1, 5] .

ILP algorithms take examples E of a concept (such as a protein family) together with background knowledge B (such as a definition of molecular dynamics) and construct a hypothesis H that explains E in terms of B. For example, in the protein-fold domains, discussed later in the article, E might consist of descriptions of molecules separated into positive and negative examples of a particular fold (overall protein shape), as shown in Figure 1 for the fold known as "four-helical-up-and-down-bundle."

A possible hypothesis H describing this class of proteins is shown in Figure 2. The hypothesis is a definite clause consisting of a head (fold(..,..)) and a body (the conjunction length(..), .. helix(..)). In this case, "fold" is the predicate involved in the examples and hypothesis, while "length," "position," and other factors are defined by the background knowledge. A logic program is simply a set of such definite clauses. E, B, and H are each logic programs.

In the context of knowledge discovery, ILP's distinct advantage over such black-box techniques as neural networks is that a hypothesis, like the one in Figure 2, can be automatically translated into the following English text: "The protein P has fold class 'four-helical up-and-down bundle' if it contains a long helix H1 at a secondary structure position between 1 and 3, and H1 is followed by a second helix H2." Such explicit hypotheses can be used within the familiar human scientific discovery cycle of debate, criticism, refutation.

Back to Top

Discovery of Biological Functions

Biological functions are regulated by the docking of small molecules (called "ligands") with sites on large molecules (such as proteins). Drugs, such as beta-blockers, mimic natural small molecules, such as adrenaline. The effectiveness of drugs depends on the correct shape and charge distribution of their ligands. For example, because beta-blockers block the binding of adrenaline, they stop overstimulation of heart muscle in patients at high risk for having heart attacks.

Results on scientific discovery ILP applications are separated into those related to small molecules, including ligands, and those related to proteins.

Small molecules (structure-activity prediction). Most pharmaceutical research and development is based on finding slightly improved variants of patented active drugs; for example, 292 out of 348 drugs introduced in the U.S. from 1981 to 1988 were of this kind, rather than purely original designs. Finding slightly improved drug variants involves chemists synthesizing and testing hundreds of compounds almost at random. The average cost today of developing a single new drug is around $300 million. One study showed that the ILP system Golem was able to construct rules that accurately predict the activity of untried drugs. Rules were constructed from examples of drugs with known medicinal activity. The accuracy of the rules was found to be slightly better than traditional statistical methods. More important, the easily understandable rules provided insights directly comparable to the relevant literature concerning the known shape of pockets in the binding site of dihydrofolate reductase; inhibition of dihydrofolate reductase is the mechanism used by the antifolate drugs methotrexate and trimethoprin for treating a range of diseases, including many cancers, infections, rheumatoid arthritis, multiple sclerosis, and lupus.

Mutagenesis. The ILP learning system Progol [4] was used in a joint collaboration between a group at Imperial Cancer Research Fund in London and my group at Oxford University Computing Laboratory to predict the mutagenicity, or the capacity of a chemical agent to cause permanent alteration of the genetic material within a living cell, of chemical compounds taken from a previous study involving linear regression [3]. Progol's predictive accuracy was equivalent to regression on the main set of the study's 188 compounds and significantly higher (85.7%, as opposed to 66.7%) on 44 compounds that had been discarded by the previous authors as unpredictable using regression. Progol's single-clause solution for the 44 compounds was judged by the domain experts to be a new structural alert for mutagenesis.

---

The ability to incorporate background knowledge and reuse learned knowledge mark ILP as a particularly effective approach.

---

Pharmacophores. In a series of "blind tests" in collaboration with the pharmaceutical company Pfizer U.K., Progol was shown to be able to rediscover a 3D description of the binding sites (or pharmacophores) of ACE inhibitors (a hypertension drug) and an HIV-protease inhibitor (an anti-AIDS-virus drug) [2].

Carcinogenicity. In 1998, Oxford University Computing Laboratory entered Progol into a worldwide carcinogenicity prediction competition run by the National Toxicology Program, which was established in 1978 to coordinate toxicology research and testing in the U.S. National Institute of Environmental Sciences. Progol was trained on approximately 300 available compounds, on which it used rules relating to mutagenicity it had developed earlier. In the first round of the competition, Progol produced the highest predictive accuracy of any automatic system in the competition (see Figure 3).

Proteins (protein secondary structure prediction). In one study, Golem, an early ILP learning system, was applied to one of the most vexing unsolved problems in molecular biology. The problem is that given a sequence of amino acid residues, how can the placement of the main 3D substructures of the protein be predicted? This question is of great interest to pharmaceutical companies involved in drug design. For this reason, during the past 20 years, many attempts have sought to apply knowledge discovery methods to this problem, ranging from statistical regression to decision-tree to neural-net learning. Published accuracy results for the general prediction problem have ranged from 50% to 60%, very close to majority-class prediction rates. Our investigation of protein secondary structure prediction found that the ability to use background knowledge from molecular biology, together with the ability to describe structural relations, boosted the predictive accuracy on a restricted sub-problem to around 80% on an independently chosen test set.

Discovery of fold descriptions. Protein shape is described in the standard SCOP classification (see scop.mrc-lmb.cam.ac.uk/scop/) at various levels of abstraction. At the lower (more specific) levels, each family of proteins contains members with high sequence similarity. At the most abstract level, folds describe proteins with similar overall shape but that are quite different at the sequence level. The lack of understanding of shape determination has made protein fold prediction particularly difficult. However, it is intriguing that although there are approximately 300 known folds, about 50% of all known proteins are members of the 20 most populated folds.

In one experiment [7], Progol was applied to discover rules governing these 20 protein folds. Average in-class cross-validated prediction was about 70%, and many of the rules were judged to be good characterizations of the fold classes by Michael Sternberg, a protein structure prediction expert who heads the molecular modeling group at Imperial Cancer Research Fund.

Back to Top

Conclusion

In his 1994 published description of the importance of this line of research to the Royal Society, Sternberg emphasized joint human-computer collaboration in scientific discoveries [6]. He wrote: "There is an interactive cycle between human analysis and machine learning. Initially, traditional methods process the data and develop representations that characterize the system and rules describing the relationship between the components of the system. Next, machine learning uses these representations to identify new, and hopefully more powerful and incisive, rules. Then, human intervention is required for interpretation of the rules, and the cycle can be repeated." Clearly, science is an activity of human societies; computer-based scientific discovery should support strong integration into the existing social environment of human scientific communities. The knowledge discovered should add to and build on existing science. The ability to incorporate background knowledge and reuse learned knowledge, together with the coherence and lucidity of the hypotheses, have marked ILP as a particularly effective approach for scientific knowledge discovery.

Back to Top

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 1999 ACM, Inc.

---

No entries found