Automated Extraction of Bio-Entity Relationships from Literature

• US 20130339005A1
• Filed: 08/20/2013
• Published: 12/19/2013
• Est. Priority Date: 03/30/2012
• Status: Active Grant

• Current Assignee: Florida State University Research Foundation, Inc. (State University System of Florida)
• Original Assignee: Florida State University Research Foundation, Inc. (State University System of Florida)
• Inventors: Zhang, Jinfeng
• Granted Patent: US 8,886,522 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis

Abstract

Automated, standardized and accurate extraction of relationships within text. Automatic extraction of such relationships/information allows the information to be stored in structured form so that it can be easily and accurately retrieved when needed. Such information can be used to build online search engines for highly specific and accurate information retrieval. The current invention discloses a novel approach to extract such information from raw text based on natural language processing (NLP) and graph theoretic algorithm. The novel method can be applied, for example, to extract protein-protein relationships in biomedical literature. The method can be easily extended to extract other biological relationships between biological terms such as proteins, genes, pathways, diseases and drugs. The method can also be applied to other information domains to extract other relationships.

Claims

1. One or more non-transitory, tangible computer-readable media having computer-executable instructions for performing a method by running a software program on a computer, the computer operating under an operating system, the method including issuing instructions from the software program to extract semantic bio-entity relationships or patterns from non-annotated data by natural language processing and graph theoretic algorithm, the instructions comprising:

receiving a plurality of known bio-entity strings and a plurality of interaction word strings;

receiving annotated text as training data that contains true and false patterns;

automatically building a decision support tool based on said true and false patterns to which said non-annotated data can be parsed,

said decision support tool including at least a first level and a second level, said first level having a first decision node, said second level having a second decision node, said first and second decision nodes each associated with at least a portion of said true and false patterns;

receiving said non-annotated data;

extracting a textual clause of said non-annotated data that contains non-triplet word strings and at least one triplet, said at least one triplet including a first bio-entity, a second bio-entity, and an interaction word;

automatically parsing said extracted textual clause through said decision support tool to obtain a plurality of components based on dependencies among said plurality of components;

extracting said at least one triplet from said plurality of components by attempting to match said plurality of components of said parsed, extracted textual clause to said first level of said decision support tool;

identifying extraction of said at least one triplet as true if said plurality of components matches said first level of said decision support tool;

identifying extraction of said at least one triplet as false if said plurality of components fails to match said first level of said decision support tool;

as a result of said plurality of components failing to match said first level of said decision support tool, extracting said at least one triplet from said plurality of components by attempting to match said plurality of components to said second level of said decision support tool;

identifying extraction of said at least one triplet as true if said plurality of components matches said second level of said decision support tool, said second level of said decision support tool being a simplified pattern of said first level of said decision support tool to capture textual clauses that are not identical to said extracted textual clause; and

identifying extraction of said at least one triplet as false if said plurality of components fails to match said second level of said decision support tool.

2. One or more non-transitory, tangible computer-readable media as in claim 1, further comprising instructions for:

establishing a threshold probability value based on probable accuracy retrieved from said decision support tool;

said step of extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said first level, including;

tagging said extracted textual clause with a first probability value based on said accurate interaction between said extracted first and second bio-entities and said extracted interaction word within said first level;

classifying said at least one triplet as true as a result of said first probability value meeting said threshold probability value, and

classifying said at least one triplet as false as a result of said first probability value failing to meet said threshold probability value;

said step of extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said second level, including;

tagging said extracted textual clause with a second probability value based on said accurate interaction between said extracted first and second bio-entities and said extracted interaction word within said second level;

classifying said at least one triplet as true as a result of said second probability value meeting said threshold probability value, and

classifying said at least one triplet as false as a result of said second probability value failing to meet said threshold probability value.

3. One or more non-transitory, tangible computer-readable media as in claim 1, further comprising instructions for:

receiving a structured form format corresponding to said plurality of known bio-entity strings; and

storing said at least one extracted triplet in said structured form format as a result of a classification of said at least one extracted triplet being true, said storing facilitating retrieval of said at least one extracted, true triplet.

4. One or more non-transitory, tangible computer-readable media as in claim 1, further comprising:

