Link Mining for Kernel-based Compound-Protein
Interaction Predictions Using a Chemogenomics
Approach
Masahito Ohue1,2,3,4*, Takuro Yamazaki3, Tomohiro Ban4, and Yutaka Akiyama1,2,3,4*
1

Department of Computer Science, School of Computing,
Tokyo Institute of Technology, Japan
2Advanced Computational Drug Discovery Unit, Institute of Innovative Research,
Tokyo Institute of Technology, Japan
3Department of Computer Science, Faculty of Engineering,
Tokyo Institute of Technology, Japan
4Department of Computer Science, Graduate School of Information Science and Engineering,
Tokyo Institute of Technology, Japan
*ohue@c.titech.ac.jp, akiyama@c.titech.ac.jp

Abstract. Virtual screening (VS) is widely used during computational drug discovery to reduce costs. Chemogenomics-based virtual screening (CGBVS) can
be used to predict new compound-protein interactions (CPIs) from known CPI
network data using several methods, including machine learning and data mining. Although CGBVS facilitates highly efficient and accurate CPI prediction, it
has poor performance for prediction of new compounds for which CPIs are unknown. The pairwise kernel method (PKM) is a state-of-the-art CGBVS method
and shows high accuracy for prediction of new compounds. In this study, on the
basis of link mining, we improved the PKM by combining link indicator kernel
(LIK) and chemical similarity and evaluated the accuracy of these methods. The
proposed method obtained an average area under the precision-recall curve
(AUPR) value of 0.562, which was higher than that achieved by the conventional Gaussian interaction profile (GIP) method (0.425), and the calculation
time was only increased by a few percent.
Keywords: virtual screening; compound-protein interactions (CPIs); pairwise
kernel; link mining; link indicator kernels (LIKs)

1

Introduction

Virtual screening (VS), in which drug candidate compounds are selected by a
computational method, is one of the main processes in the early stages of drug discovery. There are three main approaches to VS: ligand-based VS (LBVS) [1] using
known activity information for the target protein of the drug; structure-based VS
(SBVS) [2] using structural information for the target protein of the drug; and

Link Mining for Kernel-based CGBVS

compound-protein
interaction network
N

2

interaction matrix
interaction profile

N

N
N

NH2
N

N

NH2

O

O
O

O

1

1

0

1

0

0

N

0

N
N

N

0

N

N

1

1

䈈

1

0

0

1

0
噣

N NH

N NH

噣

噣

噣

compound kernel
protein kernel
(similarity matrix) (similarity matrix)

compound kernel
(GIP/LIK)

protein kernel
(GIP/LIK)

Fig. 1. Schematic diagram of information used in CGBVS. Information on interaction matrices
and interaction profiles can be obtained from CPI data. Kernel matrices were obtained from the
relationship between the compounds and the proteins.

chemogenomics-based VS (CGBVS) [3] based on known interaction information for
multiple proteins and multiple compounds (also called drug-target interaction prediction). Both LBVS and CGBVS do not require a protein tertiary structure, and both
depend on statistical machine learning using known experimental activity data. However, CGBVS yields more robust prediction results by handling multiple types of
proteins. CGBVS has been well studied in recent years [4][5][6][7][8][9], and a review of CGBVS was recently published by Ding et al. [3].
In CGBVS, computations are mainly performed using a similarity matrix of proteins, a similarity matrix of compounds, and an interaction profile matrix composed of
binary values with and without interactions (Fig. 1).
The kernel method is often applied for prediction [5][6][7]. Conventionally, in
CGBVS, an interaction profile matrix is used only as labeled training data; however,
an increasing number of frameworks have recently been described that utilize interaction profile matrices as their main features. The Gaussian interaction profile (GIP) is
one of these frameworks [5]. In addition to information regarding similarity matrices,
GIP uses similarities between vectors when an interaction profile matrix is viewed as
vertical and horizontal vectors. The GIP kernel functions of proteins and compounds
are represented as follows (details are described in Section 2):
kGIP, c (c, cc)

exp J c v c  v cc

