A multi-queue branch-and-bound algorithm for anytime optimal search with biological applications.
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.
Lathrop
R H
RH
Information and Computer Science, U. of California, Irvine, CA 92697-3425, USA. rickl@uci.edu
Sazhin
A
A
Sun
Y
Y
Steffin
N
N
Irani
S S
SS
D000465:Algorithms; D019295:Computational Biology; D004247:DNA / Q000378:metabolism; D008968:Molecular Conformation; D015394:Molecular Structure; D011485:Protein Binding; D011506:Proteins / Q000737:chemistry
D011506:Proteins; D004247:DNA