Global Optimum Protein Threading with Gapped Alignment and Empirical Pair Score Functions

We describe a branch-and-bound search algorithm for finding the exact1Artificial Intelligence global optimum gapped sequence-structure alignment (‘‘threading’’)Laboratory, Massachusetts between a protein sequence and a protein core or structural model, usingInstitute of Technology an arbitrary amino acid pair score function (e.g. contact potentials,Cambridge, MA 02139, USA knowledge-based potentials, potentials of mean force, etc.). The search2BioMolecular Engineering method imposes minimal conditions on how structural environments are Research Center defined or the form of the score function, and allows arbitrar