PROTEIN FOLD RECOGNITION BY THREADING - COMPARISON OF ALGORITHMS AND ANALYSIS OF RESULTS

Optimal sequence threading can be used to recognize members of a libra ry 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 alig nment optimizes a score function, and the predicted fold is the highes t scoring member of the library of folds. Most score functions contain a pairwise interaction energy term, This, coupled with the need to in troduce gaps into the alignment, means that the optimization problem i s NP hard, We report a comparison between two heuristic optimization a lgorithms used in the literature, double dynamic programming and an it erative algorithm based on the so-called frozen approximation, These a re compared in terms of both the ranking of likely folds and the quali ty of the alignment produced.