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 polynomial-time algorithm for a class of protein threading problems

Y Xu1, E C Uberbacher

  • 1Computer Science and Mathematics Division, Oak Ridge National Laboratory, TN 37831-6364, USA. xyn@ornl.gov

Computer Applications in the Biosciences : CABIOS
|December 1, 1996
PubMed
Summary
This summary is machine-generated.

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

Computational tools for protein modeling.

Current protein & peptide science·2002
Same author

Sequence-structure specificity of a knowledge based energy function at the secondary structure level.

Bioinformatics (Oxford, England)·2000
Same author

The Genome Channel: a browser to a uniform first-pass annotation of genomic DNA.

Trends in genetics : TIG·1999
Same author

An efficient computational method for globally optimal threading.

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

An editing environment for DNA sequence analysis and annotation (extended abstract).

Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing·1998
Same author

The yeast 8-oxoguanine DNA glycosylase (Ogg1) contains a DNA deoxyribophosphodiesterase (dRpase) activity.

Nucleic acids research·1998
Same journal

DCA: an efficient implementation of the divide-and-conquer approach to simultaneous multiple sequence alignment.

Computer applications in the biosciences : CABIOS·1998
Same journal

Two applications to facilitate the viewing of database search result files on the Macintosh.

Computer applications in the biosciences : CABIOS·1998
Same journal

BioWish: a molecular biology command extension to Tcl/Tk.

Computer applications in the biosciences : CABIOS·1998
Same journal

The Sequence Alerting Server--a new WEB server.

Computer applications in the biosciences : CABIOS·1998
Same journal

A software tool for the analysis of mass spectrometric disulfide mapping experiments.

Computer applications in the biosciences : CABIOS·1998
Same journal

SAMBA: hardware accelerator for biological sequence comparison.

Computer applications in the biosciences : CABIOS·1998
See all related articles

This study introduces an efficient algorithm for optimal protein structure-sequence alignment, considering long-range interactions. The method achieves polynomial time complexity, improving upon existing NP-hard problem solutions.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Structural Bioinformatics

Background:

  • Protein structure-sequence alignment is crucial for understanding protein function and evolution.
  • Traditional sequence alignment methods do not fully capture the complexities of 3D structural interactions.
  • Incorporating long-range interactions in alignment is computationally challenging.

Purpose of the Study:

  • To develop an algorithm for optimal alignment between 3D protein structure templates and amino acid sequences.
  • To address the computational complexity of structure-sequence alignment with long-range interactions.
  • To provide a polynomial-time solution for specific cases of structure-sequence alignment.

Main Methods:

  • Developed a novel algorithm for optimal structure-sequence alignment.

Related Experiment Videos

  • Incorporated match scores, gap penalties, and long-range interaction preferences.
  • Algorithm complexity is O(2^C * N * M), where C is the maximum cut size of long-range interactions, N is sequence size, and M is template size.
  • Algorithm runs in polynomial time when C is logarithmic.

    • Main Results:

    • The algorithm finds optimal structure-sequence alignments in polynomial time for structures with a limited number of long-range interactions.
    • When long-range interactions are absent (C=0), the algorithm matches the Smith-Waterman algorithm's complexity.
    • Demonstrated efficiency for structure-sequence alignment problems with interactions between different core secondary structures.

    Conclusions:

    • The proposed algorithm offers an efficient approach to optimal protein structure-sequence alignment.
    • It effectively handles long-range interactions, a key factor in structural biology.
    • This method advances the field of computational structural bioinformatics by providing a tractable solution to a complex problem.