Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

A multi-queue branch-and-bound algorithm for anytime optimal search with biological applications.

R H Lathrop1, A Sazhin, Y Sun

  • 1Information and Computer Science, U. of California, Irvine, CA 92697-3425, USA. rickl@uci.edu

Genome Informatics. International Conference on Genome Informatics
|January 16, 2002
PubMed
Summary

This study introduces a novel multi-queue branch-and-bound search algorithm. It efficiently finds optimal solutions for complex biological problems, providing approximate results rapidly and refining them over time.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Development and evaluation of a novel simulation model for transabdominal preperitoneal (TAPP) inguinal hernia repair.

Hernia : the journal of hernias and abdominal wall surgery·2019
Same author

Prevalence and risk factors for abdominal wall hernia in the general Russian population.

Hernia : the journal of hernias and abdominal wall surgery·2019
Same author

DNA sequence and structure: direct and indirect recognition in protein-DNA binding.

Bioinformatics (Oxford, England)·2002
Same author

An anytime local-to-global optimization algorithm for protein threading in theta (m2ñ2) space.

Journal of computational biology : a journal of computational molecular cell biology·1999
Same author

A Bayes-optimal sequence-structure theory that unifies protein sequence-structure recognition and alignment.

Bulletin of mathematical biology·1998
Same author

Modeling protein homopolymeric repeats: possible polyglutamine structural motifs for Huntington's disease.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·1998

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Development

Background:

  • Many biological problems require searching vast possibility spaces, often proving computationally intractable (NP-hard).
  • Existing search algorithms may struggle to balance speed with the guarantee of finding a global optimum.

Purpose of the Study:

  • To present a novel multi-queue variant of the branch-and-bound search algorithm.
  • To combine anytime (rapid approximate) and optimal search behaviors for NP-hard problems.
  • To apply the algorithm to diverse biological challenges.

Main Methods:

  • Developed a multi-queue branch-and-bound search algorithm adaptable to N-dimensional vector solution spaces.
  • Implemented an iterative improvement strategy, delivering approximate solutions quickly and progressively refining them towards global optima.

Related Experiment Videos

  • Ensured that local minima are never revisited during the search process.

    • Main Results:

    • Demonstrated preliminary successful applications in ab initio protein backbone prediction.
    • Showcased utility in determining small drug-like molecule conformations.
    • Applied effectively to protein-DNA binding motif discovery.

    Conclusions:

    • The multi-queue branch-and-bound algorithm shows promise for efficiently tackling complex biological search problems.
    • The approach offers a valuable method for obtaining both rapid approximate and guaranteed optimal solutions.
    • Further research and validation are warranted given the preliminary nature of the results.