Protein sequence threading, the alignment problem, and a two-step strategy

Conventionally, protein structure prediction via "threading" relies on some nonoptimal method to align a protein sequence to each member of a library of known structures. We show how a score function (force field) can be modi fied so as to allow the direct application of a dynamic programming algorit hm to the problem. This involves an approximation whose damage can be minim ized by an optimization process during score function parameter determinati on. The method is compared to sequence to structure alignments using a more conventional pair-wise score function and the frozen approximation. The ne w method produces results comparable to the frozen approximation, but is fa ster and has fewer adjustable parameters. It is also free of memory of the template's original amino acid sequence, and does not suffer from a problem of nonconvergence, which can be shown to occur with the frozen approximati on. Alignments generated by the simplified score function can then be ranke d using a second score function with the approximations removed. (C) 1999 J ohn Wiley & Sons, Inc.