Quan i a i e Pha macopho e Models wi h
Induc i e Logic P og amming
Ashwin S ini asan1, Da id Page2, Rui Camacho3, and Ross D. King4
1IBM India Resea ch Lab, Block 1, Indian Ins i u e o Technology, New Delhi.
2Depa men o Bios a is ics, Uni e si y o Madison, Wisconsin.
3LIACC - CIUP, R. Campo Aleg e, 4150 Po o, Po ugal.
4Depa men o Compu e Science, Uni e si y o Wales, Abe ys wy h.
Abs ac . Th ee-dimensional models, o pha macopho es, desc ibing
Euclidean cons ain s on he loca ion on small molecules o unc ional
g oups (like hyd ophobic g oups, hyd ogen accep o s and dono s, e c.),
a e o en used in d ug design o desc ibe he medicinal ac i i y o po en-
ial d ugs (o ‘ligands’). This medicinal ac i i y is p oduced by in e ac-
ion o he unc ional g oups on he ligand wi h a binding si e on a a ge
p o ein. In iden i ying s uc u e-ac i i y ela ions o his kind he e a e
h ee p incipal issues: (1) I is o en di icul o “align” he ligands in
o de o iden i y common s uc u al p ope ies ha may be esponsi-
ble o ac i i y; (2) Ligands in solu ion can adop di e en shapes (o
‘con o ma ions’) a ising om o sional o a ions abou bonds. The 3-D
molecula subs uc u e is ypically sough on one o mo e low-ene gy con-
o me s; and (3) Pha macopho e models mus , ideally, p edic medicinal
ac i i y on some quan i a i e scale. I has been shown ha he logical
ep esen a ion adop ed by Induc i e Logic P og amming (ILP) na u ally
esol es many o he di icul ies associa ed wi h he alignmen and mul i-
con o ma ion issues. Howe e , he p edic ions o models cons uc ed by
ILP ha e hi he o only been nominal, p edic ing medicinal ac i i y o
be p esen o absen . In his pape , we in es iga e he cons uc ion o
wo kinds o quan i a i e pha macopho ic models wi h ILP: (a) Models
ha p edic he p obabili y ha a ligand is “ac i e”; and (b) Models
ha p edic he ac ual medicinal ac i i y o a ligand. Quan i a i e p e-
dic ions a e ob ained by he u ilising he ollowing s a is ical p ocedu es
as backg ound knowledge: logis ic eg ession and nai e Bayes, o p ob-
abili y p edic ion; linea and ke nel eg ession, o ac i i y p edic ion.
The mul i-con o ma ion issue and, mo e gene ally, he ela ional ep-
esen a ion used by ILP esul s in some special di icul ies in he use
o any s a is ical p ocedu e. We p esen he p incipal issues and some
solu ions. Speci ically, using da a on he inhibi ion o he p o ease The -
molysin, we demons a e ha i is possible o an ILP p og am o con-
s uc good quan i a i e s uc u e-ac i i y models. We also commen on
he ela ionship o his wo k o o he ecen de elopmen s in s a is ical
ela ional lea ning.
1 In oduc ion
The p ima y goal o he pha maceu ical indus y is o ind, de elop and ma ke
new d ugs o p e iously un ea able diseases o which ha e be e p ope ies
han exis ing d ugs. The de elopmen o a new d ug is a ime-consuming, ex-
pensi e p ocess—i can ake anywhe e om 12 o 16 yea s om he s a o a
esea ch p og am o inal app o al; and he cos can be up o US$700 million.
I is clea ly o signi ican humani a ian and comme cial in e es o in es iga e
echniques and ools ha can assis in making he p ocess mo e e icien .
Mos d ugs molecules wo k by binding o “ a ge si es”—commonly p o eins—
wi hin he body. By in e ac ion wi h hese a ge s, d ugs can modula e hei ac-
ions. The p ocess o d ug de elopmen begins wi h he selec ing an app op ia e
a ge wi h which he d ug could in e ac o modula e disease. In some cases, he
de ailed s uc u e o he a ge binding si e is known (by he use o X- ay c ys-
allog aphic echniques) o can be guessed (by s uc u e p edic ion echniques
o om he s uc u e o simila molecules); bu his si ua ion is s ill a e and
he iden i ica ion o po en ial d ugs has o p oceed wi hou his knowledge.
Chemis y o d ug de elopmen (see Fig. 1) is conce ned wi h he iden i-
ica ion o “ligands”: small molecules ha a e po en ial d ugs. The sea ch o
ligands commences wi h some compounds ha a e known o in e ac wi h he
a ge . These compounds, o “leads”, may be iden i ied in a numbe o ways, o
example om la ge scale empi ical es ing o a ailable chemicals. They will ha e
some ac i i y, i.e. abili y o in e ac wi h he a ge , bu may do so only weakly,
and may possess o he undesi able p ope ies, o example me abolic ins abili y.
Once a se o leads ha e been isola ed, hei chemical s uc u e can be e ined
o imp o e biological ac i i y and educe side e ec s. A compu a ional ac i i y
ha assis s his is conce ned wi h cons uc ing models ha ela e ac i i y o
molecula s uc u e. These “s uc u e-ac i i y ela ionships”, o SARs, desc ibe
how he s uc u al di e ences o a se o leads a ec s hei ac i i y, and can be
used o sugges new molecules o make which should ha e enhanced ac i i y.
Chemical syn hesis and es ing o such molecules leads o he disco e y o mo e
ac i e molecules un il, ul ima ely, ligands o he desi ed ac i i y and p ope ies
a e disco e ed. These compounds now begin he long p ocess o de elopmen
including biological ials o e icacy, sa e y ials, o mula ion and ad anced
es ing, pa en de elopmen and inally, applica ion o clinical ials.
The whole p ocess is c i ically dependen on e ec i e ini ial chemis y: p o-
posal o a la ge numbe o ligands o de elopmen and es ing, mos o which
u n ou o be useless is clea ly o be a oided. In his, good SAR models can
play an impo an ole. “T adi ional” SAR me hods (“1-D” and “2-D” me hods
in Fig. 1), gene a e many ea u es o each lead (e ec i ely, a o m o domain-
speci ic p oposi ionalisa ion) and use s a is ical modelling ools on he esul ing,
able con aining he ea u e- alues o a se o leads and hei ac i i y. The ea-
u es, o molecula desc ip o s, can be p ope ies o he whole molecule, such as
pa i ion coe icien , molecula olume, numbe o ings, e c., and, i he se ies
o leads sha e a common co e, p ope ies o he subs uc u es a he posi ions
o a ia ion The modelling ask is o cons uc a p edic i e model ha ela es
Chemis y Pha macology, Sa e y e c.Resea ch
Compounds
Syn hesise
Ge
Leads
Po en ial Ac i i y
P edic
P o ein o inhibi
Choose
Ta ge
Biological
T ials
‘‘G id’’−based
S uc u e−Ac i i y
Rela ionships
(SARs)
1−D 2−D 3−D
Ta ge −Ligand
Models
Ligand−only
Models
Models Pha macopho e
Models
Quali a i e Quan i i e
Fig. 1. A simpli ied iew o he chemis y in ol ed in he d ug-design p ocess (adap ed
om a igu e kindly p o ided by D . S ua G een, Uni e si y o Leeds). The ocus o
his pape is shown in bold- ace.
ea u e- alues o ac i i y. Such models ha e been widely applied, and he e a e
many examples o success ul SAR analyses [12]. The e a e ou p incipal di icul-
ies wi h his app oach. Fi s , much depends on he abili y o iden i y molecula
desc ip o s ha e ain all he in o ma ion necessa y o ob aining a good model.
Second, cons uc ing eliable models is no easy. The molecula desc ip o s can
numbe in o se e al millions, and special ca e mus be aken a oid chance co e-
la ions. Thi d, he models a e no always easy o use in e ining leads. I is easy
o calcula e he alue o a molecula desc ip o o a gi en lead ( o example,
an elec onic pa ial cha ge), bu qui e a di e en ma e o design a molecule
ha will possess ha alue. Finally, by dealing wi h bulk molecula p ope ies,
a he han a mo e explici ep esen a ion o he molecules, no accoun is aken
o he h ee-dimensional shape o he leads.
Leads, being small molecules a e lexible and can adop di e en shapes (con-
o ma ions) by o sional o a ions abou bonds wi hin he molecule. Molecules
apidly con e om one con o ma ion o ano he , so ha no single con o ma-
ion can be isola ed and es ed o a gi en ac i i y. Hence in gene al one does
no know a p io i which con o ma ion o a molecule is an ac i e con o ma ion
o a gi en o m o ac i i y. Compu a ional chemis s usually employ one o wo
app oaches o his p oblem. In he i s , he shape and elec os a ic in e ac ions
a e deal wi h ia a calcula ed in e ac ion wi h a “p obe” a om o g oup a
poin s on a h ee-dimensional g id which su ounds he molecules. S a is ical
me hods a e hen used o iden i y hose pa s o he molecule which a e espon-
sible o ac i i y. The analysis can be displayed g aphically o aid in he design
o new molecules. The majo disad an age wi h his app oach is ha , in o de
o compa e alues a he calcula ed poin s be ween molecules, he con o ma ion
o he molecules, and a common coo dina e ame, o alignmen , mus be chosen
in ad ance o he analysis. This is equi alen o deciding on he manne in which
he molecules in e ac wi h he a ge . I he molecules con ain a la ge common
s uc u al elemen his alignmen may be s aigh o wa d, bu his is o en no
he case.
The second app oach uses a ep esen a ion o biological ac i i y called a
pha macopho e. This is an abs ac ion o he molecula s uc u e o he, usu-
ally, small numbe o key ea u es which con ibu e he majo i y o he ac i i y,
oge he wi h hei geome ic a angemen ep esen ed by pai wise dis ances (see
Fig. 2, om [8]). An ad an age o he pha macopho e ep esen a ion is ha i
exp esses biological ac i i y in a language ha is amilia o chemis s wi hin he
pha maceu ical indus y. These ep esen a ions a e also eadily con e ible in o
sea ch que ies o compound da abases, which is an e ec i e means o iden i ying
addi ional ac i e molecules [9].
Tha Induc i e Logic P og amming (ILP) is pa icula ly well-sui ed o ep-
esen and disco e SARs has been a gued pe suasi ely elsewhe e [8, 20]. The
mos impo an easons gi en a e: (i) he comp ehensibili y o he models con-
s uc ed allow an easy ansla ion o he models in o new chemical s uc u es;
(ii) ILP p og ams do no need o align he leads o a common spa ial e e ence
ame; and (iii) he i s -o de ep esen a ion used by ILP na u ally deals wi h
d1
d2 d3
Ta ge
Lead
Fig. 2. A schema ic diag am o how a “pha macopho e” de ini ion ( igh ) is ela ed
o a lead- a ge in e ac ion ( om [8]). The pha macopho e con ains he key unc ional
in e ac ions and he geome ic ela ionships be ween hem exp essed as dis ances d1,
d2, and d3. Fo example, he unc ional g oups may be a hyd ogen dono and wo
hyd ogen accep o s; d1 migh be 4.5 Angs oms, d2 migh be 5.0 Angs oms, and d3
migh be 3.75 Angs oms.
di icul ies a ising om he ac ha he leads may assume se e al shapes (o
con o ma ions), no all o which may be esponsible o he biological ac i i y.
Non- ela ional lea ning algo i hms— hose ha need a ea u e ec o ep esen-
ion o da a— equi e modi ica ion o handle poin iii. Fu he mo e, gi en e en
jus wo shapes o each molecule, hese app oaches ei he equi e wo s -case
exponen ial ime (in he numbe o molecules) o pe o m he alignmen men-
ioned in poin ii, o mus a imes wo k wi h an inco ec alignmen —one in
which he pa s o he molecules esponsible o in e ac ion a e no aligned wi h
each o he . Rega ding poin i, comp ehensibili y, he mos complex SARs ound
by ILP using only he s uc u es o leads and hei ac i i ies a e pha macopho e
models in he o m o ules like he ollowing:
Molecule M is “ac i e” i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen accep o a posi ion P2 and
M has a hyd ogen accep o a posi ion P3 and
he dis ance be ween P1 and P2 is 4 ±1˚
A and
he dis ance be ween P1 and P3 is 3 ±1˚
A and
he dis ance be ween P2 and P3 is 5 ±1˚
A.
He e, posi ions P1, P2, and P3 a e poin s in 3-dimensional space and he ule
ep esen s a “3-poin pha macopho e”. The ule, e iden ly simple o unde s and,
ne e heless highligh s an impo an sho coming o SARs cons uc ed by ILP:
hey a e classi ica o y in na u e and unable o quan i y hei p edic ions o ac-

