Enhancing interacting residue prediction with integrated contact matrix prediction in protein-protein interaction

Identifying the residues in a protein that are involved in protein-protein interaction and identifying the contact matrix for a pair of interacting proteins are two computational tasks at different levels of an in-depth analysis of protein-protein interaction. Various methods for solving these two problems have been reported in the literature. However, the interacting residue prediction and contact matrix prediction were handled by and large independently in those existing methods, though intuitively good prediction of interacting residues will help with predicting the contact matrix. In this work, we developed a novel protein interacting residue prediction system, contact matrix-interaction profile hidden Markov model (CM-ipHMM), with the integration of contact matrix prediction and the ipHMM interaction residue prediction. We propose to leverage what is learned from the contact matrix prediction and utilize the predicted contact matrix as “feedback” to enhance the interaction residue prediction. The CM-ipHMM model showed significant improvement over the previous method that uses the ipHMM for predicting interaction residues only. It indicates that the downstream contact matrix prediction could help the interaction site prediction.     

Predicting protein interaction sites from residue spatial sequence profile and evolution rate

This paper proposes a novel method that can predict protein interaction sites in heterocomplexes using residue spatial sequence profile and evolution rate approaches. The former represents the information of multiple sequence alignments while the latter corresponds to a residue's evolutionary conservation score based on a phylogenetic tree. Three predictors using a support vector machines algorithm are constructed to predict whether a surface residue is a part of a protein-protein interface. The efficiency and the effectiveness of our proposed approach is verified by its better prediction performance compared with other models. The study is based on a non-redundant data set of heterodimers consisting of 69 protein chains.     

ToPS: A Framework to Manipulate Probabilistic Models of Sequence Data

Discrete Markovian models can be used to characterize patterns in sequences of values and have many applications in biological sequence analysis, including gene prediction, CpG island detection, alignment, and protein profiling. We present ToPS, a computational framework that can be used to implement different applications in bioinformatics analysis by combining eight kinds of models: (i) independent and identically distributed process; (ii) variable-length Markov chain; (iii) inhomogeneous Markov chain; (iv) hidden Markov model; (v) profile hidden Markov model; (vi) pair hidden Markov model; (vii) generalized hidden Markov model; and (viii) similarity based sequence weighting. The framework includes functionality for training, simulation and decoding of the models. Additionally, it provides two methods to help parameter setting: Akaike and Bayesian information criteria (AIC and BIC). The models can be used stand-alone, combined in Bayesian classifiers, or included in more complex, multi-model, probabilistic architectures using GHMMs. In particular the framework provides a novel, flexible, implementation of decoding in GHMMs that detects when the architecture can be traversed efficiently.

This is a PLOS Computational Biology Software Article.

     

SuperStar: comparison of CSD and PDB-based interaction fields as a basis for the prediction of protein-ligand interactions.

SuperStar is an empirical method for identifying interaction sites in proteins, based entirely on the experimental information about non-bonded interactions, present in the IsoStar database. The interaction information in IsoStar is contained in scatterplots, which show the distribution of a chosen probe around structure fragments. SuperStar breaks a template molecule (e.g. a protein binding site) into structural fragments which correspond to those in the scatterplots. The scatterplots are then superimposed on the corresponding parts of the template and converted into a composite propensity map.The original version of SuperStar was based entirely on scatterplots from the CSD. Here, scatterplots based on protein-ligand interactions are implemented in SuperStar, and validated on a test set of 122 X-ray structures of protein-ligand complexes. In this validation, propensity maps are compared with the experimentally observed positions of ligand atoms of comparable types. Although non-bonded interaction geometries in small molecule structures are similar to those found in protein-ligand complexes, their relative frequencies of occurrence are different. Polar interactions are more common in the first class of structures, while interactions between hydrophobic groups are more common in protein crystals. In general, PDB and CSD-based SuperStar maps appear equally successful in the prediction of protein-ligand interactions. PDB-based maps are more suitable to identify hydrophobic pockets, and inherently take into account the experimental uncertainties of protein atomic positions. If the protonation state of a histidine, aspartate or glutamate protein side-chain is known, specific CSD-based maps for that protonation state are preferred over PDB-based maps which represent an ensemble of protonation states.     

