An anytime algorithm for gapped block protein threading with pair interactions

This paper describes a novel anytime branch-andbound threading search algorithm for gapped block protein sequence-structure alignment with general sequence residue pair interactions. The new algorithm (1) returns a good approximate answer quickly, (2) iteratively improves that answer to the global optimum if allowed more time, (3) eventually produces a proof that the final answer found is indeed the global optimum, and (4) always terminates correctly within a bounded number of steps if allowed sufficient space and time. Using previously published data sets and the Bryant-Lawrence (1993) objective function, the algorithm found the true (proven) global optimum in less than five minutes in alI search spaces size 1O25 or smaller (sequences to 478 residues), and a putative (not guaranteed) optimum in less than five hours in all search spaces size 10” or smaller (sequences to 793 residues, cores to 42 secondary structure segments). If the threading in the largest case were eventually proven to be globally optimal, then the corresponding search speed in the largest case studied would be the equivalent of 1.5 x 1O56 threadings per second, a speed-up exceeding 1O25 over previously published batch branch-and-bound speeds, and exceeding 1050 over previously published exhaustive search speeds, using the same objective function and threading paradigm. Implementation independent measures of search efficiency are defined for equivalent branching factor, depth, and probability of success per draw; empirical data on these measures is given. The general approach should apply to other alignment methodologies and search methods that use a divide-and-conquer strategy.