Improved algorithms for protein motif recognition
Bonnie Berger, David Brown Wilson · Symposium on Discrete Algorithms · 1995
The identification of protein sequences that fold into certain known three-dimensional (3D) structures, or motifs, is evaluated through a probabilistic analysis of their one-dimensional (1D) sequences. We present correlation methods that run in linear time and incorporate pairwise dependencies between amino acid residues at multiple distances to assess the conditional probability that a given residue is part of a given 3D structure. One of these methods is generalized to multiple motifs, where a dynamic programming approach leads to an efficient algorithm that runs in linear time for practical problems. By this approach, we were able to distinguish (2-stranded) coiled-coil from noncoiled-coil domains and globins from nonglobins.