A novel approach to remote homology detection: jumping alignments.

We describe a new algorithm for protein classification and the detection of remote homologs. The rationale is to exploit both vertical and horizontal information of a multiple alignment in a well-balanced manner. This is in contrast to established methods such as profiles and profile hidden Markov models which focus on vertical information as they model the columns of the alignment independently and to family pairwise search which focuses on horizontal information as it treats given sequences separately. In our setting, we want to select from a given database of "candidate sequences" those proteins that belong to a given superfamily. In order to do so, each candidate sequence is separately tested against a multiple alignment of the known members of the superfamily by means of a new jumping alignment algorithm. This algorithm is an extension of the Smith-Waterman algorithm and computes a local alignment of a single sequence and a multiple alignment. In contrast to traditional methods, however, this alignment is not based on a summary of the individual columns of the multiple alignment. Rather, the candidate sequence is at each position aligned to one sequence of the multiple alignment, called the "reference sequence." In addition, the reference sequence may change within the alignment, while each such jump is penalized. To evaluate the discriminative quality of the jumping alignment algorithm, we compare it to profiles, profile hidden Markov models, and family pairwise search on a subset of the SCOP database of protein domains. The discriminative quality is assessed by median false positive counts (med-FP-counts). For moderate med-FP-counts, the number of successful searches with our method is considerably higher than with the competing methods.     

Protein complex prediction based on maximum matching with domain-domain interaction

With the development of high-throughput methods for identifying protein-protein interactions, large scale interaction networks are available. Computational methods to analyze the networks to detect functional modules as protein complexes are becoming more important. However, most of the existing methods only make use of the protein-protein interaction networks without considering the structural limitations of proteins to bind together. In this paper, we design a new protein complex prediction method by extending the idea of using domain-domain interaction information. Here we formulate the problem into a maximum matching problem (which can be solved in polynomial time) instead of the binary integer linear programming approach (which can be NP-hard in the worst case). We also add a step to predict domain-domain interactions which first searches the database Pfam using the hidden Markov model and then predicts the domain-domain interactions based on the database DOMINE and InterDom which contain confirmed DDIs. By adding the domain-domain interaction prediction step, we have more edges in the DDI graph and the recall value is increased significantly (at least doubled) comparing with the method of Ozawa et al. (2010) [1] while the average precision value is slightly better. We also combine our method with three other existing methods, such as COACH, MCL and MCODE. Experiments show that the precision of the combined method is improved. This article is part of a Special Issue entitled: Computational Methods for Protein Interaction and Structural Prediction.     

Protein-protein interaction site prediction based on conditional random fields

MOTIVATION: We are motivated by the fast-growing number of protein structures in the Protein Data Bank with necessary information for prediction of protein-protein interaction sites to develop methods for identification of residues participating in protein-protein interactions. We would like to compare conditional random fields (CRFs)-based method with conventional classification-based methods that omit the relation between two labels of neighboring residues to show the advantages of CRFs-based method in predicting protein-protein interaction sites. RESULTS: The prediction of protein-protein interaction sites is solved as a sequential labeling problem by applying CRFs with features including protein sequence profile and residue accessible surface area. The CRFs-based method can achieve a comparable performance with state-of-the-art methods, when 1276 nonredundant hetero-complex protein chains are used as training and test set. Experimental result shows that CRFs-based method is a powerful and robust protein-protein interaction site prediction method and can be used to guide biologists to make specific experiments on proteins. AVAILABILITY: http://www.insun.hit.edu.cn/~mhli/site_CRFs/index.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.     

Probabilistic prediction of Saccharomyces cerevisiae mRNA 3'-processing sites

We present a tool for the prediction of mRNA 3′-processing (cleavage and polyadenylation) sites in the yeast Saccharomyces cerevisiae, based on a discrete state-space model or hidden Markov model. Comparison of predicted sites with experimentally verified 3′-processing sites indicates good agreement. All predicted or known yeast genes were analyzed to find probable 3′-processing sites. Known alternative 3′-processing sites, both within the 3′-untranslated region and within the protein coding sequence were successfully identified, leading to the possibility of prediction of previously unknown alternative sites. The lack of an apparent 3′-processing site calls into question the validity of some predicted genes. This is specifically investigated for predicted genes with overlapping coding sequences.     

