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

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

R H Lathrop1

  • 1Department of Information and Computer Science, University of California, Irvine 92697, USA. rickl@uci.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|December 3, 1999
PubMed
Summary

A new anytime threading search algorithm quickly finds approximate protein sequence-structure alignments and iteratively refines them to the global optimum. This novel method guarantees optimality proofs and terminates within bounded steps, significantly outperforming previous search speeds.

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

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

Bioinformatics (Oxford, England)·2002
Same author

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

Genome informatics. International Conference on Genome Informatics·2002
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
Same author

Global optimum protein threading with gapped alignment and empirical pair score functions.

Journal of molecular biology·1996
Same author

A shape-based machine learning tool for drug design.

Journal of computer-aided molecular design·1994

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Development

Background:

  • Protein sequence-structure alignment is crucial for understanding protein function.
  • Existing alignment algorithms often struggle with computational complexity and finding globally optimal solutions.
  • Gapped block alignment with residue pair interactions presents significant computational challenges.

Purpose of the Study:

  • To introduce a novel anytime branch-and-bound or best-first threading search algorithm.
  • To enable rapid approximation of optimal protein sequence-structure alignments.
  • To provide a method for iteratively improving alignments towards a proven global optimum.

Main Methods:

  • Development of an anytime branch-and-bound/best-first threading search algorithm.

Related Experiment Videos

  • Implementation utilizing polynomial space complexity, dominated by lower bound computation.
  • Testing on established datasets using the Bryant-Lawrence objective function.

    • Main Results:

    • The algorithm rapidly finds approximate solutions and converges to proven global optima for smaller search spaces (up to 10^25).
    • It achieves near-optimal solutions for larger search spaces (up to 10^60) within hours.
    • Demonstrated speed-ups exceeding 10^25 and 10^50 compared to previous branch-and-bound and exhaustive search methods, respectively.

    Conclusions:

    • The novel algorithm offers a significant advancement in protein sequence-structure alignment efficiency and accuracy.
    • Its anytime nature allows for flexible trade-offs between computation time and solution quality.
    • The general approach is adaptable to other alignment methodologies and divide-and-conquer search strategies.