A Multi-Queue Branch-and-Bound Algorithm for Anytime Optimal Search with Biological Applications

Richard H. Lathrop (rickl@uci.edu)
Anton Sazhin (sazhin@ics.uci.edu)
Ye Sun (ysun@uci.edu)
Nick Steffen (nsteffen@ics.uci.edu)
Sandra S. Irani (irani@ics.uci.edu)

Information and Computer Science, U. of California, Irvine, CA 92697-3425, U.S.A.


Abstract

Many practical biological problems involve an intractable (NP-hard) search through a large space of possibilities. This paper describes preliminary results from a multi-queue variant of branch-and-bound search that combines anytime and optimal search behavior. The algorithm applies to problems whose solutions may be described by an N-dimensional vector. It produces an approximate solution quickly, then iteratively improves the result over time until a global optimum is produced. A global optimum may be produced before producing its proof of global optimality. Local minima are never revisited. We describe preliminary applications to ab initio protein backbone prediction, small drug-like molecule conformations, and protein-DNA binding motif discovery. The results are encouraging, although still quite preliminary.

[ Full-text PDF | Table of Contents ]


Japanese Society for Bioinformatics