A branch-and-bound algorithm for optimal protein threading with pairwise (contact potential) amino acid interactions

Presents a new branch-and-bound method of searching the space of possible "threadings" for the optimal match of a sequence to an adjacency matrix of environments in the "motif threading" version of the "inverse protein folding problem." The method is guaranteed to find the optimal threading first, and thereafter will enumerate successive candidate threadings in order of decreasing optimality. We require minimal conditions on how environments are defined and the form of the score function, and the search method is sufficiently general to be used with many different score functions which model contact potentials or other interactions between explicit pairs of amino acids. This algorithm has been used in conjunction with a pairwise interaction score function to identify the optimal threading out of as many as 1.69/spl times/10/sup 24/ possibilities on a Sun Sparcstation IPC workstation in 40 minutes total elapsed time.<>