Richard H. Lathrop (email@example.com)
Anton Sazhin (firstname.lastname@example.org)
Ye Sun (email@example.com)
Nick Steffen (firstname.lastname@example.org)
Sandra S. Irani (email@example.com)
Information and Computer Science, U. of California, Irvine, CA 92697-3425, U.S.A.
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.