Efficient Algorithms for Protein Threading and Folding (May 1998)

Several key technologies have been developed in the Life Sciences Division Computational Biosciences Section for the computational determination of protein structure from sequence: (1) New polynomial time algorithms for protein threading evaluating whether a protein sequence matches any folds in the protein structure database. These new global optimization algorithms for threading consider both variable gaps and residue pair interactions in polynomial time and permit more realistic treatment of threading energy terms. (2) Improved energies and methods for protein threading. A database of energy minimized protein structures has been developed from which new tables for sidechain pair interaction, hydrophobicity, and local conformational energies for threading are being derived. AI-based protein structure classifiers trained by machine learning have been developed to assign protein sequences showing low homology with known sequences to structural classes. (3) Improving threading results and fold prediction using genetic algorithms. Techniques based on structure database-derived statistical information have been developed to improve partially correct threading results and improve/extend the target conformation obtained from one or several threadings. (Contact. E. C. Uberbacher, 574-6134 or ube@ornl.gov