Protein fold recognition by threading: comparison of algorithms and analysis of results

Optimal sequence threading can be used to recognize members of a library of protein folds which are closely related in 3-D structure to the native fold of an input test sequence, even when the test sequence is not significantly homologous to the sequence of any member of the fold library. The methods provide an alignment between the residues of the test sequence and the residue positions in a template fold. This alignment optimizes a score function, and the predicted fold is the highest scoring member of the library of folds. Most score functions contain a pairwise interaction energy term. This, coupled with the need to introduce gaps into the alignment, means that the optimization problem is NP hard. We report a comparison between two heuristic optimization algorithms used in the literature, double dynamic programming and an iterative algorithm based on the so-called frozen approximation. These are compared in terms of both the ranking of likely folds and the quality of the alignment produced.