i i y1. In his pape , we in es iga e iden i ica ion by ILP o wo kinds o quan-
i a i e SARs, namely, class-p obabili y models o he o m:
The p obabili y o molecule M being “ac i e” is P i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen accep o a posi ion P2 and
M has a hyd ogen accep o a posi ion P3 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and
he dis ance be ween P2 and P3 is X3 and
P is he p obabili y o being “ac i e” gi en X1, X2, X3.
and eg ession models o he o m:
The a ini y o molecule M is A i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen accep o a posi ion P2 and
M has a hyd ogen accep o a posi ion P3 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and
he dis ance be ween P2 and P3 is X3 and
A is he expec ed a ini y gi en X1, X2, X3.
We will call hese “quan i a i e pha macopho e models”: speci ically, he ules
abo e a e 3-poin quan i a i e pha macopho e models. The eason o in e es
in he eg ession model is e iden : when accu a e quan i a i e in o ma ion o
lead-ac i i y is a ailable, SARs ha ela e lead-s uc u e o ac i i y a e mos
use ul. E en when we only ha e ca ego ic in o ma ion abou he lead-ac i i y
( o example, leads a e “ac i e” o “inac i e”), class-p obabili y models can s ill
be ex emely use ul o he easons below:
– Inhe en unce ain ies in he domain may make ca ego ic classi ica ion di i-
cul . Fo example, da a may be labo a o y measu emen s ob ained om an
imp ecise assay;
– Applica ions in ol ing decision-making o en equi e p obabili y es ima es
o use in cos /bene i calcula ions. Fo example, a syn hesis o a pa icula
molecule may p oceed only i he e was a e y high p obabili y o i being
biologically ac i e;
– I may be impo an o ank al e na i es wi h a gi en class alue. Fo ex-
ample, labo a o y cons ain s may equi e syn hesis o molecules o p oceed
in small ba ches. An o de ing on molecules p edic ed o be ac i e is hen
needed.
1These classi ica o y ules ha e been used o cons uc boolean ea u es, which ha e
hen be used by eg ession echniques o build quan i a i e models o ac i i y [21,
37]. We a e conce ned he e wi h cons uc ing quan i a i e models solely wi h he
use o ILP.
In his pape , bo h he geome ic cons ain s and he “nume ic” cons ain in
he ules abo e ( ha is, compu ing P o A gi en X1, X2 and X3) a e o be
ob ained du ing hypo hesis cons uc ion by an ILP p og am. I is ou in en ion
o in es iga e he use o s a is ical p ocedu es as backg ound knowledge o
ob aining he nume ic cons ain . The ollowing ques ions—no el o bo h ILP
and s a is ical me hods—a ise o ules abo e:
Model Iden i ica ion. Molecule M may ha e se e al hyd ogen dono s and ac-
cep o s, a di e en posi ions, esul ing in di e en se s o alues o X1, X2
and X32. The no el y o ILP is ha he domain dic a es only one o hese
se s is ele an o iden i ying he he app op ia e nume ic cons ain . Which
one?
P edic ion. Each se o alues o X1, X2 and X3 esul s in a p edic ion o
P o A. Which o hese alues should be e u ned3? This ques ion has no
a isen p e iously in ei he ILP o s a is ical me hods.
These wo asks a e unlike hose con on ed by a s a is ician du ing no mal
discou se. The e i is common, due o andom a ia ion, o ob ain di e en
a ini y alues o epea ed measu emen s o he same alues o X1, X2 and X3.
Machine lea ning esea che s will ecognise he ques ions he e as consequences
o a mul iple-ins ance ep esen a ion [6]. No el he e, howe e , is he eal- alued
p edic ion ask in a mul iple-ins ance se ing. While his combina ion has been
add essed be o e, in wo pape s [32, 1], as discussed in he nex pa ag aph an
adequa e solu ion o model iden i ica ion and p edic ion in his se ing has no
been ound. And he combina ion o eal- alued p edic ion in a mul iple-ins ance
se ing has no been add essed explici ly be o e in ILP, al hough he pape by
Ray and Page [32] poin ed o i s impo ance.
The app oaches p oposed in he wo pape s al eady men ioned pe o med
well on model iden i ica ion om syn he ic da a. No e ha model iden i ica ion
is easy o assess on syn he ic da a, whe e he da a gene a o can eco d he
model i used o gene a e he eal- alued esponse o each da a poin . Model
iden i ica ion is di icul o impossible o assess on eal-wo ld da a, whe e one
sees only he esponse alue and no he co ec model, o se o bindings o
a iables. Hence one mus ely on p edic ion o assess pe o mance on mos eal-
wo ld asks. The app oaches in he wo pape s ha e no been demons a ed o
pe o m well on eal-wo ld asks, such as p edic ing quan i a i e d ug ac i i y
alues.
The p esen pape p esen s p ocedu es o add ess bo h model iden i ica ion
and p edic ion, and i es s hese p ocedu es on eal-wo ld da a o quan i a i e
d ug ac i i y p edic ion. Fo illus a i e pu poses, we will use linea eg ession as
2The logic p og amme will ecognise his as di e en subs i u ion-se s a ising om
a non-de e mina e de ini ion o he dono and accep o p edica es.
3We could conside using some ep esen a i e se o alues o dis ances ( o example,
he a e age) o bo h model iden i ica ion and p edic ion. Howe e , wha his ep-
esen a i e should be may no be appa en and in any case, will equi e a di e en
ule o he ones shown.
a backg ound p edica e o pe o m quan i a i e p edic ion, al hough he p oce-
du es p oposed a e no es ic ed o ha pa icula modelling echnique (as will
be demons a ed in Sec ion 6.1). The pape is o ganised as ollows. In Sec ion
2 we p esen a simple example o illus a e he p incipal issues. Sec ion 3 in-
oduces ele an e minology om he li e a u e on mul iple-ins ance lea ning.
“Solu ions” o he p oblems ha a ise du ing model iden i ica ion and p edic ion
a e in Sec ions 4 and 5 espec i ely. Applica ion o he p ocedu es de eloped o
quan i a i e s uc u e-ac i i y ela ions is in Sec ion 6. Sec ion 7 concludes he
pape . The pape is accompanied by wo appendices. Appendix A desc ibes he
s a is ical p ocedu es used in he empi ical s udy. Appendix B ela es he wo k
in Sec ion 6.1 o o he , mo e gene al, wo k on inco po a ing p obabili ies in ILP
and ela ional lea ning gene ally.
2 An Example
Conside lea ning he ollowing simple 1-poin quan i a i e pha macopho e model
using an ILP sys em:
The a ini y o molecule M is Y i :
M has a hyd ogen dono a posi ion X and
Y = mX + c.
He e “Y = mX + c” is a s a is ical model in which mand ca e pa ame e s
o be es ima ed and Suppose da a a ailable a e as ollows: (1) a ini y alues
o 5 di e en molecules; and (2) eco ds o hyd ogen dono loca ions on each
molecule (a molecule can ha e mo e han one dono ). The da a a e abula ed in
Fig. 3. Logically speaking, he ule abo e s a es ha he a ini y o he molecule
is a linea unc ion o one o he hyd ogen dono posi ions (wi hou speci ying
which one: he logician will ecognise his as a consequence o he a iable X
being exis en ially quan i ied wi hin he ule body).
Since o each N, i is no appa en which o he X alues a e o be pai ed wi h
he co esponding Y, a combina o ial p oblem a ises4. Fo his simple p oblem,
he combina o ics a e manageable: he e a e only 3×1×2×1×2 = 12 di e en
ables con aining exac ly 1 en y o each o he 5 alues o X. Two such ables
a e shown in Fig 4.
Pa ame e es ima es can now be ob ained using each such able. The es i-
ma es e u ned a e hose ha esul in he bes i ing model. Fo he da a in
Fig 4, he bes i ing model Y = 2.572 X - 33.155 is ob ained wi h he able in
Fig 5. The esul ing ule is he e o e:
The a ini y o molecule M is Y i :
M has a hyd ogen dono a posi ion X and
Y = 2.572 X - 33.155.
4Some heo e ical esul s known o mul iple-ins ance lea ning can be ound in [7].
Mol (M) A . (Y) Dono (X)
25
1 50 33
29
2 100 50
3 150 73
75
4 200 90
5 250 120
110
Fig. 3. “T aining” da a o he p oblem o p edic ing a ini y Y using hyd ogen dono
loca ion X. Fo a gi en alue o N, i is known ha he alue o Y depends on one o
X alues—bu i is no known which one.
Mol (N) A . (Y) Dono (X) Mol (N) A . (Y) Dono (X)
1 50 25 1 50 33
2 100 50 2 100 50
3 150 73 3 150 75
4 200 90 4 200 90
5 250 120 5 250 110
Fig. 4. Example ables ob ained by combina o ial enume a ion o he da a in Fig. 3.
The able on he le yields he model Y = 2.161 X - 4.739, wi h sample co ela ion coe -
icien 0.997. The one on he igh yields Y = 2.565 X - 33.677, wi h sample co ela ion
coe icien 0.998.
Sec ion 4 desc ibes p ocedu es ha equips an ILP sys em o each such a model
(o a leas , an app oxima ion o i ) gi en he da a in Fig 3.
Now conside using his ule on he da a shown in Fig. 6. I is e iden ha
simply execu ing he ule abo e will yield wo p edic ions: Y = 188.037 (using
X = 86) and Y = 203.469 (using X = 92). Which o hese p edic ions should be
e u ned is he p oblem posed by (Q2). In Sec ion 5, we examine some solu ions
o his p oblem.
3 Te minology
I is con enien a his poin o in oduce some e minology om he machine
lea ning li e a u e on mul iple ins ance lea ning. The ollowing s a emen o he
mul i-ins ance lea ning ask is la gely om [32]. Da a consis s o a se o nbags
(1 ≤n < ∞). The i h bag consis s o miins ances (1 ≤mi<∞) and a label
yi(which may be nominal o eal- alued). Ins ance jo bag iis desc ibed by a
d-dimensional ec o o alues (1 ≤d < ∞). The ask is o cons uc a model
6 Quan i a i e Pha macopho e Models o The molysin
Inhibi ion
Ou es -bed o he cons uc ion o quan i a i e pha macopho e is he inhibi-
ion o The molysin. The molysin is a zinc-con aining p o ease ha consis s o
wo sphe ical domains sepa a ed by a deep cle ha cons i u es he ac i e si e.
Zinc-con aining p o eases like The molysin play an impo an ole in physiolog-
ical p ocesses like diges ion and blood p essu e egula ion. Da a on a numbe
o inhibi o s o The molysin a e eadily a ailable in he li e a u e: we use he
molecules s udied by [21]. The da a consis o c ys al s uc u es and co espond-
ing ac i i y alues (pKi = -logKi) o 31 inhibi o s.
All expe imen s use he ILP sys em Aleph [35] (speci ically, Aleph Ve sion
4). The expe imen s we e pe o med on machine equipped wi h wo 512 Mhz
Pen ium III p ocesso s wi h 128 megaby es o andom access memo y. We ollow
he wo k o [8] in p o iding he ILP sys em wi h backg ound knowledge o he
ollowing:
–Compound-speci ic knowledge. This is in he o m o he a om and bond
s uc u e o each compound, as well as i s 3-dimensional con o ma ion ( o
each o he h ee lowes ene gy con o me s iden i ied by [21]). This in o ma-
ion is ep esen ed by i s -o de a omic o mulae: we e e he eade o [8]
o examples o his encoding.
–Gene al chemical and geome ic knowledge. Gene ic chemical knowledge p o-
ided is in he o m o a lib a y o elemen a y chemical concep s ( o example
de ini ions o hyd ogen dono s, hyd ogen accep o s, hyd ophobic g oups, es-
e s, e he s, e c.). We ha e p o ided he same concep s as hose in [21] ( he
au ho s he e ha e used 39 such concep s). The only geome ic knowledge
needed o his ask is a p ocedu e o calcula ing he Euclidean dis ance
be ween wo poin s.
Addi ional backg ound knowledge equi ed o he cons uc ion o class-p obabili y
and eg ession models will be desc ibed below.
6.1 Class-p obabili y models
I is ou goal in his sec ion o demons a e ha an ILP sys em capable o using
he p ocedu e in Fig. 7 and s a is ical p ocedu es o condi ional p obabili y es-
ima ion can cons uc class-p obabili y models o s uc u e-ac i i y p edic ion.
Recall ha hese models we e o he o m:
The p obabili y o molecule M being ac i e is P i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen accep o a posi ion P2 and
M has a hyd ogen accep o a posi ion P3 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and

