Prediction of Indel flanking regions in protein sequences using a variable-order Markov model

Motivation: Insertion/deletion (indel) and amino acid substitution are two common events that lead to the evolution of and variations in protein sequences. Further, many of the human diseases and functional divergence between homologous proteins are more related to indel mutations, even though they occur less often than the substitution mutations do. A reliable identification of indels and their flanking regions is a major challenge in research related to protein evolution, structures and functions. Results: In this article, we propose a novel scheme to predict indel flanking regions in a protein sequence for a given protein fold, based on a variable-order Markov model. The proposed indel flanking region (IndeIFR) predictors are designed based on prediction by partial match (PPM) and probabilistic suffix tree (PST), which are referred to as the PPM IndeIFR and PST IndeIFR predictors, respectively. The overall performance evaluation results show that the proposed predictors are able to predict IndeIFRs in the protein sequences with a high accuracy and F1 measure. In addition, the results show that if one is interested only in predicting IndeIFRs in protein sequences, it would be preferable to use the proposed predictors instead of HMMER 3.0 in view of the substantially superior performance of the former.