Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Motivation: Although there are several databases storing protein--protein interactions, most such data still exist only in the scientific literature. They are scattered in scientific literature written in natural languages, defying data mining efforts. Much time and labor have to be spent on extracting protein pathways from literature. Our aim is to develop a robust and powerful methodology to mine protein--protein interactions from biomedical texts. ::: ::: Results: We present a novel and robust approach for extracting protein--protein interactions from literature. Our method uses a dynamic programming algorithm to compute distinguishing patterns by aligning relevant sentences and key verbs that describe protein interactions. A matching algorithm is designed to extract the interactions between proteins. Equipped only with a dictionary of protein names, our system achieves a recall rate of 80.0% and precision rate of 80.5%. ::: ::: Availability: The program is available on request from the authors. <s> BIB001 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Motivation: To understand biological process, we must clarify how proteins interact with each other. However, since information about protein–protein interactions still exists primarily in the scientific literature, it is not accessible in a computer-readable format. Efficient processing of large amounts of interactions therefore needs an intelligent information extraction method. Our aim is to develop an efficient method for extracting information on protein–protein interaction from scientific literature. Results: We present a method for extracting information on protein–protein interactions from the scientific literature. This method, which employs only a protein name dictionary, surface clues on word patterns and simple part-ofspeech rules, achieved high recall and precision rates for yeast (recall = 86.8% and precision = 94.3%) and Escherichia coli (recall = 82.5% and precision = 93.5%). The result of extraction suggests that our method should be applicable to any species for which a protein name dictionary is constructed. Availability: The program is available on request from the authors. <s> BIB002 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Systems that extract structured information from natural language passages have been highly successful in specialized domains. The time is opportune for developing analogous applications for molecular biology and genomics. We present a system, GENIES, that extracts and structures information about cellular pathways from the biological literature in accordance with a knowledge model that we developed earlier. We implemented GENIES by modifying an existing medical natural language processing system, MedLEE, and performed a preliminary evaluation study. Our results demonstrate the value of the underlying techniques for the purpose of acquiring valuable knowledge from biological <s> BIB003 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Motivation: As research into disease pathology and cellular function continues to generate vast amounts of data pertaining to protein, gene and small molecule (PGSM) interactions, there exists a critical need to capture these results in structured formats allowing for computational analysis. Although many efforts have been made to create databases that store this information in computer readable form, populating these sources largely requires a manual process of interpreting and extracting interaction relationships from the biological research literature. Being able to efficiently and accurately automate the extraction of interactions from unstructured text, would greatly improve the content of these databases and provide a method for managing the continued growth of new literature being published. Results: In this paper, we describe a system for extracting PGSM interactions from unstructured text. By utilizing a lexical analyzer and context free grammar (CFG), we demonstrate that efficient parsers can be constructed for extracting these relationships from natural language with high rates of recall and precision. Our results show that this technique achieved a recall rate of 83.5% and a precision rate of 93.1% for recognizing PGSM names and a recall rate of 63.9% and a precision rate of 70.2% for extracting interactions between these entities. In contrast to other published techniques, the use of a CFG significantly reduces the complexities of natural language processing by focusing on domain specific structure as opposed to analyzing the semantics of a given language. Additionally, our approach provides a level of abstraction for adding new rules for extracting other types of biological relationships beyond PGSM relationships. Availability: The program and corpus are available by request from the authors. Contact: gilder@research.ge.com; jtemkin1@comcast.net <s> BIB004 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Motivation: An enormous number of protein--protein interaction relationships are buried in millions of research articles published over the years, and the number is growing. Rediscovering them automatically is a challenging bioinformatics task. Solutions to this problem also reach far beyond bioinformatics. ::: ::: Results: We study a new approach that involves automatically discovering English expression patterns, optimizing them and using them to extract protein--protein interactions. In a sister paper, we described how to generate English expression patterns related to protein--protein interactions, and this approach alone has already achieved precision and recall rates significantly higher than those of other automatic systems. This paper continues to present our theory, focusing on how to improve the patterns. A minimum description length (MDL)-based pattern-optimization algorithm is designed to reduce and merge patterns. This has significantly increased generalization power, and hence the recall and precision rates, as confirmed by ourexperiments. ::: ::: Availability: http://spies.cs.tsinghua.edu.cn ::: ::: Contact: zxy-dcs@tsinghua.edu.cn <s> BIB005 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Biology can be regarded as a science of networks: interactions between various biological entities (eg genes, proteins, metabolites) on different levels (eg gene regulation, cell signalling) can be represented as graphs and, thus, analysis of such networks might shed new light on the function of biological systems. Such biological networks can be obtained from different sources. The extraction of networks from text is an important technique that requires the integration of several different computational disciplines. This paper summarises the most important steps in network extraction and reviews common approaches and solutions for the extraction of biological networks from scientific literature. <s> BIB006 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> BackgroundPredicting the binding sites between two interacting proteins provides important clues to the function of a protein. Recent research on protein binding site prediction has been mainly based on widely known machine learning techniques, such as artificial neural networks, support vector machines, conditional random field, etc. However, the prediction performance is still too low to be used in practice. It is necessary to explore new algorithms, theories and features to further improve the performance.ResultsIn this study, we introduce a novel machine learning model hidden Markov support vector machine for protein binding site prediction. The model treats the protein binding site prediction as a sequential labelling task based on the maximum margin criterion. Common features derived from protein sequences and structures, including protein sequence profile and residue accessible surface area, are used to train hidden Markov support vector machine. When tested on six data sets, the method based on hidden Markov support vector machine shows better performance than some state-of-the-art methods, including artificial neural networks, support vector machines and conditional random field. Furthermore, its running time is several orders of magnitude shorter than that of the compared methods.ConclusionThe improved prediction performance and computational efficiency of the method based on hidden Markov support vector machine can be attributed to the following three factors. Firstly, the relation between labels of neighbouring residues is useful for protein binding site prediction. Secondly, the kernel trick is very advantageous to this field. Thirdly, the complexity of the training step for hidden Markov support vector machine is linear with the number of training samples by using the cutting-plane algorithm. <s> BIB007 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Motivation: Protein–protein interaction (PPI) extraction from published biological articles has attracted much attention because of the importance of protein interactions in biological processes. Despite significant progress, mining PPIs from literatures still rely heavily on time-and resource-consuming manual annotations. ::: ::: Results: In this study, we developed a novel methodology based on Bayesian networks (BNs) for extracting PPI triplets (a PPI triplet consists of two protein names and the corresponding interaction word) from unstructured text. The method achieved an overall accuracy of 87% on a cross-validation test using manually annotated dataset. We also showed, through extracting PPI triplets from a large number of PubMed abstracts, that our method was able to complement human annotations to extract large number of new PPIs from literature. ::: ::: Availability: Programs/scripts we developed/used in the study are available at http://stat.fsu.edu/~jinfeng/datasets/Bio-SI-programs-Bayesian-chowdhary-zhang-liu.zip ::: ::: Contact: jliu@stat.harvard.edu ::: ::: Supplementary information:Supplementary data are available at Bioinformatics online. <s> BIB008 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> BackgroundThe ability to predict protein-protein binding sites has a wide range of applications, including signal transduction studies, de novo drug design, structure identification and comparison of functional sites. The interface in a complex involves two structurally matched protein subunits, and the binding sites can be predicted by identifying structural matches at protein surfaces.ResultsWe propose a method which enumerates “all” the configurations (or poses) between two proteins (3D coordinates of the two subunits in a complex) and evaluates each configuration by the interaction between its components using the Atomic Contact Energy function. The enumeration is achieved efficiently by exploring a set of rigid transformations. Our approach incorporates a surface identification technique and a method for avoiding clashes of two subunits when computing rigid transformations. When the optimal transformations according to the Atomic Contact Energy function are identified, the corresponding binding sites are given as predictions. Our results show that this approach consistently performs better than other methods in binding site identification.ConclusionsOur method achieved a success rate higher than other methods, with the prediction quality improved in terms of both accuracy and coverage. Moreover, our method is being able to predict the configurations of two binding proteins, where most of other methods predict only the binding sites. The software package is available at http://sites.google.com/site/guofeics/dobi for non-commercial use. <s> BIB009 </s> Survey of Natural Language Processing Techniques in Bioinformatics <s> Extracting Protein-Protein <s> Protein-protein interactions play a key role in a multitude of biological processes, such as signal transduction, de novo drug design, immune responses, and enzymatic activities. It is of great interest to understand how proteins interact with each other. The general approach is to explore all possible poses and identify near-native ones with the energy function. The key issue here is to design an effective energy function, based on various physicochemical properties. In this paper, we first identify two new features, the coupled dihedral angles on the interfaces and the geometrical information on π-π interactions. We study these two features through statistical methods: a mixture of bivariate von Mises distributions is used to model the correlation of the coupled dihedral angles, while a mixture of bivariate normal distributions is used to model the orientation of the aromatic rings on π-π interactions. Using 6438 complexes, we parametrize the joint distribution of each new feature. Then, we propose a novel method to construct the energy function for protein-protein interface prediction, which includes the new features as well as the existing energy items such as dDFIRE energy, side-chain energy, atom contact energy, and amino acid energy. Experiments show that our method outperforms the state-of-the-art methods, ZRANK and ClusPro. We use the CAPRI evaluation criteria, Irmsd value, and Fnat value. On Benchmark v4.0, our method has an average Irmsd value of 3.39 Å and Fnat value of 62%, which improves upon the average Irmsd value of 3.89 Å and Fnat value of 49% for ZRANK, and the average Irmsd value of 3.99 Å and Fnat value of 46% for ClusPro. On the CAPRI targets, our method has an average Irmsd value of 3.56 Å and Fnat value of 42%, which improves upon the average Irmsd value of 4.27 Å and Fnat value of 39% for ZRANK, the average Irmsd value of 5.15 Å and Fnat value of 30% for ClusPro. <s> BIB010
Interactions. Extracting the protein interaction network is an important research topic in bioinformatics and systems biology BIB007 BIB010 BIB009  . In previous studies, researchers searched for protein-protein interactions manually. However, with the exponential growth of biological literature, a program that can recognize protein-protein interactions automatically from PubMed abstracts is necessary. Nevertheless, no unified naming rule for proteins has been established yet. Many proteins and genes use the same name. Consequently, recognizing protein names from the literature abstracts and further determining their interactions are key problems in the application of text mining in searching for protein-protein interactions. Initially, researchers extracted protein-protein interactions through statistical and counting methods. They manually created dictionaries of protein names and then searched abstracts that involve elements occurring at least twice. On this basis, researchers determined that associated proteins interact with one another BIB001 . Some researchers also used dynamic planning to extract and compare protein-protein interactions BIB005 . Extracting protein-protein interactions has been a research hot spot in bioinformatics for a long time and has attracted an increasing number of researchers in the fields of text mining and natural language processing. First, the grammar of literature abstracts is analyzed more carefully, rather than making a simple statistics of dictionary words. Kim et al. converted a complicated semantic structure analysis into calculating the shortest path in a graph by creating a nucleus  . Similar analysis methods of literature abstracts include grammatical analysis BIB002   BIB003 , context-free grammar analysis BIB004 , ontology analysis BIB006 , and other information retrieval methods. Protein-protein interactions are examined using these analysis methods. In addition, many machine learning methods, such as ensemble learning  and Bayesian network BIB008 , are applied to recognize protein names and interactions.