he dis ance be ween P2 and P3 is X3 and
P is he p obabili y o being ac i e gi en X1, X2, X3
Candida e s a is ical p ocedu es o compu ing P conside ed a e logis ic eg es-
sion and “nai e” Bayes (see Sec ion A.1). The easons o selec ing hese ech-
niques a e:
–They a e simple;
–The e is abundan suppo o hei use in class p obabili y es ima ion, bo h
in he s a is ical and machine lea ning li e a u e (see o example, [29]).
In addi ion, i can be shown ha he logis ic unc ion is he app op ia e
Bayesian choice unde some ai ly gene al condi ions (see [17]); and
–They can be seen as special cases o mo e gene al wo k on combining Bayesian
ne wo ks and ILP (see Appendix B).
Da a O he 31 The molysin inhibi o s a ailable, we ha e designa ed he op
15 inhibi o s o be be “ac i e” and he emaining 16 inhibi o s o be “inac-
i e”. In o de o build class-p obabili y models, he ac ual examples a e o he
o m “p obabili y o molecule mbeing ac i e is p”, whe e pis one o 1.0 o 0.0
(depending on whe he mis ac i e o inac i e).
Addi ional backg ound knowledge In addi ion o he backg ound in o ma-
ion desc ibed ea lie we also include he ollowing:
–Cons ain s on legi ima e models. Legi ima e models a e equi ed o con-
ain unc ional g oups, pai wise dis ances be ween he g oups and a nume ic
cons ain ha p edic s he p obabili y o being ac i e.
–Model iden i ica ion. This de ini ion implemen s he p ocedu e desc ibed in
Fig. 7. The ac ual model cons uc ion wi hin his p ocedu e is done by one
o logis ic eg ession o nai e Bayes.
Me hod Ou me hod is s aigh o wa d. Using backg ound de ini ions o logis-
ic eg ession o nai e Bayes:
1. Cons uc he “bes ” class-p obabili y model o he la ges pha macopho e
possible o he inhibi o s.
2. Es ima e he pe o mance o he model ob ained in he p e ious s ep.
The ollowing de ails a e ele an :
(a) Looking o he la ges pha macopho e model o a se o ac i e molecules
is a cha ac e is ic o his kind o domain (see [8] o mo e de ails). Models
can be seen as con aining wo so s o cons ain s: i s , hose in he “p e-
ix”, consis ing o he unc ional g oups and hei pai wise dis ances ( he
pha macopho e pe se); and second, he nume ic cons ain ha p edic s
p obabili ies using he dis ances be ween hese unc ional g oups. In S ep
(1) we es ic models o be a single clauses. This is simila o [8] and o e s
he mos comp ehensible models o ac i i y). Fu he , he sea ch o his
model is done in 2 s eps:(i) he la ges p e ixes common o all inhibi o s a e
ound; and (ii) each p e ix is ex ended o include he nume ic cons ain . Fo
he The molysin da a, he la ges pha macopho e models con ain 4-poin
pha macopho es ( ha is, he e is no single clause 5-poin pha macopho e
model ha can be used o explain he ac i i y o all o he 31 inhibi o s).
The sea ch p ocedu e in Fig. 7 sea ches o he “bes ” nume ic cons ain by
minimising a loss- unc ion. He e we will use a s anda d quad a ic loss unc-
ion (sum o squa ed di e ences be ween ac ual and p edic ed p obabili ies)
summed o e all aining ins ances.
(b) In S ep (2) pe o mance es ima es will be es ima ed using a lea e-one-ou
p ocedu e. Tha is, each inhibi o is, in u n, ca ego ised as a “ es ” ins ance.
A class-p obabili y model is cons uc ed using he emaining ins ances and
hen used o p edic he p obabili y o he es ins ance being ac i e. The
non-de e mina e na u e o he domain will esul in a se o p edic ions
o he p obabili y. We ha e elec ed o selec he highes o hese as he
inal p edic ion (as desc ibed in Sec ion 5.2). This is a easonable choice
o he domain conside ed, as we a e in e es ed in he bes chance o a
molecule being able o inhibi The molysin (i he se o p edic ions is emp y,
hen he es ins ance is no included in es ima ing he pe o mance). The
pe o mance is summa ised by an ROC cu e, ob ained by changing he
h eshold p obabili y abo e which he es ins ance is o be classi ied as
being ac i e ( o example, i his h eshold is 0.3, and he model p edic s
he p obabili y o he es ins ance being ac i e as being 0.2, hen he es
ins ance is classi ied as being inac i e).
Resul s Figu e 10 shows ROC cu es gene a ed by changing h eshold p ob-
abili ies in he manne desc ibed abo e. The cu es a e, in ac , he con ex
hull o he poin s deno ing classi ica o y models ob ained om he co espond-
ing class-p obabili y models (i has been shown elsewhe e [31] ha he con ex
hull con ains he op imal classi ie s unde some e y gene al decision- heo e ic
condi ions).
The cu es clea ly show how we can ob ain highe posi i e p edic ion a es
a he expense o an inc eased alse-posi i e a e: ob aining a se o models wi h
such p ope ies is s aigh o wa d once we ha e class-p obabili y models. Fo
alse-posi i e a es abo e 0.2, he ROC cu e ob ained wi h nai e Bayes dom-
ina es ha wi h he logis ic eg ession. Tha is, as long as a alse ala m a e
o a leas 20% is ole able, he use o nai e Bayes as a backg ound p edica e
esul s in be e p edic i e pe o mance. O he wise, he use o logis ic eg ession
yields a be e model. The posi ion is mo e clea -cu on he comp ehensibili y
on : he use o logis ic eg ession esul s in a simple equa ion o p edic ing
p obabili y. In con as , he when using he nai e Bayes p ocedu e, p obabili ies
a e ke nel-densi y es ima es ob ained om he aining ins ances. This makes
he co esponding ule e u ned by he ILP p og am signi ican ly ha de o un-
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
T ue Posi i e Ra e
False Posi i e Ra e
NBayes
Logis ic
Random
Fig. 10. ROC cu es o The molysin Inhibi ion. “NBayes” is he cu e ob ained using
a nai e Bayesian p ocedu e o p obabili y es ima ion. “Logis ic” is he co esponding
cu e using logis ic eg ession as backg ound knowledge. “Random” is he pe o mance
o a classi ie ha assigns class- alues using a coin oss.
de s and. Example ules ob ained wi h logis ic eg ession and nai e Bayes a e
shown in Figu es 11 and 12.
6.2 Reg ession models
The s uc u e-ac i i y ela ions cons uc ed so a do no include p edic ions o
ac ual binding a ini ies. This is usually ha de and in his sec ion we demon-
s a e ha an ILP sys em capable o using he p ocedu e in Fig. 7 and ap-
p op ia e s a is ical p ocedu es o condi ional mean es ima ion can cons uc
a eg ession model ha p edic s binding a ini ies. Recall ha an example is a
ule o he o m:
The a ini y o molecule M is A i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen accep o a posi ion P2 and
The p obabili y o molecule M being “ac i e” is P i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen dono a posi ion P2 and
M has a hyd ogen dono a posi ion P3 and
M has a hyd ogen dono a posi ion P4 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and
he dis ance be ween P1 and P4 is X3 and
he dis ance be ween P2 and P3 is X4 and
he dis ance be ween P2 and P4 is X5 and
he dis ance be ween P3 and P4 is X6 and
P = 1
1+e−87.5+16.1X1−6.4X2+0.1X3−36.3X4+43.8X5−80.1X6
Fig. 11. An example o a class-p obabili y model ob ained wi h he use o logis ic
eg ession. The eg ession p ocedu e compu es he numbe s in he equa ion o P.
M has a hyd ogen accep o a posi ion P3 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and
he dis ance be ween P2 and P3 is X3 and
A is he expec ed a ini y gi en X1, X2, X3
Once again ou choice o s a is ical p ocedu es—linea and ke nel eg ession (see
Sec ion A.2)—is p ima ly based on simplici y and p e alance o use.
Da a Da a consis s o he 31 The molysin inhibi o s along wi h hei ac i i y
(pKi) alues. Examples a e hus o he o m “ he a ini y o molecule mis y”
whe e yis some loa ing-poin numbe .
Addi ional backg ound knowledge In addi ion o he backg ound in o ma-
ion desc ibed ea lie we also include he ollowing:
–Cons ain s on legi ima e models. Legi ima e models a e equi ed o con-
ain unc ional g oups, pai wise dis ances be ween he g oups and a nume ic
cons ain ha p edic s he a ini y.
–Model iden i ica ion. This de ini ion implemen s he p ocedu e desc ibed in
Fig. 7. The ac ual model cons uc ion wi hin his p ocedu e is done by one
o linea o ke nel eg ession.
Me hod Ou me hod is simila o ha used o he cons uc ion o class-
p obabili y models. Tha is, using backg ound de ini ions o linea o ke nel
eg ession:
1. Cons uc he “bes ” eg ession model o he la ges pha macopho e possi-
ble o he inhibi o s.
The p obabili y o molecule M being “ac i e” is P i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen dono a posi ion P2 and
M has a nega i ely cha ged a om a posi ion P3 and
M has a nega i ely cha ged a om a posi ion P4 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and
he dis ance be ween P1 and P4 is X3 and
he dis ance be ween P2 and P3 is X4 and
he dis ance be ween P2 and P4 is X5 and
he dis ance be ween P3 and P4 is X6 and
P is he ke nel densi y es ima e using ins ances I
Whe e I is:
P X1 X2 X3 X4 X5 X6
0.0 5.6 2.2 4.3 4.5 2.2 4.1
0.0 5.3 2.2 4.8 5.7 2.2 5.3
... ... ... ... ... ... ...
... ... ... ... ... ... ...
... ... ... ... ... ... ...
Fig. 12. An example o a class-p obabili y model ob ained wi h he use o nai e Bayes.
The en ies in he abula ion a e he aining ins ances e u ned by he sea ch p ocedu e
in Fig. 7.
2. Es ima e he pe o mance o he model ob ained in he p e ious s ep.
The ollowing de ails a e ele an :
(a) Models will again con ain wo so s o cons ain s: i s , hose in he “p e-
ix”, consis ing o he unc ional g oups and hei pai wise dis ances ( he
pha macopho e pe se); and second, he nume ic cons ain ha p edic s
a ini y using he dis ances be ween hese unc ional g oups. As be o e, we
es ic models o be a single clause and he sea ch is done in 2 s eps:(i) he
la ges p e ixes common o all inhibi o s a e ound; and (ii) each p e ix is ex-
ended o include he nume ic cons ain . We use he s anda d quad a ic loss
unc ion (sum o squa ed di e ences be ween ac ual and p edic ed a ini ies)
summed o e all aining ins ances.
(b) Fo ke nel eg ession, we use he Epanechniko quad a ic ke nel [14] whose
window size is de e mined by he k h-nea es neighbou (wi h k= 3). These
choices a e a bi a y, al hough he Epanechniko ke nel has some op imali y
p ope ies ha a e desc ibed in [13].
(c) In S ep (2) pe o mance es ima es will be es ima ed using a lea e-one-ou
p ocedu e. Tha is, each inhibi o is, in u n, ca ego ised as a “ es ” ins ance.
A eg ession model is cons uc ed using he emaining ins ances and hen
used o p edic he a ini y o he es ins ance. The non-de e mina e na u e
o he domain will esul in a se o p edic ions o he a ini y. As wi h
class-p obabili y models, we ha e elec ed o selec he highes o hese as