Bayesian restoration of a hidden Markov chain with applications to DNA sequencing.

Hidden Markov models (HMMs) are a class of stochastic models that have proven to be powerful tools for the analysis of molecular sequence data. A hidden Markov model can be viewed as a black box that generates sequences of observations. The unobservable internal state of the box is stochastic and is determined by a finite state Markov chain. The observable output is stochastic with distribution determined by the state of the hidden Markov chain. We present a Bayesian solution to the problem of restoring the sequence of states visited by the hidden Markov chain from a given sequence of observed outputs. Our approach is based on a Monte Carlo Markov chain algorithm that allows us to draw samples from the full posterior distribution of the hidden Markov chain paths. The problem of estimating the probability of individual paths and the associated Monte Carlo error of these estimates is addressed. The method is illustrated by considering a problem of DNA sequence multiple alignment. The special structure for the hidden Markov model used in the sequence alignment problem is considered in detail. In conclusion, we discuss certain interesting aspects of biological sequence alignments that become accessible through the Bayesian approach to HMM restoration.     

Predicting allergenic proteins using wavelet transform

MOTIVATION: With many transgenic proteins introduced today, the ability to predict their potential allergenicity has become an important issue. Previous studies were based on either sequence similarity or the protein motifs identified from known allergen databases. The similarity-based approaches, although being able to produce high recalls, usually have low prediction precisions. Previous motif-based approaches have been shown to be able to improve the precisions on cross-validation experiments. In this study, a system that combines the advantages of similarity-based and motif-based prediction is described. RESULTS: The new prediction system uses a clustering algorithm that groups the known allergenic proteins into clusters. Proteins within each cluster are assumed to carry one or more common motifs. After a multiple sequence alignment, proteins in each cluster go through a wavelet analysis program whereby conserved motifs will be identified. A hidden Markov model (HMM) profile will then be prepared for each identified motif. The allergens that do not appear to carry detectable allergen motifs will be saved in a small database. The allergenicity of an unknown protein may be predicted by comparing it against the HMM profiles, and, if no matching profiles are found, against the small allergen database by BLASTP. Over 70% of recall and over 90% of precision were observed using cross-validation experiments. Using the entire Swiss-Prot as the query, we predicted about 2000 potential allergens. AVAILABILITY: The software is available upon request from the authors.     

PredSL： A Tool for the N-terminal Sequence-based Prediction of Protein Subcellular Localization

The ability to predict the subcellular localization of a protein from its sequence is of great importance, as it provides information about the protein＇s function. We present a computational tool, PredSL, which utilizes neural networks, Markov chains, profile hidden Markov models, and scoring matrices for the prediction of the subcellular localization of proteins in eukaryotic cells from the N-terminal amino acid sequence. It aims to classify proteins into five groups： chloroplast, thylakoid, mitochondrion, secretory pathway, and ＂other＂. When tested in a fivefold cross-validation procedure, PredSL demonstrates 86.7% and 87.1% overall accuracy for the plant and non-plant datasets, respectively. Compared with TargetP, which is the most widely used method to date, and LumenP, the results of PredSL are comparable in most cases. When tested on the experimentally verified proteins of the Saccharomyces cerevisiae genome, PredSL performs comparably if not better than any available algorithm for the same task. Furthermore, PredSL is the only method capable for the prediction of these subcellular localizations that is available as a stand-alone application through the URL： http：//bioinformatics.biol.uoa.gr/PredSL/.     

On the packing density of the unbound protein-protein interaction interface and its implications in dynamics

Background