said simplified pattern of said second level automatically created by replacing said non-triplet word strings with a wildcard that permits extraction of non-annotated data not containing said non-triplet word strings.

5. One or more non-transitory, tangible computer-readable media as in claim 1, further comprising instructions for:

establishing a third level in said hierarchical structure, said third level having a third decision node,

said third level being a further simplified pattern of said second level to capture triplets that are not identical to said at least one extracted triplet; and

as a result of said extracted textual clause failing to match said second level, extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said third level;

identifying extraction of said at least one triplet as true if said extracted textual clause matches said third level; and

identifying extraction of said at least one et as false if said extracted textual clause fails to match said third level.

6. One or more non-transitory, tangible computer-readable media as in claim 5, further comprising:

said further simplified pattern of said third level automatically created by grouping analogous interaction words with said interaction word to permit extraction of non-annotated data not containing said interaction word but containing one of said analogous interaction words.

7. One or more non-transitory, tangible computer-readable media as in claim 1, further comprising:

said first bio-entity being a first protein,

said second bio-entity being a second protein, and

said interaction word associating said first protein to said second protein.

8. One or more non-transitory, tangible computer-readable media as in claim 1, further comprising:

said decision support tool being a decision tree.

9. One or more non-transitory, tangible computer-readable media as in claim 1, further comprising:

the step of automatically building said decision support tool further based on relationships among additional dependencies among said true and false patterns in said annotated data.

10. A computer-implemented method of extracting semantic bio-entity relationships or patterns from non-annotated data by natural language processing and graph theoretic algorithm, comprising the steps of:

receiving a plurality of known bio-entity strings and a plurality of interaction word strings;

receiving annotated text as training data that contains true and false patterns;

automatically building a decision support tool based on said true and false patterns to which said non-annotated data can be parsed,

said decision support tool including at least a first level and a second level, said first level having a first decision node, said second level having a second decision node, said first and second decision nodes each associated with at least a portion of said true and false patterns;

receiving said non-annotated data;

extracting a textual clause of said non-annotated data that contains non-triplet word strings and at least one triplet, said at least one triplet including a first bio-entity, a second bio-entity, and an interaction word;

automatically parsing said extracted textual clause through said decision support tool to obtain a plurality of components based on dependencies among said plurality of components;

extracting said at least one triplet from said plurality of components by attempting to match said plurality of components of said parsed, extracted textual clause to said first level of said decision support tool;

identifying extraction of said at least one triplet as true if said plurality of components matches said first level of said decision support tool;

identifying extraction of said at least one triplet as false if said plurality of components fails to match said first level of said decision support tool;

as a result of said plurality of components failing to match said first level of said decision support tool, extracting said at least one triplet from said plurality of components by attempting to match said plurality of components to said second level of said decision support tool;

identifying extraction of said at least one triplet as true if said plurality of components matches said second level of said decision support tool, said second level of said decision support tool being a simplified pattern of said first level of said decision support tool to capture textual clauses that are not identical to said extracted textual clause; and

identifying extraction of said at least one triplet as false if said plurality of components fails to match said second level of said decision support tool.

11. A computer-implemented method as in claim 10, further comprising instructions for:

establishing a threshold probability value based on probable accuracy retrieved from said decision support tool;

said step of extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said first level, including;

tagging said extracted textual clause with a first probability value based on said accurate interaction between said extracted first and second bio-entities and said extracted interaction word within said first level;

classifying said at least one triplet as true as a result of said first probability value meeting said threshold probability value, and

classifying said at least one triplet as false as a result of said first probability value failing to meet said threshold probability value;

said step of extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said second level, including;

tagging said extracted textual clause with a second probability value based on said accurate interaction between said extracted first and second bio-entities and said extracted interaction word within said second level;

classifying said at least one triplet as true as a result of, aid second probability value meeting said threshold probability value, and

classifying said at least one triplet as false as a result of said second probability value failing to meet said threshold probability value.

12. A computer-implemented method as in claim 10, further comprising instructions for:

receiving a structured form format corresponding to said plurality of known bio-entity strings; and

storing said at least one extracted triplet in said structured form format as a result of a classification of said at least one extracted triplet being true, said storing facilitating retrieval of said at least one extracted, true triplet.