2

, kGIP, p ( p, p c)

exp J p v p  v pc

2

.

(1)

3

M. Ohue, T. Yamazaki, T. Ban, and Y. Akiyama

The problem with GIP kernels is that ‘0’ bit (interaction is unknown) is taken into
account, similarly to ‘1’ bit (interaction). Thus, kGIP shows a maximum value (which
is equivalent to two compounds with common interaction partners) for two novel
compounds when the interactions with all proteins are unknown. Since ‘0’ potentially
includes both no interactions and unknown interactions in general CGBVS problems
and benchmark datasets, information for ‘1’ should be considered more reliable.
In this way, as a framework that mainly considers ‘1’ rather than ‘0’, link mining
has emerged for calculation of links within a network. Link mining is a framework
applied to analyze networks such as social networks and the World Wide Web. Nodes
and edges (links) of a network are used in the calculation. If nodes of the network are
proteins/compounds, and edges are drawn in the interacting compound-protein pair,
analysis using the framework of link mining becomes possible. Some reports have
also applied the method of link mining directly to the problem of CGBVS [8][9].
However, these methods do not use the framework of the kernel method.
Therefore, in this study, we propose to use the link indicator kernel (LIK), based
on link indicators used in link mining, as the kernel with an interaction profile matrix
such as that formed from GIP kernels. According to a review by Ding et al., the pairwise kernel method (PKM) [7] using a support vector machine (SVM) as a kernel
learning scheme is superior in learning performance to CGBVS [3]. Thus, we integrated GIP and LIK kernels to the PKM and showed that LIK kernels could capture
the effects of interaction profiles.

2

Materials and Methods

2.1

Preliminary

An overview of the compound-protein interaction prediction problem is shown in
Figure 1. Similarities were defined between compounds and between proteins, with
the Tanimoto coefficient of fingerprints (e.g. ECFP [10], SIMCOMP [11]) or Euclid
distance of physicochemical properties for compounds, and the Euclid distance of kmer amino acid sequence profiles or Smith-Waterman alignment scores [12] for proteins.
The interaction y(c, p) between a compound c and a protein p is defined as binary
{0, 1}, where ‘1’ represents an interaction (e.g., c is the active compound for the protein p) and ‘0’ represents no interaction (often including unknowns). For learning, the
nc × np matrix Y = {y(c, p)}c, p (called the interaction matrix) was used as training
data, where nc is the number of target compounds and np is the number of target proteins. Interactions were predicted for pairs of compounds and proteins using the
learned model. When looking at each row and each column of the interaction matrix
as a vector, the vector was called the interaction profile. The interaction profile vc of
compound c was v c ( y (c, p1 ), y (c, p2 ),..., y (c, pnp ))T , and the interaction profile vp
of protein p was v p

( y (c1 , p ), y (c2 , p ),..., y (cnc , p))T .

Link Mining for Kernel-based CGBVS

2.2

4

PKM

The pairwise kernel method (PKM) [7] developed by Jacob et al. is based on pairwise kernels and tensor product representation for compound and protein vectors.
1RUPDOO\DPDSĭ c, p) for a pair of compounds and proteins (c, p) is required for a
learning scheme. In the PKM, the learning scheme involves the tensor product of the
PDSRIFRPSRXQGĭc(c DQGWKHPDSRISURWHLQĭp(p 7KHUHIRUHĭ c, p) is represented as follows:
) (c, p )

) c (c )

) p ( p) ,

(2)

where
is the tensor product operator. Pairwise kernel k is defined between two
pairs of proteins and compounds (c, p) and (c’, p’) as follows:
k ((c, p ), (cc, p c)) { ) (c, p )T ) (cc, p c)
() c (c )

) p ( p ))T () c (cc)

) p ( p c))

) c (c)T ) c (cc) u ) p ( p )T ) p ( p c)

(3)

