An important task in biological information extraction is to identify descriptions of biological relations and events involving genes or proteins. We propose a graph-based approach to automatically learn rules for detecting biological events in the literature. The detection is performed by searching for isomorphism between event rules and the dependency graphs of complete sentences. When applying our approach to the datasets of the Task 1 of the BioNLP shared task, we achieved an 37.28% F-score in detecting biological events across 9 event types.
Recent research in information extraction in the
biological domain has focused on extracting semantic
relations between molecular biology concepts
Sentences in the biological literature often have
long-range dependencies. Therefore, co-occurrence
based or surface pattern based shallow analysis on
biological texts suffers from either low precision or recall
More recently, the dependency representation
obtained from full parsing, with its ability to reveal
longrange dependencies, has shown an advantage in
biological relation extraction over the traditional Penn
Treebank-style phrase structure trees
Graphs provide a powerful primitive for modeling
biological data such as pathways and protein
interaction networks
The rest of the paper is organized as follows: In Section 2, we introduce the BioNLP’09 shared task on event extraction. Section 3 describes our subgraph matching-based event extraction method. Sections 4 elaborates the implementation details. Performance is evaluated in Section 5. Finally, Section 6 summarizes the paper and introduces future work. 2
The BioNLP’09 shared task
Definition 1. A biological event is a four-tuple e = (Type, Trigger, Arguments, ST). ST ∈ W ∗, called the source text, is a sequence of tokens that contains the event; Type ∈ Te is an event type from a finite set of event types Te; Trigger is a substring of tokens from ST that signals the event; Arguments is a non-empty, finite set of pairs (l, a) where l ∈ L is a label from a finite set of semantic role labels L, and a is a token from ST, or another biological event.
For the shared task, Te consists of nine event types defined in Table 1, and L = {Theme, Cause}. A gold event denotes a biological event where all the information has been manually annotated by domain experts.
The primary task of the shared task was to detect biological events such as protein binding and phosphorylation, given only the annotation of protein names. It was required to extract type, trigger, and primary arguments of each event. This task is an example of extraction of semantically typed, complex events for which the arguments can also be other events. We focus on the primary task and propose a graph matching-based method to cope with the problem.
Subgraph Matching-based Event Extraction 3.1
The dependency representation is designed to provide a
simple description of the grammatical relationships in
a sentence that can be effectively used to extract textual
relations
The dependency representation of a sentence is formed by tokens in the sentence and the binary relations between them. A single dependency relation is represented as relation(governor, dependent), where governor and dependent are tokens, and relation is a type of the grammatical dependency relation. A dependency representation is essentially a labeled directed graph, which is named dependency graph. 3.2
A biological event rule is defined as follows:
Definition 2. A biological event rule is a pair r = (e, Gr). Gr = (Vr, Er) is a dependency graph, which characterizes the contextual structure of events. e = (Type, Trigger, Arguments) encodes a detailed event frame, where Type is the event type, Trigger = {(t1, v1), (t2, v2), · · ·} records the event trigger and is a non-empty finite sequence of tokens associated with nodes in Gr, i.e., Trigger ∈ (W × Vr)+, and Arguments = {(t1, l1, v1), (t2, l2, v2), · · ·} records the event arguments and is a non-empty finite sequence of tokens associated with semantic role labels and nodes in Gr, i.e., Arguments ∈ (W × L × Vr)+.
The biological event rules are learned from labeled training sentences using the following induction method. Starting with the dependency graph of each training sentence, the directions of edges are first removed so that the directed graph is transformed into an undirected graph, where a path must exist between any two nodes since the graph is always connected. For each gold event, the shortest dependency path in the undirected graph connecting the event trigger nodes to each event argument node is selected. The union of all shortest dependency paths is then computed for each event, and the original directed dependency representation of the path union is retrieved and used as the graph representation of the event.
For multi-token event triggers, the shortest dependency path connecting the node of every trigger token to the node of each event argument is selected, and the union of the paths is then computed for each trigger. For regulation events, when a sub-event is used as an argument, only the type and the trigger of the sub-event are preserved as the argument of the main events. The shortest dependency path is extracted so as to connect the trigger nodes of the main event to the trigger nodes of the sub-event. In case that there exists more than one shortest path, all of the paths are considered. As a result, each gold event is transformed into the form of a biological event rule. The obtained rules are categorized in terms of the nine event types of the task.
We propose a sentence matching approach to attempt to match event rules to each testing sentence. Since the event rules and the sentences all possess a dependency graph, the matching process is a subgraph matching problem, which corresponds to the search for a subgraph isomorphic to an event rule graph within the graph of a testing sentence. This problem is also called subgraph isomorphism, defined in this work as follows:
Definition 3. An event rule graph Gr = (Vr, Er) is isomorphic to a subgraph of a sentence graph Gs = (Vs, Es), denoted by Gr =∼ Ss ⊆ Gs, if there is an injective mapping f : Vr → Vs such that, for every directed pair of nodes vi, vj ∈ Vr, if (vi, vj ) ∈ Er then (f (vi), f (vj )) ∈ Es, and the edge label of (vi, vj ) is the same as the edge label of (f (vi), f (vj )).
The subgraph isomorphism problem is NP-complete
For each sentence, the algorithm returns all the matched rules together with the corresponding injective mappings from rule nodes to sentence tokens. Biological events are then extracted by applying the event descriptions of tokens in each matched rule such as the type to the corresponding tokens of the sentence. In practice, it only takes the algorithm a couple of seconds to return the results.
We assume that a sentence is a suitable level of text granularity in event extraction. The target text is first segmented into sentences. Then, each sentence is tokenized with whitespace separating tokens. We require that every protein be separated from surrounding text and become one individual token. All the protein
Input: Dependency graph of a testing sentence s, Gs = (Vs, Es) where Vs is the set of nodes and Es is the set of edges of the graph; a finite set of biological event rules R = {r1, r2, · · · , ri, · · ·}, where ri = (ei, Gri ). Gri = (Vri , Eri ) is the dependency graph of ri.
Output: MR : a set of biological event rules from R matched with s together with the injective mapping Main algorithm: 1: MR ← ∅ 2: for all ri ∈ R do 3: stri ← StartNode(Gri ) //StartNode finds the start 4: //node stri of the rule graph Gri 5: STs ← {sts1 , sts2 , · · · , stsj , · · ·} 6: //STs : the set of start nodes of the sentence graph Gs 7: for all stsj ∈ STs do 8: create an empty stack σ and push (stri , stsj ) onto 9: the stack σ 10: IM ← ∅ //IM : records of injective matches 11: //between nodes in Gri and Gs 12: call MatchNode(σ, rIM, Gri , Gs) 13: //rIM : reference of IM 14: if MatchNode returned TRUE then 15: MR ← MR ∪ {ri with IM } 16: return MR names are replaced with a unified tag “BIO Entity”.
GENIA tagger
For each gold event, the shortest path in the
undirected graph connecting the event trigger to each event
argument is extracted using the Dijkstra’s algorithm
We use the BioNLP’09 Shared Task datasets for
evaluation. A training set and a development set are provided
for the purpose of developing task solution. They are
prepared based on the publicly available portion of the
GENIA event corpus
Table 1 shows the nine event types considered in the
Recursive subroutine: MatchNode(σ, rIMparent, Gri , Gs) 1: IMcurrent ← IMparent //assign IMparent from the 2: //parent level to the current IMcurrent 3: while stack σ is not empty do 4: pop node pair (vr, vs) from stack σ 5: if an injective match between vr and vs already exists 6: in IMcurrent then 7: do nothing 8: else if an injective match is possible between vr and 9: vs then 10: IMcurrent ← IMcurrent ∪ { the match between 11: vr and vs } 12: else 13: return FALSE 14: for all edges er adjacent to node vr in Gri do 15: let (vr, nr) be the edge er 16: for all edges es adjacent to node vs in Gs do 17: let (vs, ns) be the edge es 18: if er and es share a same direction and 19: possess identical edge labels then 20: S ← S ∪ ns //S : the set of candidate 21: //nodes for matching nr 22: for all ns ∈ S do 23: if an injective match between nr and ns 24: already exists in IMcurrent then 25: go to Line 14 and proceed with next edge er 26: else if an injective match is possible between 27: nr and ns then 28: σn ← σ //copy σ to a new stack σn 29: push (vr, vs, nr, ns) onto the stack σn 30: call MatchNode(σn, rIMcurrent, Gri , Gs) 31: //rIMcurrent : reference of IMcurrent 32: if MatchNode returned TRUE then 33: IMparent ← IMcurrent 34: //update IMparent using IMcurrent 35: return TRUE 36: return FALSE 37: IMparent ← IMcurrent 38: return TRUE shared task. Since these types are all related to protein biology, they take proteins (P) as their theme. Regulation events always take a theme argument and, when expressed, also a cause argument. As a unique feature of the shared task, regulation events may take another event (E), namely sub-event, as its theme or cause. 5.2
For training data, only sentences that contain at least one protein and one event are considered candidates for further processing. For testing data, candidate sentences contain at least one protein. Our proposed graph matching-based method focuses on extracting biological events from sentences. Therefore, only sentencebased events are considered in this work. After removing duplicate rules, we obtained 6,435 event rules, which are distributed over nine event types.
We observed that some event rules of an event type are overlapped with rules of other event types. For instance, a Transcription rule is isomorphic to a Gene expression rule in terms of the graph representation and they also share a same event trigger token. In fact, tokens like “gene expression” and “induction” are used as event trigger of both Transcription and Gene expression in training data. Therefore, the detection of some Gene expression events is always accompanied by certain Transcription events.
In tackling this problem, we processed the rules and built a non-overlapping rule set. When the dependency graphs of two rules across different event types are isomorphic to each other and two rules share a same event trigger token, we keep the rule of the event type in which the trigger token of the rule occurs more frequent as a trigger in the training data, and remove the rule of the other event type from the set. The non-overlapping rule sets in terms of different combinations of matching features are then applied to the 988 candidate development sentences using our graph matching algorithm. Table 2 shows the event extraction results based on each feature.
The least specific matching criterion when matching between rules and sentences is “E”, which assumes that, without checking any information about nodes, as long as edge directions and labels are the same, both edges and nodes of a rule and a sentence can match with each other. It achieves the highest recall among all the runs and captures more than half of the gold events in the sentences. However, the precision is quite low, leading to a low F-score as too many false positives are generated due to the disregard of node information.
As the strictest matching criteria, “E+P+A” requires that the edges (E), the POS tags (P) and all tokens (A) be exactly the same for the edges and the nodes of a rule and a sentence to match with each other. It achieves the highest precision 69.72% and an F-score over 40%. This indicates that a certain number of biological events are described in very similar way in the literature, involving the same grammatical structures and identical contextual contents. Comparing to “P+A”, adding the edge features improves the overall precision of event extraction by a large margin, nearly 13%. “E+P+T” requires that edge directions and labels of all edges be identical, POS tags of all tokens be identical, and tokens of only event triggers (T) be identical. It achieves better performance than “E+P+A” when relaxing the matching criteria from all tokens being the same to only event trigger tokens having to be identical. The best 2 of the first 6 runs in Table 2 are “E+P+T” and “P+A”.
Next, we attempted to relax the matching criterion of POS tags for nouns and verbs. For nouns, the plural form of nouns is allowed to match with the singular form, and proper nouns are allowed to match with regular nouns. For verbs, past tense, present tense and base present form are allowed to match with each other. Further, the event trigger tokens are stemmed to their root forms allowing the trigger tokens derived from a same root word to match. “E+P*+T*” and “P*+A+T*” in Table 2 demonstrate the improved performance to the above best two runs. These modifications improve the recall but produce many incorrect events, leading to only a small increase on the overall F-score.
E E+P E+P+A E+P+T P+A P+T E+P*+T* P*+A+T*
Prec.(%) 1.22 2.23 69.72 58.85 57.00 40.65 50.86 51.51
Recall(%) 52.26 45.33 28.06 31.02 32.53 36.95 34.71 35.22 We decided to conduct four runs on the testing sentences in terms of 4 features: “E”, “E+P+A”, “E+P*+T*” and “P*+A+T*”. For “E” and “E+P+A”, aiming to investigate the highest recall and precision on the testing sentences that can be achieved by our method. Table 3 gives the event extraction results on the 1,670 testing sentences in terms of the 4 features.
E E+P+A E+P*+T* P*+A+T*
“E+P*+T*” achieves the best overall F-score of 37.28% among all the runs. Similarly to the development set, the highest precision 58.64% on the testing sentences is achieved by the strictest matching criteria “E+P+A”. The highest recall 52.17% is obtained by the least specific matching criterion “E”, indicating that a large amount of biological events is described in quite different grammatical structures in the literature. Although “P*+A+T*” produced the best performance on the development set, it does not perform as well on the testing set. This clearly suggests that when requiring every token to be exactly the same for matching nodes of a rule and a sentence, the event rules have less stable generalization power to capture the underlying events.
Table 4 gives the performance comparison of our method with top-performing teams in the task. The official evaluation shows that our best results would rank 6th in extracting biological events in the testing data compared to the results of the 24 participating teams.
UTurku JULIELab ConcordU UT+DBCLS VIBGhent DalhousieU UTokyo UNSW conducted the experiments to tackle the primary task of the BioNLP shared task, and our method achieves an 37.28% F-score on the testing data in detecting biological events across nine event types.
In future work, we would like to experiment with more matching criteria when mapping event rules to sentences. We also plan to expand the coverage of event trigger tokens using external lexical resources for new event triggers and synonyms of existing triggers.