title: A post-decoding re-ranking algorithm for predicting interacting residues in proteins with hidden Markov models incorporating long-distance information.
abstract: Protein-protein interactions play a central role in the biological processes of cells. Accurate prediction of the interacting residues in protein-protein interactions enhances understanding of the interaction mechanisms and enables in silico mutagenesis, which can help facilitate drug design and deepen our understanding of the inner workings of cells. Correlations have been found among interacting residues as a result of selection pressure to retain the interaction during evolution. In previous work, incorporation of such correlations in the interaction profile hidden Markov models with a special decoding algorithm (ETB-Viterbi) has led to improvement in prediction accuracy. In this work, we first demonstrated the sub-optimality of the ETB-Viterbi algorithm, and then reformulated the optimality of decoding paths to include correlations between interacting residues. To identify optimal decoding paths, we propose a post-decoding re-ranking algorithm based on a genetic algorithm with simulated annealing and show that the new method gains an increase of near 14% in prediction accuracy over the ETB-Viterbi algorithm.
authors.affiliation: Department of Computer and Information Science, University of Delaware, Newark, DE 19716, USA.
authors.forename: Colin
authors.initials: C
authors.lastname: Kern
authors.affiliation: Department of Computer and Information Science, University of Delaware, Newark, DE 19716, USA. Electronic address: liliao@udel.edu.
authors.forename: Li
authors.initials: L
authors.lastname: Liao
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D008390:Markov Chains; D011506:Proteins / Q000737:chemistry*; D017386:Sequence Homology, Amino Acid
chemical_list: D011506:Proteins
keywords: Genetic algorithm; Protein–protein interaction