{ kc (c, cc) u k p ( p, p c) ,

where kc is a compound kernel between two compounds, and kp is a protein kernel
between two proteins. Thus, it is possible to find the kernel k between two compoundprotein pairs with the scalar product of kc and kp. If both kc and kp are positive definite
kernels, k is also a positive definite kernel. The similarity value mentioned in Section
2.1 is often used for kc and kp [4].
2.3

GIP

The Gaussian interaction profile (GIP) [5] was developed to incorporate interaction
profiles into kernel learning by van Laarhoven et al. The GIP kernel kGIP based on the
radial basis function shown in Eq. (1) is used for the compound kernel kc and protein
kernel kp in Eq. (3). Here,

Jc

§1
¨
© nc

nc

¦
i 1

v ci

2

1

·
¸ , Jp
¹

§ 1
¨¨
© np

1

np

¦
i 1

v pi

2

·
¸¸ .
¹

(4)

Importantly, kGIP is never used alone for kc and kp, but is used as a multiple kernel
(simple weighted average) in combination with similarity-based kernels:
kc (c, cc)
k p ( p, p c)

ksim, c (c, cc)  wk , c kGIP, c (c, cc)
ksim, p ( p, p c)  wk , p kGIP, p ( p, p c) ,

where wk, c and wk, p are weighted parameters for multiple kernels.

(5)

5

M. Ohue, T. Yamazaki, T. Ban, and Y. Akiyama

2.4

LIK

The link indicator is an index used for network structural analysis, such as analysis
of the hyperlink structure of the World Wide Web and friend relationships in social
network services. In this study, we proposed link indicator kernels (LIKs) based on
the link indicators for compound-protein interaction networks to incorporate interaction profiles into kernel learning. We selected three link indicators:
Jaccard index

kLIK-Jac ( v, v c)

Cosine similarity

LHN

v T vc
2

2

v  vc  v T vc

kLIK-cos ( v, v c)

kLIK-LHN ( v, v c)

v T vc
v vc

(7)

.

(8)

v T vc
v

2

vc

(6)

2

These link indicators become positive definite kernels when used as kernels. Cosine
similarity and LHN are positive definite kernels because of the properties of the kernel function 1 and the positive definite of the inner product between the two vectors,
and the Jaccard index was previously proven to be positive definite by Bouchard et al.
[13]. There are other link indicators, such as the Adamic-Adar index and graph distance; however, because these are not positive definite kernels, as required for kernel
methods, they were not used in this study.
For integration of LIK and PKM (similarity kernels), the same method applied for
GIP was adopted. That is, considering multiple kernels, the kernels were defined as:
kc (c, cc)
k p ( p, p c)

ksim, c (c, cc)  wk , c kLIK, c (c, cc)
ksim, p ( p, p c)  wk , p kLIK, p ( p, p c) ,

(9)

where kLIK, c and kLIK, p are LIKs for two compounds and two proteins, respectively.
2.5

Implementation

In this study, we used scikit-learn [14], a Python library for machine learning, to
implement PKM, GIP, and LIK. As a kernel learning method, SVM can be used for
scikit-learn based on LIBSVM [15]. For the link indicator calculation of LIK, we used
the python library networkx [16].

1

Let k : X u X o \ be a positive definite kernel and f : X o \ be an arbitrary function.
Then, the kernel k c(x, y ) f (x)k (x, y ) f (y ) (x, y  X ) is also positive definite.

Link Mining for Kernel-based CGBVS

2.6

6

Dataset and Performance Evaluation

We used the benchmark dataset of CPI predictions published by Yamanishi et al.
[4] according to the review of Ding et al. [3]. It is a well-known and well-used
benchmark dataset in the field. The dataset consisted of four target protein groups
(“Nuclear Receptor”, “GPCR”, “Ion Channel”, and “Enzyme”). The SIMCOMP score
[11] was used for compound similarity, and the normalized Smith-Waterman score
[12] was used for protein similarity, as calculated by Yamanishi et al. [4]. Information
on the interaction matrix was also provided by Yamanishi et al. [4]. Evaluation was
performed by cross validation (CV). Three types of CVs were tested: randomly selected from all compound-protein pairs (pairwise CV), randomly selected compounds
(compound CV), and randomly selected proteins (protein CV). The outlines of these
CVs are shown in Figure 2. According to Ding et al. [3], the area under the receiver
operating characteristic curve (AUROC) and the area under the precision-recall curve
(AUPR) were calculated for the evaluation value of 10-fold CVs. Each accuracy value
was averaged five times for 10-fold CVs with different random seeds. Note that the
cost parameter C of SVM was optimized from {0.1, 1, 10, 100} in 3-fold CVs according to Ding et al. [3]. The multiple kernel weights wk of Eqs. (5) and (9) have the
same values for proteins and compounds, and we evaluated {0.1, 0.3, 0.5, 1}.

3

Results and Discussion

3.1

Performance of the Proposed Method for Cross-Validation Benchmarking

Figure 3 shows the results for the prediction accuracy of the average values of
three types of CVs in the four Yamanishi datasets (i.e., average values of 12 prediction accuracy values). We tested multiple kernel weights wk in four patterns, and LIK
with cosine similarity was the most accurate for both AUPR and AUROC (AUPR:
0.562 and AUROC: 0.906). In the case of cosine similarity, the weight wk = 0.5
showed the best performance. Compared with GIP, the prediction accuracy of LIK
showed higher accuracy overall.

p1 p2 p3 p4 p5 p6

p1 p2 p3 p4 p5 p6

p1 p2 p3 p4 p5 p6

c1

1

0

0

1

0

0

c1

1

0

0

1

?

?

c1

?

0

?

1

0

?

c2

0

1

0

0

1

1

c2

0

1

0

0

?

?

c2

0

?

0

?

1

1

c3

1

0

0

0

0

0

c3

1

0

0

0

?

?

c3

1

0

0

0

0

?

c4

1

0

1

1

0

0

c4

1

0

1

1

?

?

c4

1

0

?

?

0

0

c5

?

?

?

?

?

?

c5

0

1

0

0

?

?

c5

?

1

0

0

0

1

c6

?

?

?

?

?

?

c6

0

0

1

1

?

?

c6

?

0

?

1

?

0

compound-wise CV

protein-wise CV

pairwise CV

Fig. 2. Conceptual diagram of three types of cross-validations (CVs): compound-wise CV,
protein-wise CV, and pairwise CV. A case with a 3-fold CV is shown as an example. The “?”
indicates samples to be used for the test set.



7

M. Ohue, T. Yamazaki, T. Ban, and Y. Akiyama
1

0.6

0.4

AUROC

AUPR

0.5

0.3
0.2

wk = 0.1
wk=0.1
wk = 0.3
wk=0.3
wk = 0.5
wk=0.5
wk=1
wk = 1

0.9

0.8

0.1
0.7

0
Jaccard cosine
index similarity

LHN

Jaccard cosine LHN
index similarity

GIP

GIP

Fig. 3. Overall prediction accuracy for each CPI prediction method in 10-fold CV tests. The
AUPR and AUROC values are averaged values of three types of CVs and four types of datasets
(total average for 12 AUPR/AUROC values). For 10-fold CVs, calculations were performed
five times with different random seeds, and the accuracy values were then averaged.

AUPR

Figure 4 shows the mean value of the prediction accuracy for each CV, including
compound-wise, protein-wise, and pairwise CVs. Division of the dataset in each CV
was randomly tried five times, and the values were averaged. The multiple kernel
weight wk was set to the best value in the cross-validation results (shown in Figure 3).
In the evaluation of AUROC, GIP showed accuracy comparable to that of the three
LIKs; however, similar results were not observed for AUPR. In particular, we found
that LIK showed a high value in the AUPR evaluation for compound-wise and protein-wise CVs, which could be evaluated for predictive performance for novel compounds and proteins, respectively.
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
compound-wise CV
Jaccard index

protein-wise CV

cosine similarity

LHN

pairwise CV
GIP

random

1

AUROC

0.9
0.8
0.7
0.6
0.5
0.4
compound-wise CV
Jaccard index

protein-wise CV

cosine similarity

LHN

pairwise CV
GIP

random

Fig. 4. Prediction accuracy of protein-wise, compound-wise, and pairwise CVs. In random
prediction cases, an AUROC value of 0.5 and an AUPR value of 0.035 were obtained (averaged values depending on the ratio of positive samples on the dataset).

8

Frequency

Link Mining for Kernel-based CGBVS

cosine similarity

LHN

GIP

Frequency

Jaccard index

Fig. 5. Distribution of values of LIKs (Jaccard index, cosine similarity, and LHN) and GIP
given all protein interaction profiles in the Yamanishi dataset.

3.2

Observed Distribution of Link Indicator Frequency

Distribution of values of four protein interaction profile similarities (kLIK(p, p'))
were calculated using each link indicator to determine why LIKs with cosine similarity showed better results. The histograms of similarity values are shown in Figure 5.
From this result, the Jaccard index and LHN were found to have relatively similar
distributions of similarity values between 0 and 1 (i.e., the intermediate value was
low). Additionally, the number of pairs whose similarities ranged from 0.95 to 1 had
the highest cosine similarity. This may be related to the AUROC value of cosine similarity, which tended to be higher. Conversely, for LHN, which showed the lowest
similarity from 0.95 to 1, precision may be higher, and AUPR may tend to be higher.
GIP also consisted of a few intermediate values similarly to LHN. Overall, cosine
similarity showed the best performance in this study. A gentle distribution using an
intermediate value may be more effective as information for the compound-protein
network structure.
3.3

Computational Complexity

The computational complexity for constructing the prediction model for the PKM
is O(nc3np3). However, the computational complexity for calculating the link indica-

9

M. Ohue, T. Yamazaki, T. Ban, and Y. Akiyama

tors used in this study was O(ncnp(nc + np)). Thus, the computational complexity of
our proposed method was O(nc3np3 + ncnp(nc + np)). Here, nc and np were greater than
1 in general, and thus, nc3np3 was greater than ncnp(nc + np). Therefore, the computational complexity was O(nc3np3), which was the same as those of PKM and GIP. Our
method could predict CPIs without a major increase in calculation time. The execution time of one run of 10 runs of 10-fold CVs is shown in Table 1. The results in the
table are shown for computations running on an ordinary personal computer with an
Intel Core i5 CPU. Thus, our proposed method showed a slight increase in the execution time by several percentage points as compared with that of PKM (“Nuclear Receptor” had the highest rate of increase due to the small dataset).
3.4

Limitations and Challenges

The proposed method can be directly applied to prediction based on the GIP (e.g.,
WNNGIP [6], KBMF2K [17], and KronRLS-MKL [18]), and improvement of prediction accuracy is expected. For example, WNNGIP can provide robust predictions for
compounds and proteins with less interaction information by complementing the interaction matrix with the weighted nearest neighbor method in advance. However,
kernel-based methods, including the proposed method, are restricted to the framework
using kernel functions. For example, it is not possible to simply combine LIK or GIP
with the method based on matrix factorization (e.g., NRLMF [19]). Further mathematical ideas and computational experiments are needed to develop integrated methods.

4

Conclusions

In this study, we proposed a kernel method using link indicators from the viewpoint of link mining to utilize the information of the CPI network for machine learning. We attempted to utilize three link indicators (Jaccard index, cosine similarity, and
LHN) for construction of positive definite kernels and compared them with the GIP
method when combined with the SVM-based PKM method. As a result, learning by
multiple kernels using LIK with cosine similarity and setting of the kernel weight wk
to 0.5 showed the best prediction accuracy (averaged AUPR = 0.562). In both
AUROC and AUPR, the improvement of LIK accuracy was confirmed compared
with that of GIP.
Table 1. Comparison of calculation times for the PKM and proposed method in each dataset.
The time taken to calculate one time out of 10 calculations of 10-fold CVs is shown.

Conventional (PKM) [sec]
Proposed (PKM plus LIK) [sec]
Increase rate (%)

Nuclear
Receptor
0.0680

4.86

Ion
Channel
24.1

0.0850

5.17

24.8

239

25

6.4

2.9

3.3

GPCR

Enzyme
232

Link Mining for Kernel-based CGBVS

10

Acknowledgments. This work was partially supported by the Japan Society for the
Promotion of Science (JSPS) KAKENHI (grant numbers 24240044 and 15K16081),
and Core Research for Evolutional Science and Technology (CREST) “Extreme Big
Data” (grant number JPMJCR1303) from the Japan Science and Technology Agency
(JST).

References
1. Lavecchia, A.: Machine-learning approaches in drug discovery: methods and applications. Drug Discov. Today. 20, 318–331 (2015).
2. Drwal, M.N., Griffith, R.: Combination of ligand- and structure-based methods in
virtual screening. Drug Discov. Today Technol. 10, e395–e401 (2013).
3. Ding, H., Takigawa, I., Mamitsuka, H., Zhu, S.: Similarity-based machine learning
methods for predicting drug-target interactions: a brief review. Brief. Bioinform.
15, 734–747 (2014).
4. Yamanishi, Y., Araki, M., Gutteridge, A., Honda, W., Kanehisa, M.: Prediction of
drug-target interaction networks from the integration of chemical and genomic
spaces. Bioinformatics. 24, i232–i240 (2008).
5. van Laarhoven, T., Nabuurs, S.B., Marchiori, E.: Gaussian interaction profile kernels for predicting drug-target interaction. Bioinformatics. 27, 3036–3043 (2011).
6. van Laarhoven, T., Marchiori, E.: Predicting drug-target interactions for new drug
compounds using a weighted nearest neighbor profile. PLoS ONE. 8, e66952
(2013).
7. Jacob, L., Vert, J.P.: Protein-ligand interaction prediction: an improved chemogenomics approach. Bioinformatics. 24, 2149–2156 (2008).
8. Daminelli, S., Thomas, J.M., Durán, C., Cannistraci, C.V.: Common neighbours
and the local-community-paradigm for topological link prediction in bipartite networks. New J. Phys. 17, 113037 (2015)
9. Durán, C., Daminelli, S., Thomas, J.M., Haupt, V.J., Schroeder, M., Cannistraci,
C.V.: Pioneering topological methods for network-based drug-target prediction by
exploiting a brain-network self-organization theory. Brief Bioinform. (2017) [Epub
ahead of print]
10. Rogers, D., Hahn, M.: Extended-connectivity fingerprints. J. Chem. Inf. Model. 50,
742–754 (2010).
11. Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences.
J. Mol. Biol. 147, 195–197 (1981).
12. Hattori, M., Okuno, Y., Goto, S., Kanehisa, M.: Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways. J. Am. Chem. Soc. 125, 11853–11865 (2003).
13. Bouchard, M., Jousselme, A.-L., Doré, P.-E.: A proof for the positive definiteness
of the Jaccard index matrix. Int. J. Approx. Reason. 54, 615–626 (2013).
14. scikit-learn: machine learning in Python, http://scikit-learn.org/stable/ (accessed
27 March 2017).
15. Chang, C.-C., Lin, C.: LIBSVM: A library for support vector machines. ACM
Trans. Intell. Syst. Technol. 2, 1–27 (2011).

11

M. Ohue, T. Yamazaki, T. Ban, and Y. Akiyama

16. NetworkX-High-productivity
software
for
complex
networks,
https://networkx.github.io/ (accessed 27 March 2017).
17. Gonen, M.: Predicting drug-target interactions from chemical and genomic kernels
using Bayesian matrix factorization. Bioinformatics. 28, 2304–2310 (2012).
18. Nascimento, A.C.A, Prudêncio, R.B.C., Costa, I.G.: A multiple kernel learning algorithm for drug-target interaction prediction. BMC Bioinformatics. 17, 46 (2016).
19. Liu, Y., Wu, M., Miao, C., Zhao, P., Li, X.-L: Neighborhood regularized logistic
matrix factorization for drug-target interaction prediction. PLoS Comput. Biol. 12,
e1004760 (2016).