In eukaryotes, ubiquitin-conjugation is an important mechanism underlying proteasome-mediated degradation of proteins, and as such, plays an essential role in the regulation of many cellular processes. In the ubiquitin-proteasome pathway, E3 ligases play important roles by recognizing a specific protein substrate and catalyzing the attachment of ubiquitin to a lysine (K) residue. As more and more experimental data on ubiquitin conjugation sites become available, it becomes possible to develop prediction models that can be scaled to big data. However, no development that focuses on the investigation of ubiquitinated substrate specificities has existed. Herein, we present an approach that exploits an iteratively statistical method to identify ubiquitin conjugation sites with substrate site specificities.

Results

In this investigation, totally 6259 experimentally validated ubiquitinated proteins were obtained from dbPTM. After having filtered out homologous fragments with 40% sequence identity, the training data set contained 2658 ubiquitination sites (positive data) and 5532 non-ubiquitinated sites (negative data). Due to the difficulty in characterizing the substrate site specificities of E3 ligases by conventional sequence logo analysis, a recursively statistical method has been applied to obtain significant conserved motifs. The profile hidden Markov model (profile HMM) was adopted to construct the predictive models learned from the identified substrate motifs. A five-fold cross validation was then used to evaluate the predictive model, achieving sensitivity, specificity, and accuracy of 73.07%, 65.46%, and 67.93%, respectively. Additionally, an independent testing set, completely blind to the training data of the predictive model, was used to demonstrate that the proposed method could provide a promising accuracy (76.13%) and outperform other ubiquitination site prediction tool.

Conclusion

A case study demonstrated the effectiveness of the characterized substrate motifs for identifying ubiquitination sites. The proposed method presents a practical means of preliminary analysis and greatly diminishes the total number of potential targets required for further experimental confirmation. This method may help unravel their mechanisms and roles in E3 recognition and ubiquitin-mediated protein degradation.

     

Protein homology detection by HMM-HMM comparison

MOTIVATION: Protein homology detection and sequence alignment are at the basis of protein structure prediction, function prediction and evolution. RESULTS: We have generalized the alignment of protein sequences with a profile hidden Markov model (HMM) to the case of pairwise alignment of profile HMMs. We present a method for detecting distant homologous relationships between proteins based on this approach. The method (HHsearch) is benchmarked together with BLAST, PSI-BLAST, HMMER and the profile-profile comparison tools PROF_SIM and COMPASS, in an all-against-all comparison of a database of 3691 protein domains from SCOP 1.63 with pairwise sequence identities below 20%.Sensitivity: When the predicted secondary structure is included in the HMMs, HHsearch is able to detect between 2.7 and 4.2 times more homologs than PSI-BLAST or HMMER and between 1.44 and 1.9 times more than COMPASS or PROF_SIM for a rate of false positives of 10%. Approximately half of the improvement over the profile-profile comparison methods is attributable to the use of profile HMMs in place of simple profiles. Alignment quality: Higher sensitivity is mirrored by an increased alignment quality. HHsearch produced 1.2, 1.7 and 3.3 times more good alignments ('balanced' score >0.3) than the next best method (COMPASS), and 1.6, 2.9 and 9.4 times more than PSI-BLAST, at the family, superfamily and fold level, respectively.Speed: HHsearch scans a query of 200 residues against 3691 domains in 33 s on an AMD64 2GHz PC. This is 10 times faster than PROF_SIM and 17 times faster than COMPASS.     

Protein complex prediction based on maximum matching with domain–domain interaction

With the development of high-throughput methods for identifying protein–protein interactions, large scale interaction networks are available. Computational methods to analyze the networks to detect functional modules as protein complexes are becoming more important. However, most of the existing methods only make use of the protein–protein interaction networks without considering the structural limitations of proteins to bind together. In this paper, we design a new protein complex prediction method by extending the idea of using domain–domain interaction information. Here we formulate the problem into a maximum matching problem (which can be solved in polynomial time) instead of the binary integer linear programming approach (which can be NP-hard in the worst case). We also add a step to predict domain–domain interactions which first searches the database Pfam using the hidden Markov model and then predicts the domain–domain interactions based on the database DOMINE and InterDom which contain confirmed DDIs. By adding the domain–domain interaction prediction step, we have more edges in the DDI graph and the recall value is increased significantly (at least doubled) comparing with the method of Ozawa et al. (2010) [1] while the average precision value is slightly better. We also combine our method with three other existing methods, such as COACH, MCL and MCODE. Experiments show that the precision of the combined method is improved. This article is part of a Special Issue entitled: Computational Methods for Protein Interaction and Structural Prediction.     