13. A computer-implemented method as in claim 10, further comprising:

said simplified pattern of said second level automatically created by replacing said non-triplet word strings with a wildcard that permits extraction of non-annotated data not containing said non-triplet word strings.

14. A computer-implemented method as in claim 10, further comprising instructions for:

establishing a third level in said hierarchical structure, said third level having a third decision node,

said third level being a further simplified pattern of said second level to capture triplets that are not identical to said at least one extracted triplet,

said third decision node having a different level of detail than said first and second decision nodes; and

as a result of said extracted textual clause failing to match said second level, extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said third level;

identifying extraction of said at least one triplet as true if said extracted textual clause matches said third level; and

identifying extraction of said at least one triplet as false if said extracted textual clause fails to match said third level.

15. A computer-implemented method as in claim 14, further comprising:

said further simplified pattern of said third level automatically created by grouping analogous interaction words with said interaction word to permit extraction of non-annotated data not containing said interaction word but containing one of said analogous interaction words.

16. A computer-implemented method as in claim 10, further comprising:

said first bio-entity being a first protein,

said second bio-entity being a second protein, and

said interaction word associating said first protein to said second protein.

17. A computer-implemented method as in claim 10, further comprising:

said decision support tool being a decision tree.

18. A computer-implemented method as in claim 10, further comprising:

the step of automatically building said decision support tool further based on relationships among additional dependencies among said true and false patterns in said annotated data.

19. One or more non-transitory, tangible computer-readable media having computer-executable instructions for performing a method by running a software program on a computer, the computer operating under an operating system, the method including issuing instructions from the software program to extract textual relationships or semantic information from non-annotated data by natural language processing and graph theoretic algorithm the instructions comprising:

receiving a plurality of known textual strings and a plurality of interaction word strings;

receiving annotated text as training data that contains true and false patterns;

automatically building a decision support tool based on said true and false patterns to which said non-annotated data can be parsed,

said decision support tool including at least a first level and a second level, said first level having a first decision node, said second level having a second decision node, said first and second decision nodes each associated with at least a portion of said true and false patterns;

receiving said non-annotated data;

extracting a textual clause of said non-annotated data that contains non-triplet word strings and at least one triplet, said at least one triplet including a first textual string, a second textual string, and an interaction word;

automatically parsing said extracted textual clause through said decision support tool to obtain a plurality of components based on dependencies among said plurality of components,

extracting said at least one triplet from said plurality of components by attempting to match said plurality of components of said parsed, extracted textual clause to said first level of said decision support tool;

identifying extraction of said at least one triplet as true if said extracted textual clause matches said first level of said decision support tool;

identifying extraction of said at least one triplet as false if said extracted textual clause fails to match said first level of said decision support tool;

as a result of said plurality of components failing to match said first level of said decision support tool, extracting said at least one triplet from said plurality of components by attempting to match said plurality of components to said second level of said decision support tool;

identifying extraction of said at least one triplet as true if said plurality of components matches said second level of said decision support tool, said second level of said decision support tool being a simplified pattern of said first level of said decision support tool to capture textual clauses that are not identical to said extracted textual clause; and

identifying extraction of said at least one triplet as false if said plurality of components fails to match said second level of said decision support tool.

20. A computer-implemented software application as in claim 19, further comprising instructions for:

establishing a threshold probability value based on probable accuracy retrieved from said decision support tool;

said step of extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said first level, including;

tagging said extracted textual clause with a first probability value based on said accurate interaction between said extracted first and second bio-entities and said extracted interaction word within said first level;

classifying said at least one triplet as true as a result of said first probability value meeting said threshold probability value, and

classifying said at least one triplet as false as a result of said first probability value failing to meet said threshold probability value;

said step of extracting said at least one triplet from said extracted textual clause by attempting to match said extracted textual clause to said second level, including;

tagging said extracted textual clause with a second probability value based on said accurate interaction between said extracted first and second bio-entities and said extracted interaction word within said second level;

classifying said at least one triplet as true as a result of said second probability value meeting said threshold probability value, and

classifying said at least one triplet as false as a result of said second probability value failing to meet said threshold probability value.

21. (canceled)