NIL UCM: Extracting Drug-Drug interactions from text through combination of sequence and tree kernels

of 7
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Brochures

Published:

Views: 67 | Pages: 7

Extension: PDF | Download: 0

Share
Description
NIL UCM: Extracting Drug-Drug interactions from text through combination of sequence and tree kernels
Transcript
  NIL UCM: Extracting Drug-Drug interactions from text throughcombination of sequence and tree kernels Behrouz Bokharaeian, Alberto D´ıaz Natural Interaction Based on Language GroupUniversidad Complutense de MadridMadrid 28011, Spain { bokharaeian, albertodiaz } @fdi.ucm.es Abstract A drug-drug interaction (DDI) occurs whenone drug affects the level or activity of anotherdrug. Semeval 2013 DDI Extraction challengeis going to be held with the aim of identify-ing the state of the art relation extraction algo-rithms. In this paper we firstly review some of the existing approaches in relation extractiongenerally and biomedical relations especially.And secondly we will explain our SVM basedapproaches that use lexical, morphosyntacticand parse tree features. Our combination of sequence and tree kernels have shown promis-ing performance with a best result of 0.54 F1macroaverage on the test dataset. 1 Introduction A drug-drug interaction occurs when one drug af-fects the level or activity of another drug, for in-stance, drug concentrations. This interaction canresult on reducing its effectiveness or possibly in-creasing its side effects (Stockley, 2007). There aresome helpful DDIs but most of them are danger-ous (Aronson, 2007), for example, patients that take clarithromycin  and  glibenclamide  concurrently mayexperiment  hypoglycaemia .There is a great amount of information about DDIdescribed in papers that health experts have to con-sultinordertobeupdated. Thedevelopmentoftoolsfor extracting this type of information from biomed-icaltextswouldproduceaclearbenefitforthesepro-fessionals reducing the time necessary to review theliterature. Semeval 2013 DDI Extraction challengedecided to being held with the aim of identifying thestate of the art algorithms for automatically extract-ing DDI from biomedical articles. This challengehas two tasks: recognition and classification of drugnames and extraction of drug-drug interactions. Forthe second task, the input corpus contains annota-tions with the drug names.A previous Workshop on Drug-Drug InteractionExtraction (Segura-Bedmar et al., 2011) was heldin 2011 in Huelva, Spain. The main difference isthat the new challenge includes the classification of the drug-drug interactions in four types dependingon the information that is described in the sentencemaking the task much more complicated than be-fore. Additionally the current task involves DDIsfrom two different corpora with different character-istics (Segura-Bedmar et al., 2013).Weparticipatedinthetaskofextractingdrug-druginteractions with two approaches that exploit a richset of tree and sequence features. Our implementedmethods utilize a SVM classifier with a linear ker-nel and a rich set of lexical, morphosyntactic and se-mantic features (e.g. trigger words) extracted fromtexts. In addition some tree features such as shortestpath and subtree features are used. 2 Related work Due to the importance of detecting biological andmedical relations several methods have been appliedfor extracting biological relation information fromtext. In (Song et al., 2010) is presented a method forextracting protein-protein interaction (PPI) throughcombination of an active learning technique and asemi-supervised SVM.Anothermotivatingworkcanbefoundin(Chenet  al., 2011) in which a PPI Pair Extractor was devel-oped that consists of a SVM for binary classificationwhich exploits a linear kernel with a rich set of fea-tures based on linguistic analysis, contextual words,interaction words, interaction patterns and specificdomain information.Another PPI extraction method have been devel-oped in (Li et al., 2010). They have applied an en-semble kernel composed of a feature-based kerneland a structure-based kernel. A more recent researchon tree kernels has been carried out by (Guodonget al., 2010). They have introduced a context-sensitive convolution tree kernel, which specifiesboth context-free and context-sensitive sub-trees bytaking into account the paths of their ancestor nodesas their contexts to capture structural information inthe tree structure. A recent work (Sim˜oes et al.,2013) has introduced an approach for RelationshipExtraction (RE) based on labeled graph kernels. Theproposed kernel is a specification of a random walk kernel that exploits two properties: the words be-tween the candidate entities and the combination of information from distinct sources. A comparativesurvey regarding different kernel based approachesand their performance can be found in (Frunza andInkpen, 2008).Using external knowledge and resources to thetarget sentence is another research direction in therelation extraction task that Chan and Roth haveinvestigated in (Chan and Roth, 2010). Theyhave reported some improvements by using exter-nal sources such as Wikipedia, comparing to basicsupervised learning systems. Thomas and his col-leagues in (Thomas et al., 2011) have developeda majority voting ensemble of contrasting machinelearning methods using different linguistic featurespaces.A more systematic and high quality investigationabout feature selection in kernel based relation ex-pression can be found in (Jiang and Zhai, 2011).They have explored a large space of features for re-lation extraction and assess the effectiveness of se-quences, syntactic parse trees and dependency parsetrees as feature subspaces and sentence representa-tion. They conclude that, by means of a set of ba-sic unit features from each subspace, a reasonablygood performance can be achieved. But when thethree subspaces are combined, the performance canslightly improve, which shows sequence, syntacticand dependency relations have much overlap for thetask of relation extraction.Although most of the previous researches inbiomedical domain has been carried out with respectto protein-protein interaction extraction, and morerecently on drug-drug interaction extraction, othertypes of biomedical relations are being studied: e.g.gene-disease (Airola et al., 2008), disease-treatment(Jung et al., 2012) and drug-disease. 3 Dataset The dataset for the DDIExtraction 2013 task con-tains documents from two sources. It includes Med-Line abstracts and documents from the DrugBank database describing drug-drug interactions (Segura-Bedmar et al., 2013). These documents are anno-tated with drug entities and with information aboutdrug pair interactions: true or false.In the training corpus the interaction type is alsoannotated. There are 4 types of interactions:  effect  , mechanism ,  int  ,  advice .The challenge corpus is divided into training andevaluation datasets (Table 1). The DrugBank train-ing data consists of 572 documents with 5675 sen-tences. This subset contains 12929 entities and26005 drug pair interactions. On the other hand, theMedLine training data consists of 142 abstracts with1301 sentences, 1836 entities and 1787 pairs.The distribution of positive and negative exam-ples are similar in both subsets, 12.98% of positivesinstances on MedLine and 14.57% on DrugBank.With respect to the distribution of categories, the fig-ures show that there is a small number of positiveinstances for categories  int   and  advice  on the Med-Line subset. The  effect   type is the most frequent,outmatching itself on the MedLine subset.The evaluation corpus contains 158 abstracts with973 sentences and 5265 drug pair interactions fromDrugbank, and 33 abstracts with 326 sentences and451 drug pair interactions from Medline. It is worthto emphasize that the distribution of positive andnegative examples is a bit greater (2.22%) in theDrugBank subset compared to the training data, butis almost doubled with respect to MedLine (12,98%to 21,06%). The categories  advice  and  int   have veryfew positive instances in the MedLine subset.  Training  pairs negative DDIs positive DDIs effect mechanism advice intDrugBank 26005 22217 3788 1535 1257 818 178MedLine 1787 1555 232 152 62 8 10 Test  pairs negative DDIs positive DDIs effect mechanism advice intDrugBank 5265 4381 884 298 278 214 94MedLine 451 356 95 62 24 7 2 Table 1: Basic statistics of the training and test datasets. 4 Method Initially several experiments have been developed toexplore the performance of shallow linguistic (SL)andparsetreebasedmethodsonasubsetofthetrain-ingcorpus. AlthoughtheSLkernelachievedconsid-erably good results we have found that the best op-tion was the combination of different kernels usinglinguistic and tree features.Our implemented kernel based approach consistsof four different processes that have been applied se-quentially: preprocessing, feature extraction, featureselection and classification (Figure 1). Our two sub-mitted results were obtained by two different strate-gies. In the first outcome, all the DDIs and type of interactions were extracted in one step, as a 5-classcategorization problem. The second run was carriedoutintwosteps, initiallytheDDIsweredetectedandthen the positively predicted DDIs were used to de-termine the type of the interaction. In the next sub-section the four different processes are described. 4.1 Preprocessing In this phase we have carried out two types of textpreprocessing steps before training the classifier.We have removed some stop words in specialplaces in the sentences that clearly were a matter of concern and caused some inaccuracy, for example,removing question marks at the beginning of a sen-tence. We also carried out a normalization task forsome tokens because of usage of different used en-codings and processing methods, mainly html tags. 4.2 Feature extraction Initially 49 feature classes were extracted for eachinstance that correspond to a drug pair interactionbetween Drug1 and Drug2: •  WordFeatures: IncludeWordsofDrug1, wordsof Drug2, words between Drug1 and Drug2, Figure 1: The different processes followed for our twosubmitted results. three words before Drug1 and three words afterDrug2. Lemmas and stems of all these words.We have used TreeTagger to obtain lemmas andPaice/Husk Stemmer (Paice, 1990) to obtainstems. •  Morphosyntactic Features: Include Part-of-speech (POS) tags of each drug words (Drug1and Drug2), POS of the previous 3 and next 3words. We have used TreeTagger. •  Constituency parse tree features: Include short-est path between Drug1 and Drug2 in the con-stituency parse tree, shortest path between firsttoken in the sentence and Drug1, and shortestpath between Drug2 and last token in the sen-tence in the parse tree, and all subtrees gener-  ated from the constituency parse tree. We haveused Stanford parser  1 for producing tree fea-tures. •  Conjunction features: We have produced somenew conjunction features by combination of different word features and morphosyntacticfeatures such as POSLEMMA and POSSTEMfor all the words before Drug1, words betweenDrug1 and Drug2 and words after Drug2. •  verbs features: Include verbs between Drug1and Drug2, first verb before Drug1 and firstverb after Drug2. Their stem, lemma and theirconjunction features are also included. •  negation features: Only if the sentence containsnegation statements. The features extracted in-clude the left side tokens of the negation scope,the right side tokens of the negation scope andthe tokens inside the negation scope. We haveused NegEx 2 as negation detection algorithm.Finally we have deployed a bag of words ap-proach (BoW) for each feature class in order to ob-tain the final representation for each instance. Wehave limited the size of the vocabulary in the BoWrepresentation with a different number depending onthe data subset. We carried out several experimentsto fix these numbers and at the end we have used1000 words/feature class for MedLine and 6000words/feature class for DrugBank. 4.3 Feature selection We have conducted some feature selection experi-ments to select the best features for improving theresults and reducing running time. We have finallyused Information Gain ranker to eliminate the lesseffective features. We have computed the informa-tion gain for each feature class as the linear combi-nation of the information gain of each correspondingword. Empirically we have selected the best 42 fea-ture classes.On the other hand, we have done a preliminarystudy of the effect of the negation related features.We have found more than 3000 sentences contain-ing negation, most of them corresponds to sentences 1 http://nlp.stanford.edu/software/lex-parser.shtml 2 http://code.google.com/p/negex/  associated with negative examples of interactions.However, these features have been eliminated be-cause we have not obtained a clear improvementwhen we combined them with the other features. 4.4 Classification First we have performed several experiments withdifferent supervised machine learning approachessuch as SVM, Naivebayes, Randomtree, Randomforest, Multilayerperceptroninadditiontocombina-tion of methods. Finally we decided to use a SVMapproach, the Weka Sequential Minimal Optimiza-tion (SMO) algorithm. We used the inner product of the BoW vectors as similarity function.We have submitted two approaches: •  approach 1: SVM (Weka SMO) with 5 cate-gories(effect, mechanism, int, adviceandnull). •  approach 2: We have extracted final results intwo stages. In the first step we have used aSVM (Weka SMO) with 2 categories (positiveand negative) and then we have used a secondSVM classifier with 4 classes on positive ex-tracted DDIs to train and extract the type of in-teraction in the test dataset.The classifiers have been applied separately witheach data subset, that is, a classifier per approach hasbeen developed using the DrugBank training subsetand has been evaluated using the DrugBank test sub-set, and the same process has been applied with theMedLine training and test subset. 5 Results In this section we first show the evaluation resultswith our two approaches. Secondly an error analy-sis was carried out with a development set extractedfrom the training corpus. 5.1 Test data results We have submitted two runs that corresponds withthe approaches described in the previous section.Table 2 shows the results obtained with the first ap-proach (one step) and Table 3 shows the results withthe second approach (two steps).It can be observed that the results on detection of DDI are better with the approach 2: 0.656 against0.588 on F1. This result is a consequence that we  Run  P R F1NILUCM1 (All) 0.632 0.464 0.535NILUCM2 (All) 0.547 0.507 0.526NILUCM1 (Drugbank) 0.651 0.498 0.565NILUCM2 (Drugbank) 0.558 0.542 0.550NILUCM1 (Medline) 0.333 0.074 0.121NILUCM2 (Medline) 0.221 0.073 0.110 Table 4: Macroaverage test set results. have more information to obtain the detection of theinteraction if we use the information from all the dif-ferent types than if we obtain it joining the resultsobtained per each category. With respect to detec-tion and classification the results are also better withapproach 2 for a similar reason: 0.548 against 0.517on F1.With respect to the categories, in the more pop-ulated ones the general tendency of better resultsfrom approach 2 continues, especially in  effect   type:0.556 against 0.489. With respect to  advice  and  int  ,the recall is better in approach 2 but the improve-ment in precision is greater in approach1 giving abetter result on F1 to approach 1, especially in  int  type: 0.427 against 0.393.Table 4 shows the macroaverage results separatedby subset data. The best results obtained for ap-proach 1 are due to that this type of average givesequal weight to each category, favouring then thecategories with less instances.Other important insight that can be extracted fromthis table is that our results are much better for Drug-Bank dataset with both approaches. These resultscan be justified due to high similarity between sen-tences in Drugbank training and test corpus. In factthe Medline corpus commonly has more words un-related to DDI subjects. In addition to this argument,the smaller number of training pairs in the Medlinecorpus can be other reason to obtain worst results. 5.2 Error analysis We have extracted a stratified development corpusfrom the training corpus in order to perform an erroranalysis. We have used a 10% of the training corpus.It contains 2779 pairs, of which 397 are DDIs. Table5 shows the results obtained with the two submittedapproaches.The results with our development corpus showsthe same tendency, that is, approach 2 is better thanapproach 1 on detection of DDI and on microav-erage classification. On the other hand, results arehigher than those on test corpus because the infor-mation contained in the development corpus is moresimilar to the rest of training corpus than informa-tion on the test set.We have performed an analysis of the errors pro-duced for both approaches in the Detection andClassification of DDI subtask. The errors obtainedare 112 false positives (Fp) and 116 false negatives(Fn) associated to approach 1, and 111 false posi-tives (Fp) and 112 false negatives (Fn) to approach2. Apart from the comments explained in the pre-vious section about the small number of instanceson the MedLine subset, we think the main problemis related with the management of long sentenceswith complex syntax. These sentences are more dif-ficult for our approaches because the complexity of the sentence generates more errors in the tokenizingand parsing processes affecting the representation of the instances both in training and test phases. Weshow below some false positives and false negativesexamples. •  The effects of   ERGOMAR  may be potentiatedby  triacetyloleandomycin  which inhibits themetabolism of ergotamine. DrugBank. Falsenegative. •  Prior administration of   4-methylpyrazole  (90mg kg(-1) body weight) was shown to preventthe conversion of   1,3-difluoro-2-propanol (100 mg kg(-1) body weight) to (-)-erythro-fluorocitrate in vivo and to eliminate thefluoride and citrate elevations seen in 1,3-difluoro-2-propanol-intoxicated animals Med-Line. False negative. •  Drug Interactions with Antacids Administra-tion of 120 mg of   fexofenadine hydrochloride (2 x 60 mg capsule) within 15 minutes of analuminum and magnesium containing antacid(Maalox ) decreased  fexofenadine  AUC by41% and cmax by 43%. DrugBank. False pos-itive. •  Dexamethasone  at 10(-10) M or retinyl acetate
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x