A new test set for validating predictions of protein-ligand interaction

We present a large test set of protein-ligand complexes for the purpose of validating algorithms that rely on the prediction of protein-ligand interactions. The set consists of 305 complexes with protonation states assigned by manual inspection. The following checks have been carried out to identify unsuitable entries in this set: (1) assessing the involvement of crystallographically related protein units in ligand binding; (2) identification of bad clashes between protein side chains and ligand; and (3) assessment of structural errors, and/or inconsistency of ligand placement with crystal structure electron density. In addition, the set has been pruned to assure diversity in terms of protein-ligand structures, and subsets are supplied for different protein-structure resolution ranges. A classification of the set by protein type is available. As an illustration, validation results are shown for GOLD and SuperStar. GOLD is a program that performs flexible protein-ligand docking, and SuperStar is used for the prediction of favorable interaction sites in proteins. The new CCDC/Astex test set is freely available to the scientific community (http://www.ccdc.cam.ac.uk).     

Modeling of metal interaction geometries for protein-ligand docking

The accurate modeling of metal coordination geometries plays an important role for structure-based drug design applied to metalloenzymes. For the development of a new metal interaction model, we perform a statistical analysis of metal interaction geometries that are relevant to protein-ligand complexes. A total of 43,061 metal sites of the Protein Data Bank (PDB), containing amongst others magnesium, calcium, zinc, iron, manganese, copper, cadmium, cobalt, and nickel, were evaluated according to their metal coordination geometry. Based on statistical analysis, we derived a model for the automatic calculation and definition of metal interaction geometries for the purpose of molecular docking analyses. It includes the identification of the metal-coordinating ligands, the calculation of the coordination geometry and the superposition of ideal polyhedra to identify the optimal positions for free coordination sites. The new interaction model was integrated in the docking software FlexX and evaluated on a data set of 103 metalloprotein-ligand complexes, which were extracted from the PDB. In a first step, the quality of the automatic calculation of the metal coordination geometry was analyzed. In 74% of the cases, the correct prediction of the coordination geometry could be determined on the basis of the protein structure alone. Secondly, the new metal interaction model was tested in terms of predicting protein-ligand complexes. In the majority of test cases, the new interaction model resulted in an improved docking accuracy of the top ranking placements.     

Detecting recombination in 4-taxa DNA sequence alignments with Bayesian hidden Markov models and Markov chain Monte Carlo

This article presents a statistical method for detecting recombination in DNA sequence alignments, which is based on combining two probabilistic graphical models: (1) a taxon graph (phylogenetic tree) representing the relationship between the taxa, and (2) a site graph (hidden Markov model) representing interactions between different sites in the DNA sequence alignments. We adopt a Bayesian approach and sample the parameters of the model from the posterior distribution with Markov chain Monte Carlo, using a Metropolis-Hastings and Gibbs-within-Gibbs scheme. The proposed method is tested on various synthetic and real-world DNA sequence alignments, and we compare its performance with the established detection methods RECPARS, PLATO, and TOPAL, as well as with two alternative parameter estimation schemes.     

HMMSTR: a hidden Markov model for local sequence-structure correlations in proteins

We describe a hidden Markov model, HMMSTR, for general protein sequence based on the I-sites library of sequence-structure motifs. Unlike the linear hidden Markov models used to model individual protein families, HMMSTR has a highly branched topology and captures recurrent local features of protein sequences and structures that transcend protein family boundaries. The model extends the I-sites library by describing the adjacencies of different sequence-structure motifs as observed in the protein database and, by representing overlapping motifs in a much more compact form, achieves a great reduction in parameters. The HMM attributes a considerably higher probability to coding sequence than does an equivalent dipeptide model, predicts secondary structure with an accuracy of 74.3 %, backbone torsion angles better than any previously reported method and the structural context of beta strands and turns with an accuracy that should be useful for tertiary structure prediction.