BACKGROUND
drugs may interact when multiple drugs are co-prescribed.
drug-drug interactions  may exert different effects, and adverse drug-drug interactions can lead to patient death or drug withdrawal .
ddi prediction can help to reduce unexpected effects as well as optimize the treatments in the drug design, clinical trials, and post-marketing surveillance.
silico methods, in vitro methods, vivo experiments and clinical trials can identify ddis, but they are labor-intensive and time-consuming.
statistical methods  were developed to detect whether the combination of two drugs is associated with an increased risk of certain adverse events, by analyzing spontaneous reports, insurance claim databases and electronic medical records.
in recent years, researchers collected drug data from literatures, reports and etc., and constructed public databases  which facilitate the development of computational prediction methods.
to the best of our knowledge, a great number of machine learning methods were proposed to predict ddis.
existing methods are roughly classified into two types: similarity-based methods and classification-based methods.
the similarity-based methods employed the assumption that similar drugs may interact with a same drug.
gottlieb et al.
<cit>  built prediction models by considering seven kinds of drug-drug similarities.
vilar et al.
proposed the substructure similarity-based prediction method  <cit>  and the interaction profile fingerprint similarity-based prediction method  <cit> .
li et al.
<cit>  developed a bayesian network of combining drug molecular similarity and phenotypic similarity to predict the combination efficacy of drugs.
by using drug-drug similarity indirectly, park et al.
<cit>  applied a random walk with restart to simulate signaling propagation from drug targets and make predictions; zhang et al.
<cit>  adopted the label propagation method to build prediction models based on drug chemical substructures, drug side effects and drug and off side effects.
classification-based methods formulate the drug-drug prediction as binary classification tasks.
cami et al.
<cit>  represented drug-drug pairs as feature vectors, and use presence or absence of interactions as labels, and then built logistic regression models.
cheng et al.
<cit>  applied five predictive models  to build prediction models.
besides similarity-based methods and classification-based methods, there are several methods designed for specific purposes.
takarabe et al.
<cit>  constructed a multi-level drug-drug interaction network, and analyzed, characterized and classified adverse drug-drug interactions.
huang et al.
<cit>  developed a target-center system for each drug, which consists of drug targets and their neighbors in the ppi network and human tissue gene expression.
since many ddis are not detected or observed in clinical trials, this work is aimed to predict undetected or unobserved drug-drug interactions.
classification methods utilize two classes of data: annotated drug-drug interaction pairs and annotated non-interaction pairs to build classification models.
in the binary classification, known interactions are used as positive instances, but other drug pairs may have undetected or unobserved interactions, which need to be predicted.
in machine learning, similar problems are transformed as semi-supervised learning tasks.
for this reason, we build ddi prediction models under the frame of semi-supervised learning.
in this paper, we collect drug substructure data, drug target data, drug enzyme data, drug transporter data, drug pathway data, drug indication data, drug side effect data, drug off side effect data and known drug-drug interactions.
multi-source data provide biological information, chemical information, phenotypic information and known interactions to characterize drug-drug interactions.
to make use of diverse information, we adopt three representative methods, i.e., the neighbor recommender method  <cit> , the random walk method and the matrix perturbation method  <cit> , to build different prediction models.
according to performances of prediction models, we evaluate the usefulness of different information sources for the ddi prediction.
the study reveals that ddi network based on known ddis can provide the important information for ddi prediction.
further, we present flexible frames of integrating different models with suitable ensemble rules, including the weighted average ensemble rule and the classifier ensemble rule, and develop ensemble models to achieve better performances.
the experiments demonstrate that ensemble methods can combine diverse information to produce the high-accuracy performances, and outperform existing state-of-the-art methods.
methods
datasets
the fda adverse event reporting system  is a database which contains adverse event reports and medication error reports submitted to fda.
tatonetti processed adverse event reports in the aers, and constructed a database named “twosides”  <cit>  which contains side effects caused by the combination of drugs.
there are  <dig> drugs and  <dig>  distinct pairwise ddis from unsafe co-prescriptions in twosides.
the biological information, chemical information and phenotypic information about drugs may be associated with drug-drug interactions.
pubchem compound database  <cit>  can provide drug structures.
drugbank database  <cit>  is a bioinformatics resource with drug targets, drug enzymes and drug transporters.
kegg database  <cit>  is an information resource for protein pathways.
drug targets are mapped to kegg to obtain drug pathways.
sider database  <cit>  contains  <dig> drugs and  <dig> side effect terms which are compiled from public documents and package inserts.
drug side effects and indications are available in sider.
offsides database  <cit>  contains  <dig> drugs and  <dig>  “off-label” side effects.
we map drugs in twosides to sider, offsides, pubchem and drugbank.
as shown in table  <dig>  we obtain  <dig> drugs and  <dig>  pairwise ddis, and substructure data, target data, enzyme data, transporter data, pathway data, indication data, side effect data, off side effect data of these drugs are available.
based on the data, we conduct the comprehensive study to evaluate the usefulness of different data sources for ddi prediction, and discuss how to combine them for the high-accuracy prediction.table  <dig> the descriptions about multi-source drug data
ddi prediction based on multi-source data
multi-source data provide different information for the ddi prediction.
here, we describe how to build models based on different data.
drug-drug similarities bring important clues for the ddi prediction, and different similarities can be extracted from multi-source data.
drug data are classified as four types, i.e., chemical data, biological data, phenotypic data and the drug-drug interaction network data .
on one hand, we calculate the drug-drug similarities in the biological space, chemical space and phenotypic space, by using drug substructures, drug targets, drug enzymes, drug transporters, drug pathways, drug indications, drug side effects and drug off side effects.
on the other hand, we calculate the drug-drug similarities in the drug-drug interaction network.
in order to utilize drug-drug similarities, we consider two representative methods  <cit> : the neighbor recommender method and random walk method, and build ddi prediction models.
we take drugs as nodes and known interactions as edges in the ddi network, and transform the ddi prediction problem as a missing link prediction task.
the missing link prediction is an important topic of theoretical interest and practical significance in the complex network  <cit> .
recently, a novel method named “matrix perturbation method”  <cit>  is proposed, which utilize the network to predict missing links .
the studies demonstrated that this method outperforms other missing link prediction methods.
therefore, we adopt the matrix perturbation method to predict potential ddis based on the ddi network.
in the following context, similarity-based ddi prediction based on multi-source data presents how to extract different drug-drug similarities from different data and how to develop similarity-based models; matrix perturbation method for ddi prediction presents the missing link prediction method .
similarity-based ddi prediction based on multi-source data
drug-drug similarity based on biological data, chemical data and phenotypic data
a drug can be represented as a binary feature vector, by using drug substructures, drug targets, drug enzymes, drug transporters, drug pathways, drug indications, drug side effects, or drug off side effects.
dimensions of the feature vector respond to presence or absence of components with values  <dig> or  <dig>  for example, there are  <dig> types of drug substructures, and a drug can be transformed as an 881-dimensional vector.
given a drug x and a drug y, their feature vectors are v
x and v
y, and the similarity between x and y is then calculated by jaccard formula: svxvy=m11m01+m10+m <dig>
where m
<dig> is the number of dimensions where v
x and v
y both have a value of 1; m
<dig> is the number of dimensions where v
x has a value of  <dig> and v
y has a value of 1; m
<dig> is the number of dimensions where v
x has a value of  <dig> and v
y has a value of  <dig>
therefore, we can obtain  <dig> drug feature-based drug-drug similarities, including substructure-based similarity, target-based similarity, enzyme-based similarity, transporter-based similarity, pathway-based similarity, indication-based similarity, side effect-based similarity and off side effect-based similarity.
drug-drug similarity based on known drug-drug interactions
by considering drugs as nodes and interaction as edges, known ddis can form a ddi network.
we calculate drug-drug similarities in the ddi network  <cit> .
the adjacent matrix of the ddi network is denoted as a = , and denotes the set of nodes linked to node.
several similarities between a drug x and a drug y can be defined.
common neighbor similarity s
cn takes the number of common neighbors between two nodes, scnxy=Γx∩Γy
adamic-adar similarity s
aa is the counting of common neighbors by assigning the less connected neighbors more weights, saaxy=∑z∈Γx∩Γy1logΓz
resource allocation similarity s
ra is based on the complex network resource allocation dynamics, sraxy=∑z∈Γx∩Γy1Γz
katz similarity s
katz sums over the collection of paths with exponential damping according to path lengths, skatzxy=αaxy+α2axy2+α3axy3+⋯=i−αa−1−i
where α is a parameter, and i is the identity matrix.
|α| < 1/λ
max is the condition for the compact form, and λ
max is the largest eigenvalue of a.
average commute time similarity s
act is the average number of steps required by a random walker starting from one node to reach another, sactxy=1lxx++lyy+−2lxy+
where l
+ is the pseudoinverse of the laplacian matrix for the network.
the random walk with restart similarity s
rwr is the probability that a random walker starting from an initial node x reaches y. the walker moves with the probability μ of returning to the initial node and the probability 1 − μ going to adjacent nodes, srwrxy=qxy+qyx
where q = − 1
a, and p = d
− 1
a is the normalized transition matrix of the adjacency matrix a, and d is the degree matrix of a.
therefore, we obtain  <dig> ddi network-based drug-drug similarities, including common neighbor similarity, adamic-adar similarity, resource allocation similarity, katz similarity, average commute time similarity and random walk with restart similarity.
similarity-based methods for ddi prediction
given a n × n similarity matrix s =  for n drugs, known pairwise ddis are denoted by an adjacent matrix a = .
the neighbor recommender method and the random walk method are briefly introduced as follows.
the neighbor recommender method  <cit>  is one of most popular methods in recommender systems, which recommends items  to users, or predicts the ‘rating’ or ‘preference’ that users would give to items.
the neighbor recommender method takes the weighted average information of neighbors for prediction.
y
ij = ∑k =  <dig> k ≠ jn
s
ik
a
kj/∑k =  <dig> k ≠ jn
s
ik is calculated for drugi and drugj which don’t have known interaction, where s
ik is the similarity between drugi and drugk, and a
kj = 1 or  <dig> means interaction or non-interaction between drugk and drugj.
we can calculate y
ji in this same way.
the probability that drugi interacts with drugj
score
ji = score
ij = y
ij + y
ji.
a random walk is a mathematical formalization of a path that consists of a succession of random steps.
there are a great number of successful applications in the network analysis .
in random walk, a random walker starts from an initial node, and moves to neighbors with the probability μ and moves back to the initial node with the probability 1 − μ. the similarity matrix s is normalized as w = d
− 1
s, where d is the degree matrix of s. the matrix form of the update is summarized as y = μwy + a, and it will converge to the solution: y = − 1
a. the probability that drugi interacts with drugj
score
ji = score
ij = y
ij + y
ji.
matrix perturbation method for ddi prediction
the matrix perturbation method assumes that random removal of a small proportion of links from a network will not change the network structure  <cit> , which is reflected by eigenvectors of its adjacent matrix.
let’s introduce notations for the matrix perturbation method.
given the drug-drug interaction network g, v is the set of nodes, and e is the set of edges.
the adjacent matrix is a = , and the eigenvectors and eigenvalues of the adjacent matrix are denoted by x
k and λ
k, k =  <dig>   <dig>  ⋯, n.
a fraction of links Δe are randomly removed from e, and the set of remaining links e
r = e − Δe.
thus, we obtain the new network g
r with the adjacent matrix a
r = a − Δa, where Δa is the adjacent matrix for removed links.
then, we calculate the eigenvectors x
kr and eigenvalues λ
kr of a
r, k =  <dig>   <dig>  ⋯, n. we denote that a = a
r + Δa, x
k = x
kr + Δx
k and λ
k = λ
kr + Δλ
k.
in the network g, the relation of eigenvectors, eigenvalues and the adjacent matrix is written as, ar+Δaxkr+Δxk=λkr+Δλkxkr+Δxk
by left multiplying t in above equation, we can obtain Δλk≈xkrtΔaxkrxkrtxkr.
we estimate eigenvalues λ
k = λ
kr + Δλ
k, and keep eigenvectors x
kr unchanged.
then, we reconstruct the adjacent matrix of g by summing eigenvalues and eigenvectors, a˜=∑i=1nλkr+Δλkxkrxkrt
the probability that drugi interacts with drugj
score
ij = score
ji = Ã
ij + Ã
ji.
more details are available in the publication  <cit> .
combining multi-source data for ddi prediction
since we build different prediction models based on different data, it is natural to combine them for better performance.
ensemble learning is a useful technique that aggregates multiple machine learning models to achieve overall high prediction accuracy as well as good generalization  <cit> .
ensemble learning has been applied to a great number of applications in bioinformatics  <cit> .
an ensemble learning system usually has two components: base predictors and ensemble rules.
in our ensemble system, we adopt heterogeneous models {f
i}i = 1n based on multi-source data as base predictors.
to integrate base predictors, we consider two popular ensemble rules: the weighted average ensemble rule and the classifier ensemble rule.
figure  <dig> demonstrates the flowchart of ensemble systems.fig.
<dig> the scheme of integrating multi-source data for ddi prediction
the weighted average ensemble rule takes the weighted average of outputs from base predictor.
for a new input x
new, base predictors give out the predictions {f
i}i = 1n, and their weighted average ∑i = 1n
w
i
f
i is adopted as the prediction of the ensemble model, where ∑i = 1n
w
i =  <dig> and w
i ≥  <dig>  we adopt the genetic algorithm  to determine weights in the ensemble model.
in the ga optimization, candidate weights are represented as chromosomes, and the fitness of a chromosome is the area under the precision-recall curve  score of the ensemble model on the validation data.
the objective function of ga optimization is to maximize the aupr score.
the classifier ensemble rule is to seek a classification function g : , f
<dig>  ⋯, f
n) → { <dig>  1}, which maps outputs of n base predictors to a label.
for a new input x
new, outputs of base predictors are {f
i}i = 1n, and the prediction of the classifier ensemble model is g, f
<dig>  ⋯, f
n).
here, we adopt logistic regression as the classification function.
RESULTS
evaluation metrics
we adopt k-fold cross validation  to evaluate prediction models.
known interactions are randomly split into k subsets with equal size.
in each fold, one subset is used as the testing set;  <dig> and 20% of other interactions  are used as the training set and validation set.
base predictors are constructed on the training set, and parameters in the ensemble system are tuned by using the validation set.
then, the ensemble model makes predictions for the testing set.
this procedure is repeated until each subset is ever used for testing.
to avoid the bias of data split, we implement  <dig> independent runs of k-cv for each model, and average performances are adopted.
here, we adopt several evaluation metrics to measure performances of prediction models, i.e., accuracy , precision, recall, f-measure , area under roc curve  and the area under the precision-recall curve .
in our task, ddis take a small proportion of all drug pairs, and thus aupr, which takes into account both recall and precision, is used as the primary evaluation metric.
performances of different models based on multi-source data
we extract  <dig> different similarities from multi-source data, and respectively adopt the neighbor recommender method and the random walk method to build  <dig> similarity-based prediction models.
by formulating the original problem as a missing link prediction task, we adopt the matrix perturbation method to build the prediction model based on known ddis.
therefore, we construct  <dig> prediction models based on multi-source data.
since different models utilize different information for ddi prediction, performances of the models are indicators for the usefulness of information sources.
as shown in table  <dig>  these models produce different performances on the benchmark dataset in the cross validation.
among eight feature-based similarities, substructure similarity, side effect similarity, off side effect similarity and indication similarity lead to better performances than other similarities, indicating that drug substructures, drug side effects, drug off side effects and drug indications provide important information for the drug-drug interactions.
among the network topology-based similarities, ra and rwr can produce better results.
the comparison shows that drug feature-based similarities as well as topological similarities can provide useful information to characterize drug-drug interactions and lead to useful models.
the matrix perturbation method utilizes the ddi network as a whole to make predictions.
among all prediction models, the matrix perturbation method produces the best results, indicating that known ddis provide one of most useful information to identify potential ddis.table  <dig> performances of different models evaluated by  <dig> runs of 5-cv
neighbor recommender
random walk
we also conduct  <dig> runs of 3-cv to evaluate prediction models, and results are shown in table  <dig>  the comparison between 3-cv results and 5-cv results demonstrates that prediction models have different performances under different experimental conditions, and a model cannot produce the best results in all cases.
for example, the matrix perturbation method assumes that the topology of a network will not change if only a small proportion of links are removed.
in 3-cv, more links are kept for testing, and the predictive power may be affected.
therefore, the matrix perturbation method is not the best predictor in 3-cv experiments.
for this reason, we integrate different models to make robust predictions.table  <dig> performances of different models evaluated by  <dig> runs of 3-cv
neighbor recommender
random walk
performances of ensemble models
based on multi-source data, we construct  <dig> prediction models including  <dig> similarity-based models and one perturbation matrix model.
we use these models as base predictors, and respectively adopt the weighted average ensemble rule and the classifier ensemble rule to build ensemble models.
we apply the genetic algorithm  to determine optimal weights in the weighted average ensemble models.
ga is implemented by using python package “deap”.
the initial population has  <dig> chromosomes.
in the population update, the elitist strategy is used for the selection operator, and default parameters are adopted for the mutation probability and crossover probability.
the population update terminates when the change of best fitness scores is less than the default value of 1e- <dig> or the max generation number of  <dig> is reached.
to build classifier ensemble models, we train the logistic regression classifier to combine outputs of base predictors.
the logistic regression is implemented by using python package “scikit-learn”.
default parameters are used; l <dig> regularization and l <dig> regularization are respectively considered.
in the following context, classifier ensembles models refer to logistic regression ensemble models.
table  <dig> shows 3-cv results and 5-cv results.
in 5-cv experiments, the weighted average ensemble model, the classifier ensemble model  and classifier ensemble model  produce the aupr scores of  <dig> ,  <dig>  and  <dig> ; in 3-cv experiments, three models yield the aupr scores of  <dig> ,  <dig>  and  <dig> .
the comparison demonstrates that the classifier ensemble models produce better results than the weighted average ensemble model.
the possible reason is that the weighted average ensemble method uses the linear function for ensemble learning and classifier ensemble method trains nonlinear function.
moreover, the classifier ensemble method with l <dig> regularization can produce better results than the classifier ensemble method with l <dig> regularization, for l <dig> regularization can produce the sparse model and enhance the generalization capability.table  <dig> performances of ensemble model evaluated by  <dig> runs of 3-cv and 5-cv
clearly, ensemble models produce better results than base predictors.
in 5-cv experiments, the classifier ensemble method  can improve the aupr score of  <dig>   to  <dig> .
since we implement  <dig> runs of 5-cv for ensemble models and matrix perturbation models, we conduct t-test to test the difference of their performances in terms of aupr score, and the statistical significance is observed .
in 3-cv experiments, the classifier ensemble method  can enhance the aupr score from  <dig>   to  <dig> , and we also observe the statistical significance of improvement between the classifier ensemble model  and the indication-based random walk model .
further, we investigate into details of the ensemble models based on 3-cv results and 5-cv results.
firstly, we analyze weights in the weighted average ensemble models determined by ga. there are  <dig> sets of weights for  <dig> runs of 5-cv; there are  <dig> sets of weights for  <dig> runs of 3-cv.
we calculate the average weights for each predictor, and visualize the normalized weights in fig.
<dig>  base predictors with high aurp scores may be assigned great weights.
for example, the matrix perturbation model produces best 5-cv results, and thus gains the greatest weight in the ensemble models.
we observe that several base predictors  are not used in the ensemble models.
the classifier ensemble method  produces the sparse models, which integrate the subset of base predictors.
according to 5-cv results, several base predictors  are not used in the classifier ensemble model.
in the view of computer science, multi-source data provide diverse information but also bring the redundant information.
combining base predictors is a combinatorial optimization problem.
therefore, the weighted average ensemble method and the classifier ensemble method  use a subset of base predictors to develop ensemble models.fig.
<dig> weights for base predictors in the weighted average ensemble models  3-cv experiments;  5-cv experiments
comparison with existing state-of-the-art methods
since this work is designed to predict undetected or unobserved ddis, we adopt methods of the same type for comparison.
vilar used known interactions of most similar drugs to predict ddis, and proposed the substructure similarity-based model  <cit>  and interaction profile fingerprint  similarity-based model  <cit> .
zhang  <cit>  adopted the label propagation algorithm to build substructure similarity-based model, side effect similarity-based model and off side effect similarity-based model.
we name these models as vilar’s substructure-based model, vilar’s cn index-based model, substructure-based label propagation model, side effect-based label propagation model and off side effect-based label propagation model.
these prediction models are implemented according to details in publications.
all models are evaluated by  <dig> runs of cross validation under the same conditions.
as shown in table  <dig>  our ensemble methods produce better results than other state-of-the-art methods in terms of different metrics.
the classifier ensemble method  produces the best results in both 3-cv experiments and 5-cv experiments.
further, we adopt t-test to compare the ensemble methods with other state-of-the-art methods in terms of aupr scores.
table  <dig> demonstrates that our ensemble methods produce significantly better results .table  <dig> performances of the ensemble method and benchmark methods evaluated by  <dig> runs of 3-cv and 5-cv
in one fold of 5-fold cross validation, we adopt 80% interactions  as the training set and the validations set, and use other interactions  as the testing set.
we build the prediction model based on the training set and the validations set, and then make predictions for non-interaction drug-drug pairs  to identify testing interactions .
based on the result, we respectively count how many testing ddis are identified in the top  <dig>  predictions and top  <dig>  predictions.
as shown in fig.
<dig>  the classifier ensemble model  can identify  <dig> testing interactions when verifying top  <dig>  predictions, and identify  <dig> testing interactions when verifying top  <dig>  predictions.
in general, our ensemble models can identify 300 ~  <dig> more interactions than other methods do.fig.
<dig> the number of identified testing interactions  top  <dig>  predictions;  top  <dig>   <dig> predictions.
1: vilar’s substructure-based model ; 2: vilar’s cn index-based model ; 3: substructure-based label propagation model ; 4: side effect-based label propagation model ; 5: off side effect-based label propagation model ; 6: weighted average ensemble method ; 7: l <dig> classifier ensemble method ; 8: l <dig> classifier ensemble method
predicted novel interactions
in this paper, we use the benchmark dataset with  <dig> drugs and  <dig>  pairwise drug-drug interactions from twosides database.
there are  <dig>  drug-drug pairs between these drugs.
besides  <dig>  known pairwise ddis,  <dig> remaining drug pairs  may contain undetected or unobserved ddis, which are not available in twosides.
we train the prediction models based on  <dig> drugs and  <dig>  known ddis, and predict unobserved ddis.
in the prediction, great scores of drug pairs indicate high probabilities of having interactions, and the prediction results are transformed as a recommendation list of unobserved interactions or novel interactions.
to confirm novel interactions, we look up them in the latest online version of drugbank database.
table  <dig> lists top  <dig> novel interactions predicted by our method, and a significant fraction of novel interactions  are confirmed in drugbank database.table  <dig> top  <dig> novel interactions predicted by our method
db00495
db00451
zidovudine
levothyroxine
db01193
db00264
acebutolol
metoprolol
db01197
db00468
captopril
quinine
db00571
db01203
propranolol
nadolol
db01264
db00863
darunavir
ranitidine
db00820
db01020
tadalafil
isosorbide mononitrate
db00540
db00967
nortriptyline
desloratadine
further, we compare the ensemble model and the matrix perturbation model by testing their capability of finding out novel interactions.
the top  <dig> novel interactions predicted by the ensemble model and the matrix perturbation model are provided in supplementary material .
for each method, we find evidences in drugbank to confirm novel interactions.
if we look up all  <dig> interactions of the matrix perturbation model and the ensemble model, we can confirm  <dig> novel interactions and  <dig> novel interactions respectively .
further, based on the top  <dig> novel interactions, we use the number of predictions as x-axis and the number of confirmed novel interactions in the predictions as y-axis, and then visualize performances of two models .
in general, the ensemble model can find out more novel interactions than the matrix perturbation model, indicating the usefulness of integrating multi-source data.
CONCLUSIONS
the prediction of drug-drug interactions is an important task in the drug discovery, which helps to reduce potential risks and understand the mechanism of drug-drug interactions.
this paper collects a wide variety of drug data, and designs the models based on multi-source data for the ddi prediction.
compared with existing ddi prediction methods, our methods produce better performances, and the statistical analysis demonstrates that the performance improvements achieved by our method are statistically significant.
in conclusion, the proposed methods are promising for the ddi prediction.
additional files
additional file 1: top  <dig> novel interactions predicted by the ensemble model and the matrix perturbation model.
additional file 2: visualization of the number of predictions vs. number of confirmed interactions.
abbreviations
5-cv5-fold cross validation
aucarea under roc curve
auprarea under precision-recall curve
ddidrug-drug interaction
gagenetic algorithm

 drugs may interact when multiple drugs are co-prescribed. drug-drug interactions may exert different effects, and adverse drug-drug interactions can lead to patient death or drug withdrawal. ddi prediction can help to reduce unexpected effects as well as optimize the treatments in the drug design, clinical trials, and post-marketing surveillance. silico methods, in vitro methods, vivo experiments and clinical trials can identify ddis, but they are labor-intensive and time-consuming. statistical methods were developed to detect whether the combination of two drugs is associated with an increased risk of certain adverse events, by analyzing spontaneous reports, insurance claim databases and electronic medical records. in recent years, researchers collected drug data from literatures, reports and etc., and constructed public databases which facilitate the development of computational prediction methods. to the best of our knowledge, a great number of machine learning methods were proposed to predict ddis. existing methods are roughly classified into two types: similarity-based methods and classification-based methods. the similarity-based methods employed the assumption that similar drugs may interact with a same drug. gottlieb et al. built prediction models by considering seven kinds of drug-drug similarities. vilar et al. proposed the substructure similarity-based prediction method and the interaction profile fingerprint similarity-based prediction method. li et al. developed a bayesian network of combining drug molecular similarity and phenotypic similarity to predict the combination efficacy of drugs. by using drug-drug similarity indirectly, park et al. applied a random walk with restart to simulate signaling propagation from drug targets and make predictions; zhang et al. adopted the label propagation method to build prediction models based on drug chemical substructures, drug side effects and drug and off side effects. classification-based methods formulate the drug-drug prediction as binary classification tasks. cami et al. represented drug-drug pairs as feature vectors, and use presence or absence of interactions as labels, and then built logistic regression models. cheng et al. applied five predictive models to build prediction models. besides similarity-based methods and classification-based methods, there are several methods designed for specific purposes. takarabe et al. constructed a multi-level drug-drug interaction network, and analyzed, characterized and classified adverse drug-drug interactions. huang et al. developed a target-center system for each drug, which consists of drug targets and their neighbors in the ppi network and human tissue gene expression. since many ddis are not detected or observed in clinical trials, this work is aimed to predict undetected or unobserved drug-drug interactions. classification methods utilize two classes of data: annotated drug-drug interaction pairs and annotated non-interaction pairs to build classification models. in the binary classification, known interactions are used as positive instances, but other drug pairs may have undetected or unobserved interactions, which need to be predicted. in machine learning, similar problems are transformed as semi-supervised learning tasks. for this reason, we build ddi prediction models under the frame of semi-supervised learning. in this paper, we collect drug substructure data, drug target data, drug enzyme data, drug transporter data, drug pathway data, drug indication data, drug side effect data, drug off side effect data and known drug-drug interactions. multi-source data provide biological information, chemical information, phenotypic information and known interactions to characterize drug-drug interactions. to make use of diverse information, we adopt three representative methods, i.e., the neighbor recommender method, the random walk method and the matrix perturbation method, to build different prediction models. according to performances of prediction models, we evaluate the usefulness of different information sources for the ddi prediction. the study reveals that ddi network based on known ddis can provide the important information for ddi prediction. further, we present flexible frames of integrating different models with suitable ensemble rules, including the weighted average ensemble rule and the classifier ensemble rule, and develop ensemble models to achieve better performances. the experiments demonstrate that ensemble methods can combine diverse information to produce the high-accuracy performances, and outperform existing state-of-the-art methods. methods datasets the fda adverse event reporting system is a database which contains adverse event reports and medication error reports submitted to fda. tatonetti processed adverse event reports in the aers, and constructed a database named “twosides” which contains side effects caused by the combination of drugs. there are drugs and distinct pairwise ddis from unsafe co-prescriptions in twosides. the biological information, chemical information and phenotypic information about drugs may be associated with drug-drug interactions. pubchem compound database can provide drug structures. drugbank database is a bioinformatics resource with drug targets, drug enzymes and drug transporters. kegg database is an information resource for protein pathways. drug targets are mapped to kegg to obtain drug pathways. sider database contains drugs and side effect terms which are compiled from public documents and package inserts. drug side effects and indications are available in sider. offsides database contains drugs and “off-label” side effects. we map drugs in twosides to sider, offsides, pubchem and drugbank. as shown in table  we obtain drugs and pairwise ddis, and substructure data, target data, enzyme data, transporter data, pathway data, indication data, side effect data, off side effect data of these drugs are available. based on the data, we conduct the comprehensive study to evaluate the usefulness of different data sources for ddi prediction, and discuss how to combine them for the high-accuracy prediction.table the descriptions about multi-source drug data ddi prediction based on multi-source data multi-source data provide different information for the ddi prediction. here, we describe how to build models based on different data. drug-drug similarities bring important clues for the ddi prediction, and different similarities can be extracted from multi-source data. drug data are classified as four types, i.e., chemical data, biological data, phenotypic data and the drug-drug interaction network data. on one hand, we calculate the drug-drug similarities in the biological space, chemical space and phenotypic space, by using drug substructures, drug targets, drug enzymes, drug transporters, drug pathways, drug indications, drug side effects and drug off side effects. on the other hand, we calculate the drug-drug similarities in the drug-drug interaction network. in order to utilize drug-drug similarities, we consider two representative methods: the neighbor recommender method and random walk method, and build ddi prediction models. we take drugs as nodes and known interactions as edges in the ddi network, and transform the ddi prediction problem as a missing link prediction task. the missing link prediction is an important topic of theoretical interest and practical significance in the complex network. recently, a novel method named “matrix perturbation method” is proposed, which utilize the network to predict missing links. the studies demonstrated that this method outperforms other missing link prediction methods. therefore, we adopt the matrix perturbation method to predict potential ddis based on the ddi network. in the following context, similarity-based ddi prediction based on multi-source data presents how to extract different drug-drug similarities from different data and how to develop similarity-based models; matrix perturbation method for ddi prediction presents the missing link prediction method. similarity-based ddi prediction based on multi-source data drug-drug similarity based on biological data, chemical data and phenotypic data a drug can be represented as a binary feature vector, by using drug substructures, drug targets, drug enzymes, drug transporters, drug pathways, drug indications, drug side effects, or drug off side effects. dimensions of the feature vector respond to presence or absence of components with values or for example, there are types of drug substructures, and a drug can be transformed as an 881-dimensional vector. given a drug x and a drug y, their feature vectors are v x and v y, and the similarity between x and y is then calculated by jaccard formula: svxvy=m11m01+m10+m where m is the number of dimensions where v x and v y both have a value of 1; m is the number of dimensions where v x has a value of and v y has a value of 1; m is the number of dimensions where v x has a value of and v y has a value of therefore, we can obtain drug feature-based drug-drug similarities, including substructure-based similarity, target-based similarity, enzyme-based similarity, transporter-based similarity, pathway-based similarity, indication-based similarity, side effect-based similarity and off side effect-based similarity. drug-drug similarity based on known drug-drug interactions by considering drugs as nodes and interaction as edges, known ddis can form a ddi network. we calculate drug-drug similarities in the ddi network. the adjacent matrix of the ddi network is denoted as a =, and denotes the set of nodes linked to node. several similarities between a drug x and a drug y can be defined. common neighbor similarity s cn takes the number of common neighbors between two nodes, scnxy=Γx∩Γy adamic-adar similarity s aa is the counting of common neighbors by assigning the less connected neighbors more weights, saaxy=∑z∈Γx∩Γy1logΓz resource allocation similarity s ra is based on the complex network resource allocation dynamics, sraxy=∑z∈Γx∩Γy1Γz katz similarity s katz sums over the collection of paths with exponential damping according to path lengths, skatzxy=αaxy+α2axy2+α3axy3+⋯=i−αa−1−i where α is a parameter, and i is the identity matrix. |α| < 1/λ max is the condition for the compact form, and λ max is the largest eigenvalue of a. average commute time similarity s act is the average number of steps required by a random walker starting from one node to reach another, sactxy=1lxx++lyy+−2lxy+ where l + is the pseudoinverse of the laplacian matrix for the network. the random walk with restart similarity s rwr is the probability that a random walker starting from an initial node x reaches y. the walker moves with the probability μ of returning to the initial node and the probability 1 − μ going to adjacent nodes, srwrxy=qxy+qyx where q = − 1 a, and p = d − 1 a is the normalized transition matrix of the adjacency matrix a, and d is the degree matrix of a. therefore, we obtain ddi network-based drug-drug similarities, including common neighbor similarity, adamic-adar similarity, resource allocation similarity, katz similarity, average commute time similarity and random walk with restart similarity. similarity-based methods for ddi prediction given a n × n similarity matrix s =  for n drugs, known pairwise ddis are denoted by an adjacent matrix a =. the neighbor recommender method and the random walk method are briefly introduced as follows. the neighbor recommender method is one of most popular methods in recommender systems, which recommends items to users, or predicts the ‘rating’ or ‘preference’ that users would give to items. the neighbor recommender method takes the weighted average information of neighbors for prediction. y ij = ∑k =  k ≠ jn s ik a kj/∑k =  k ≠ jn s ik is calculated for drugi and drugj which don’t have known interaction, where s ik is the similarity between drugi and drugk, and a kj = 1 or  means interaction or non-interaction between drugk and drugj. we can calculate y ji in this same way. the probability that drugi interacts with drugj score ji = score ij = y ij + y ji. a random walk is a mathematical formalization of a path that consists of a succession of random steps. there are a great number of successful applications in the network analysis. in random walk, a random walker starts from an initial node, and moves to neighbors with the probability μ and moves back to the initial node with the probability 1 − μ. the similarity matrix s is normalized as w = d − 1 s, where d is the degree matrix of s. the matrix form of the update is summarized as y = μwy + a, and it will converge to the solution: y = − 1 a. the probability that drugi interacts with drugj score ji = score ij = y ij + y ji. matrix perturbation method for ddi prediction the matrix perturbation method assumes that random removal of a small proportion of links from a network will not change the network structure, which is reflected by eigenvectors of its adjacent matrix. let’s introduce notations for the matrix perturbation method. given the drug-drug interaction network g, v is the set of nodes, and e is the set of edges. the adjacent matrix is a =, and the eigenvectors and eigenvalues of the adjacent matrix are denoted by x k and λ k, k =     ⋯, n. a fraction of links Δe are randomly removed from e, and the set of remaining links e r = e − Δe. thus, we obtain the new network g r with the adjacent matrix a r = a − Δa, where Δa is the adjacent matrix for removed links. then, we calculate the eigenvectors x kr and eigenvalues λ kr of a r, k =     ⋯, n. we denote that a = a r + Δa, x k = x kr + Δx k and λ k = λ kr + Δλ k. in the network g, the relation of eigenvectors, eigenvalues and the adjacent matrix is written as, ar+Δaxkr+Δxk=λkr+Δλkxkr+Δxk by left multiplying t in above equation, we can obtain Δλk≈xkrtΔaxkrxkrtxkr. we estimate eigenvalues λ k = λ kr + Δλ k, and keep eigenvectors x kr unchanged. then, we reconstruct the adjacent matrix of g by summing eigenvalues and eigenvectors, a˜=∑i=1nλkr+Δλkxkrxkrt the probability that drugi interacts with drugj score ij = score ji = Ã ij + Ã ji. more details are available in the publication. combining multi-source data for ddi prediction since we build different prediction models based on different data, it is natural to combine them for better performance. ensemble learning is a useful technique that aggregates multiple machine learning models to achieve overall high prediction accuracy as well as good generalization. ensemble learning has been applied to a great number of applications in bioinformatics. an ensemble learning system usually has two components: base predictors and ensemble rules. in our ensemble system, we adopt heterogeneous models {f i}i = 1n based on multi-source data as base predictors. to integrate base predictors, we consider two popular ensemble rules: the weighted average ensemble rule and the classifier ensemble rule. figure  demonstrates the flowchart of ensemble systems.fig. the scheme of integrating multi-source data for ddi prediction the weighted average ensemble rule takes the weighted average of outputs from base predictor. for a new input x new, base predictors give out the predictions {f i}i = 1n, and their weighted average ∑i = 1n w i f i is adopted as the prediction of the ensemble model, where ∑i = 1n w i =  and w i ≥  we adopt the genetic algorithm to determine weights in the ensemble model. in the ga optimization, candidate weights are represented as chromosomes, and the fitness of a chromosome is the area under the precision-recall curve score of the ensemble model on the validation data. the objective function of ga optimization is to maximize the aupr score. the classifier ensemble rule is to seek a classification function g:, f  ⋯, f n) → {  1}, which maps outputs of n base predictors to a label. for a new input x new, outputs of base predictors are {f i}i = 1n, and the prediction of the classifier ensemble model is g, f  ⋯, f n). here, we adopt logistic regression as the classification function.  evaluation metrics we adopt k-fold cross validation to evaluate prediction models. known interactions are randomly split into k subsets with equal size. in each fold, one subset is used as the testing set; and 20% of other interactions are used as the training set and validation set. base predictors are constructed on the training set, and parameters in the ensemble system are tuned by using the validation set. then, the ensemble model makes predictions for the testing set. this procedure is repeated until each subset is ever used for testing. to avoid the bias of data split, we implement independent runs of k-cv for each model, and average performances are adopted. here, we adopt several evaluation metrics to measure performances of prediction models, i.e., accuracy, precision, recall, f-measure, area under roc curve and the area under the precision-recall curve. in our task, ddis take a small proportion of all drug pairs, and thus aupr, which takes into account both recall and precision, is used as the primary evaluation metric. performances of different models based on multi-source data we extract different similarities from multi-source data, and respectively adopt the neighbor recommender method and the random walk method to build similarity-based prediction models. by formulating the original problem as a missing link prediction task, we adopt the matrix perturbation method to build the prediction model based on known ddis. therefore, we construct prediction models based on multi-source data. since different models utilize different information for ddi prediction, performances of the models are indicators for the usefulness of information sources. as shown in table  these models produce different performances on the benchmark dataset in the cross validation. among eight feature-based similarities, substructure similarity, side effect similarity, off side effect similarity and indication similarity lead to better performances than other similarities, indicating that drug substructures, drug side effects, drug off side effects and drug indications provide important information for the drug-drug interactions. among the network topology-based similarities, ra and rwr can produce better results. the comparison shows that drug feature-based similarities as well as topological similarities can provide useful information to characterize drug-drug interactions and lead to useful models. the matrix perturbation method utilizes the ddi network as a whole to make predictions. among all prediction models, the matrix perturbation method produces the best results, indicating that known ddis provide one of most useful information to identify potential ddis.table performances of different models evaluated by runs of 5-cv neighbor recommender random walk we also conduct runs of 3-cv to evaluate prediction models, and results are shown in table  the comparison between 3-cv results and 5-cv results demonstrates that prediction models have different performances under different experimental conditions, and a model cannot produce the best results in all cases. for example, the matrix perturbation method assumes that the topology of a network will not change if only a small proportion of links are removed. in 3-cv, more links are kept for testing, and the predictive power may be affected. therefore, the matrix perturbation method is not the best predictor in 3-cv experiments. for this reason, we integrate different models to make robust predictions.table performances of different models evaluated by runs of 3-cv neighbor recommender random walk performances of ensemble models based on multi-source data, we construct prediction models including similarity-based models and one perturbation matrix model. we use these models as base predictors, and respectively adopt the weighted average ensemble rule and the classifier ensemble rule to build ensemble models. we apply the genetic algorithm to determine optimal weights in the weighted average ensemble models. ga is implemented by using python package “deap”. the initial population has chromosomes. in the population update, the elitist strategy is used for the selection operator, and default parameters are adopted for the mutation probability and crossover probability. the population update terminates when the change of best fitness scores is less than the default value of 1e- or the max generation number of is reached. to build classifier ensemble models, we train the logistic regression classifier to combine outputs of base predictors. the logistic regression is implemented by using python package “scikit-learn”. default parameters are used; l regularization and l regularization are respectively considered. in the following context, classifier ensembles models refer to logistic regression ensemble models. table  shows 3-cv results and 5-cv results. in 5-cv experiments, the weighted average ensemble model, the classifier ensemble model and classifier ensemble model produce the aupr scores of, and; in 3-cv experiments, three models yield the aupr scores of, and. the comparison demonstrates that the classifier ensemble models produce better results than the weighted average ensemble model. the possible reason is that the weighted average ensemble method uses the linear function for ensemble learning and classifier ensemble method trains nonlinear function. moreover, the classifier ensemble method with l regularization can produce better results than the classifier ensemble method with l regularization, for l regularization can produce the sparse model and enhance the generalization capability.table performances of ensemble model evaluated by runs of 3-cv and 5-cv clearly, ensemble models produce better results than base predictors. in 5-cv experiments, the classifier ensemble method can improve the aupr score of to. since we implement runs of 5-cv for ensemble models and matrix perturbation models, we conduct t-test to test the difference of their performances in terms of aupr score, and the statistical significance is observed. in 3-cv experiments, the classifier ensemble method can enhance the aupr score from to, and we also observe the statistical significance of improvement between the classifier ensemble model and the indication-based random walk model. further, we investigate into details of the ensemble models based on 3-cv results and 5-cv results. firstly, we analyze weights in the weighted average ensemble models determined by ga. there are sets of weights for runs of 5-cv; there are sets of weights for runs of 3-cv. we calculate the average weights for each predictor, and visualize the normalized weights in fig.  base predictors with high aurp scores may be assigned great weights. for example, the matrix perturbation model produces best 5-cv results, and thus gains the greatest weight in the ensemble models. we observe that several base predictors are not used in the ensemble models. the classifier ensemble method produces the sparse models, which integrate the subset of base predictors. according to 5-cv results, several base predictors are not used in the classifier ensemble model. in the view of computer science, multi-source data provide diverse information but also bring the redundant information. combining base predictors is a combinatorial optimization problem. therefore, the weighted average ensemble method and the classifier ensemble method use a subset of base predictors to develop ensemble models.fig. weights for base predictors in the weighted average ensemble models 3-cv experiments; 5-cv experiments comparison with existing state-of-the-art methods since this work is designed to predict undetected or unobserved ddis, we adopt methods of the same type for comparison. vilar used known interactions of most similar drugs to predict ddis, and proposed the substructure similarity-based model and interaction profile fingerprint similarity-based model. zhang adopted the label propagation algorithm to build substructure similarity-based model, side effect similarity-based model and off side effect similarity-based model. we name these models as vilar’s substructure-based model, vilar’s cn index-based model, substructure-based label propagation model, side effect-based label propagation model and off side effect-based label propagation model. these prediction models are implemented according to details in publications. all models are evaluated by runs of cross validation under the same conditions. as shown in table  our ensemble methods produce better results than other state-of-the-art methods in terms of different metrics. the classifier ensemble method produces the best results in both 3-cv experiments and 5-cv experiments. further, we adopt t-test to compare the ensemble methods with other state-of-the-art methods in terms of aupr scores. table  demonstrates that our ensemble methods produce significantly better results.table performances of the ensemble method and benchmark methods evaluated by runs of 3-cv and 5-cv in one fold of 5-fold cross validation, we adopt 80% interactions as the training set and the validations set, and use other interactions as the testing set. we build the prediction model based on the training set and the validations set, and then make predictions for non-interaction drug-drug pairs to identify testing interactions. based on the result, we respectively count how many testing ddis are identified in the top predictions and top predictions. as shown in fig.  the classifier ensemble model can identify testing interactions when verifying top predictions, and identify testing interactions when verifying top predictions. in general, our ensemble models can identify 300 ~  more interactions than other methods do.fig. the number of identified testing interactions top predictions; top predictions. 1: vilar’s substructure-based model; 2: vilar’s cn index-based model; 3: substructure-based label propagation model; 4: side effect-based label propagation model; 5: off side effect-based label propagation model; 6: weighted average ensemble method; 7: l classifier ensemble method; 8: l classifier ensemble method predicted novel interactions in this paper, we use the benchmark dataset with drugs and pairwise drug-drug interactions from twosides database. there are drug-drug pairs between these drugs. besides known pairwise ddis, remaining drug pairs may contain undetected or unobserved ddis, which are not available in twosides. we train the prediction models based on drugs and known ddis, and predict unobserved ddis. in the prediction, great scores of drug pairs indicate high probabilities of having interactions, and the prediction results are transformed as a recommendation list of unobserved interactions or novel interactions. to confirm novel interactions, we look up them in the latest online version of drugbank database. table  lists top novel interactions predicted by our method, and a significant fraction of novel interactions are confirmed in drugbank database.table top novel interactions predicted by our method db00495 db00451 zidovudine levothyroxine db01193 db00264 acebutolol metoprolol db01197 db00468 captopril quinine db00571 db01203 propranolol nadolol db01264 db00863 darunavir ranitidine db00820 db01020 tadalafil isosorbide mononitrate db00540 db00967 nortriptyline desloratadine further, we compare the ensemble model and the matrix perturbation model by testing their capability of finding out novel interactions. the top novel interactions predicted by the ensemble model and the matrix perturbation model are provided in supplementary material. for each method, we find evidences in drugbank to confirm novel interactions. if we look up all interactions of the matrix perturbation model and the ensemble model, we can confirm novel interactions and novel interactions respectively. further, based on the top novel interactions, we use the number of predictions as x-axis and the number of confirmed novel interactions in the predictions as y-axis, and then visualize performances of two models. in general, the ensemble model can find out more novel interactions than the matrix perturbation model, indicating the usefulness of integrating multi-source data.  the prediction of drug-drug interactions is an important task in the drug discovery, which helps to reduce potential risks and understand the mechanism of drug-drug interactions. this paper collects a wide variety of drug data, and designs the models based on multi-source data for the ddi prediction. compared with existing ddi prediction methods, our methods produce better performances, and the statistical analysis demonstrates that the performance improvements achieved by our method are statistically significant. in conclusion, the proposed methods are promising for the ddi prediction. additional files additional file 1: top novel interactions predicted by the ensemble model and the matrix perturbation model. additional file 2: visualization of the number of predictions vs. number of confirmed interactions. abbreviations 5-cv5-fold cross validation aucarea under roc curve auprarea under precision-recall curve ddidrug-drug interaction gagenetic algorithm 
