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