he inal p edic ion (and as be o e, i he se o p edic ions is emp y, hen
he es ins ance is no included in es ima ing he pe o mance). Spea man’s
ank co ela ion coe icien ( CV ) be ween ac ual and p edic ed alues will
be aken o be ep esen a i e o he pe o mance o he model.
Resul s Figu e 13 shows he co ela ion coe icien s ob ained by he lea e-one-
ou p ocedu e desc ibed. Also abula ed a e he bes esul s ob ained wi h he
s anda d QSAR 3-D echnique CoMFA (compa a i e molecula ield analysis)
and a wo-s age app oach by King and colleagues ([21]).
Me hod CV
Linea 0.34
Ke nel 0.68
CoMFA 0.78
King 0.86
Fig. 13. Lea e-one-ou es ima es o he ank co ela ion be ween ac ual and p edic ed
alues o a ini y. “Linea ” and “Ke nel” s and o linea and ke nel eg ession espec-
i ely. “CoMFA” ep esen s he bes QSAR model ob ained wi h compa a i e molec-
ula ield analysis. “King” ep esen s he app oach desc ibed in [21].
The models ob ained wi h linea and ke nel eg ession a e no as good as
hose wi h CoMFA o King. This is no su p ising, gi en he models cons uc ed
he e—single clauses wi h a eg ession cons ain —a e e y simple (in con as ,
King uses a kind o o ing wi h mul iple pha macopho e models). Ne e heless,
he pe o mance using linea eg ession is pa icula ly poo , sugges ing ha he
assump ion o a linea model may be inapp op ia e. The e a e also good bio-
logical easons o belie e ha his may be he case: assuming an ideal binding
geome y, a ini y alues should dec ease as dis ances de ia e (on ei he side)
om he ideal dis ances be ween unc ional g oups. Quad a ic eg ession should
yield a be e model unde hese ci cums ances: his is con i med by an imp o ed
CV alue o 0.55. This is, o cou se, s ill well sho o he ma k achie ed by King:
some po ion o he blame appea s o lie in he selec ion ule used o ob ain a
inal p edic ion ( ha is, he highes alue o all p edic ions ob ained). Be e
co ela ion alues a e ob ainable, bu he selec ion ule is no e iden a p io i.
Example ules ob ained wi h linea and ke nel eg ession a e shown in Figu es
14 and 15.
7 Concluding Rema ks
The p ocess o de eloping a new d ug is long, labo ious and expensi e. A la ge
pa o he ime and e o goes in o he es ing and assesmen o compounds ha
The a ini y o molecule M is A i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen accep o a posi ion P2 and
M has a hyd ogen dono a posi ion P3 and
M has a nega i ely cha ged a om a posi ion P4 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and
he dis ance be ween P1 and P4 is X3 and
he dis ance be ween P2 and P3 is X4 and
he dis ance be ween P2 and P4 is X5 and
he dis ance be ween P3 and P4 is X6 and
A = 1.06 + 0.55 X1 - 0.63 X2 + 0.29 X3 - 0.26 X4 + 0.06 X5 + 0.91 X6.
Fig. 14. An example o a eg ession model ob ained wi h he use o linea eg ession.
The eg ession p ocedu e compu es he numbe s in he equa ion o A.
ul ima ely p o e unsui able as medica ions. Gi en a biological a ge o modu-
la e, he ole o chemis y is o iden i y he ini ial se o chemical compounds ha
can be aken o wa d o de elopmen . In his, s uc u e-ac i i y ela ionships
(SARs) can play an impo an ole in ensu ing ha a la ge p opo ion o he
compounds p oposed a e also e ec i e. In he pas , he ela ional ep esen a ion
used by ILP has been epea edly shown o be pa icula ly well-sui ed o he
ask o cons uc ing good SARs, wi h one ca ea : he ep esen a ion o ac i i y
has been a simple ca ego isa ion (usually “ac i e” o “inac i e”). In his pape ,
we ha e sough o ex end ILP-cons uc ed SARs o ue quan i a i e models
by u ilising some s anda d s a is ical p ocedu es as backg ound knowledge. In
doing so, we ha e had o con on some speci ic issues ha a ise du ing model
cons uc ion and p edic ion when using s a is ical p ocedu es wi hin a i s -o de
logic se ing. To add ess hese, we ha e p oposed an ILP sys em ha : (a) iden-
i ies s a is ical models in he SAR by employing he p ocedu e in Sec ion 4;
and (b) uses he esul ing SAR wi hin domain-independen o domain-speci ic
p ocedu es o ensu e de e minis ic p edic ion (as desc ibed in Sec ion 5).
The ob ious limi a ion o he p ocedu es p oposed he e is he lack o p o able
p ope ies, in pa icula , abou he op imali y o models cons uc ed. In he ab-
sence o such p ope ies, we ha e a emp ed o demons a e he p ac ical u ili y
o he p ocedu es using using da a on he inhibi ion o The molysin. To he bes
o ou knowledge, he esul s ep esen he i s examples o a cons uc ing uly
quan i a i e 3-dimensional SARs wi h ILP.
The li e a u e on a emp ing o inco po a e s a is ical models wi hin ILP
hypo heses is ela i ely spa se. Bo h [18] and [36] a e conce ned wi h he use
o linea eg ession by an ILP p og am (as a buil -in de ini ion in [18] and as
a backg ound p edica e in [36]). In he o me , he mul iple ins ance p oblem
is a oided by es ic ing backg ound p edica es ha in oduce he independen
a iables o be s ic ly de e minis ic ( ha is, unc ional). The la e simply ig-
The a ini y o molecule M is A i :
M has a hyd ogen dono a posi ion P1 and
M has a hyd ogen dono a posi ion P2 and
M has a nega i ely cha ged a om a posi ion P3 and
M has a nega i ely cha ged a om a posi ion P4 and
he dis ance be ween P1 and P2 is X1 and
he dis ance be ween P1 and P3 is X2 and
he dis ance be ween P1 and P4 is X3 and
he dis ance be ween P2 and P3 is X4 and
he dis ance be ween P2 and P4 is X5 and
he dis ance be ween P3 and P4 is X6 and
A is he ke nel eg ession es ima e using ins ances I
Whe e I is:
A X1 X2 X3 X4 X5 X6
3.3 3.7 2.2 5.5 2.9 2.3 4.2
7.5 6.6 6.8 4.7 12.0 10.0 4.6
... ... ... ... ... ... ...
... ... ... ... ... ... ...
... ... ... ... ... ... ...
Fig. 15. An example o a eg ession model ob ained wi h he use o ke nel eg ession.
The en ies in he abula ion a e he aining ins ances e u ned by he sea ch p ocedu e
in Fig. 7.
no es he mul i-ins ance p oblem and ea s all ins ances as independen da a
poin s. Adop ing he same app oach, Sla e y and C a en [4] examine he use
o a buil -in nai e Bayesian classi ie . To his ex en , he wo k he e appea s o
he i s o con on squa ely he p oblems o using s a is ical p ocedu es wi h
non-de e mina e backg ound knowledge. Mo e gene ally, he e is an inc easing
awa eness wi hin machine lea ning o he impo ance o lea ning s a is ical mod-
els om ela ional da a. In Appendix B, we place his wo k wi hin he con ex
o b oade e o s in he eme ging ield o s a is ical ela ional lea ning.
The echniques p esen ed a e no con ined o he pa icula s a is ical p o-
cedu es used, a pa icula ILP sys em, o o he cons uc ion o SARs. This
sugges s h ee in e es ing ways in which he wo k he e could be ex ended. Fi s ,
he use o o he condi ional es ima ion p ocedu es may yield be e SAR models
han hose ob ained he e. Second, he same echniques could be used o ex end
he capabili ies o o he quan i a i e ILP app oaches like hose ha cons uc
i s -o de eg ession ees. Thi d, and mos in e es ingly, he same p ocedu es
should p o ide any ILP sys em wi h he ools necessa y o cons uc complex
heo ies ha combine i s -o de and ‘p oposi ional’ aspec s. An example o his
a e he heo ies desc ibed in [34]. A.D. Shapi o’s wo k on s uc u ed induc ion
equi es expe assis ance o decompose hie a chically a complex induc ion ask
in o sub-p oblems ha can sol ed induc i ely (in Shapi o’s case, using a ee
lea ne ). While he app oach was shown on di icul chess endgames o yield
no el and comp ehensible heo ies, he need o p o ide a comple e decomposi-
ion o he ask has emained a p incipal di icul y wi h he echnique. I is o
in e es o see he ex en o which an ILP sys em can cons uc such heo ies au-
oma ically (equipped, o example, wi h a ee lea ne as backg ound knowledge
and app op ia e domain-speci ic cons ain s).
Acknowledgemen s
Much o his wo k was done when he i s au ho was a he Compu ing Labo a o y,
Ox o d. Thanks a e also due o S e e Moyle o se e al in e es ing discussions on
he echniques desc ibed he e and his gene ous compu a ional suppo ; o Na halie
Ma chand-Genes e o he da a on he The molysin inhibi o s; and o Ra i Ko ha i
o sugges ing he use o ke nel eg ession.
Re e ences
1. R.A. Ama , D.R. Dooly, S.A. Goldman, and Q. Zhang. Mul iple-Ins ance Lea ning
o Real-Valued Da a. In C.E. B odley and A.P. Danyluk, edi o s, P oceedings o
he Eigh een h In e na ional Con e ence on Machine Lea ning (ICML 2001), pages
3–10, San F ancisco, 2001. Mo gan Kau mann Publishe s.
2. W. Bun ine. Ope a ions o lea ning wi h g aphical models. Jou nal o A i icial
In elligence Resea ch, 2:159–225, 1994.
3. V. S. Cos a, D. Page, M. Qazi, and J. Cussens. CLP(BN): Cons ain Logic P o-
g amming o P obabilis ic Knowledge. In P oceedings o he Nine een h In e -
na ional Con e ence on Unce ain y in AI (UAI-2003), San F ancisco, CA, 2003.
Mo gan Kau mann. ( o appea ).
4. M. C a en and S. Sla e y. Rela ional Lea ning wi h S a is ical P edica e In en-
ion: Be e Models o Hype ex . Machine Lea ning, 43(1-2):97–119, 2001.
5. J. Cussens. S ochas ic logic p og ams: Sampling, in e ence and applica ions. In
P oceedings o he Six een h Annual Con e ence on Unce ain y in A i icial In el-
ligence (UAI-2000), pages 115–122, San F ancisco, CA, 2000. Mo gan Kau mann.
6. T. Die e ich, R. La h op, and T. Lo ano-Pe ez. Sol ing he mul iple-ins ance
p oblem wi h axis-pa allel ec anges. A i icial In elligence, 89:31–71, 1997.
7. D.R. Dooly, S.A. Goldman, and S.S. Kwek. Real-Valued Mul iple-Ins ance Lea n-
ing wi h Que ies. In N. Abe, R. Kha don, and T. Zeugmann, edi o s, P oceedings
o he Twel h Con e ence on Algo i hmic Lea ning Theo y (ALT 2001), olume
2225 o LNAI, pages 167–180, Be lin, 2001. Sp inge -Ve lag.
8. P. Finn, S. Muggle on, D. Page, and A. S ini asan. Pha macopho e Disco e y using
he Induc i e Logic P og amming sys em P ogol. Machine Lea ning, 30:241–270,
1998.
9. P.W. Finn. Compu e -based sc eening o compound da abases o he iden i ica ion
o no el leads. D ug Design Today, 1(9):363–370, 1996.
10. N. F iedman, L. Ge oo , D. Kolle , and A. P e e . Lea ning p obabilis ic ela ional
models. In P oceedings o he 16 h In e na ional Join Con e ence on A i icial
In elligence. S ockholm, Sweden, 1999.
11. L. Ge oo , N. F iedman, D. Kolle , and A. P e e . Lea ning p obabilis ic ela ional
models. In S. Dze oski and N. La ac, edi o s, Rela ional Da a Mining, pages 307–
335. Sp inge , Be lin, 2001.