in this paper, we collect a variety of drug data that may influence drug-drug interactions, i.e., drug substructure data, drug target data, drug enzyme data, drug transporter data, drug pathway data, drug indication data, drug side effect data, drug off side effect data and known drug-drug interactions. we adopt three representative methods: the neighbor recommender method, the random walk method and the matrix perturbation method to build prediction models based on different data. the ensemble methods can produce better performances than individual methods, and outperform existing state-of-the-art methods. thus, we evaluate the usefulness of different information sources for the ddi prediction. the experiments demonstrate that different data sources provide diverse information, and the ddi network based on known ddis is one of most important information for ddi prediction. further, we present flexible frames of integrating different models with suitable ensemble rules, including weighted average ensemble rule and classifier ensemble rule, and develop ensemble models to achieve better performances. since many ddis are not detected or observed in clinical trials, this work is aimed to predict unobserved or undetected ddis. drug-drug interactions are one of the major concerns in drug discovery. the online version of this article contains supplementary material, which is available to authorized users. accurate prediction of potential ddis can help to reduce unexpected interactions in the entire lifecycle of drugs, and are important for the drug safety surveillance.
 drug-drug interactions are one of the major concerns in drug discovery. accurate prediction of potential ddis can help to reduce unexpected interactions in the entire lifecycle of drugs, and are important for the drug safety surveillance.  since many ddis are not detected or observed in clinical trials, this work is aimed to predict unobserved or undetected ddis. in this paper, we collect a variety of drug data that may influence drug-drug interactions, i.e., drug substructure data, drug target data, drug enzyme data, drug transporter data, drug pathway data, drug indication data, drug side effect data, drug off side effect data and known drug-drug interactions. we adopt three representative methods: the neighbor recommender method, the random walk method and the matrix perturbation method to build prediction models based on different data. thus, we evaluate the usefulness of different information sources for the ddi prediction. further, we present flexible frames of integrating different models with suitable ensemble rules, including weighted average ensemble rule and classifier ensemble rule, and develop ensemble models to achieve better performances.  the experiments demonstrate that different data sources provide diverse information, and the ddi network based on known ddis is one of most important information for ddi prediction. the ensemble methods can produce better performances than individual methods, and outperform existing state-of-the-art methods. the datasets and source codes are available at https://github.com/zw9977129/drug-drug-interaction/. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords drug-drug interactionensemble learningmissing link predictionrandom walkhttp://dx.doi.org/ /501100001809national natural science foundation of china6110312661572368zhang wen liu feng national natural science foundation of china 61402340luo fei natural science foundation of hubei province of chinazry2014000901tian gang issue-copyright-statement© the author 2017 