PubMed · 11791226
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.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
R H Lathrop, A Sazhin, Y Sun, N Steffin, S S Irani. 2001. A multi-queue branch-and-bound algorithm for anytime optimal search with biological applications.. https://pubmed.health/record/pubmed%3A11791226/a-multi-queue-branch-and-bound-algorithm-for-anytime-optimal-search-with-biological-applications
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite PubMed Health by Indiciae: BibTeX · RIS.