A Bayesian Insertion/Deletion Algorithm for Distant Protein Motif Searching via Entropy Filtering

Abstract

Bayesian models have been developed that find ungapped motifs in multiple protein sequences. In this article, we extend the model to allow for deletions and insertions in motifs. Direct generalization of the ungapped algorithm, based on Gibbs sampling, proved unsuccessful because the configuration space became much larger. To alleviate the convergence difficulty, a two-stage procedure is introduced. At the first stage, we develop a method called entropy filtering, which quickly searchs “good” starting points for the alignment approach without the concern of deletion/insertion patterns. At the second stage, we switch to an algorithm that generates both a random vector that represents insertion/deletion patterns and a random variable of motif locations. After the two steps, gapped-motif alignments are obtained for multiple sequences. When applied to datasets that consist of helix–loop–helix proteins and high mobility group proteins, respectively, our methods show great improvements over those that produce ungapped alignments.

KEY WORDS :

• Entropy filtering
• Gapped alignment
• Gibbs sampling
• Protein motif