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

Dynamic programming algorithms for biological sequence comparison.

W R Pearson1, W Miller

  • 1Department of Biochemistry, University of Virginia, Charlottesville 22908.

Methods in Enzymology
|January 1, 1992
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

Achievement of Target Gain Larger than Unity in an Inertial Fusion Experiment.

Physical review letters·2024
Same author

Lawson Criterion for Ignition Exceeded in an Inertial Fusion Experiment.

Physical review letters·2022
Same author

Letter from New York-Yellow Fever Prevented by Innoculation.

The Southern medical record·2022
Same author

Scintillation light detection in the 6-m drift-length ProtoDUNE Dual Phase liquid argon TPC.

The European physical journal. C, Particles and fields·2022
Same author

Prospects for beyond the Standard Model physics searches at the Deep Underground Neutrino Experiment: DUNE Collaboration.

The European physical journal. C, Particles and fields·2021
Same author

STAGdb: a 30K SNP genotyping array and Science Gateway for Acropora corals and their dinoflagellate symbionts.

Scientific reports·2020
Same journal

1,2-Aminothiol-specific conjugation for dual-color fluorescent labeling via ultrafast TAMM conjugates.

Methods in enzymology·2026
Same journal

Nitrone dipoles in bioorthogonal chemistry applications.

Methods in enzymology·2026
Same journal

Bioorthogonal labeling of sialic acid isomers for detection of glycoconjugates by mass spectrometry imaging and microscopy.

Methods in enzymology·2026
Same journal

Bioorthogonal photocatalytic proximity labeling for quantitative mapping of cell-cell interactions.

Methods in enzymology·2026
Same journal

inCu-click: Enabling copper-catalyzed click chemistry inside living cells.

Methods in enzymology·2026
Same journal

Site-specific antibody labeling via endo-S2 mediated Fc glycan remodeling.

Methods in enzymology·2026
See all related articles

Dynamic programming algorithms offer efficient sequence comparison for DNA and proteins. These methods, while computationally intensive for large databases, are suitable for evolutionary tree calculations and profile comparisons on desktop computers.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Dynamic programming algorithms provide efficient solutions for protein and DNA sequence comparison.
  • These algorithms have a time complexity of O(N^2) and a space complexity of O(N).
  • While O(N^2) time complexity limits their use in large-scale database searches, they are applicable to other computational biology tasks.

Purpose of the Study:

  • To highlight the utility of dynamic programming algorithms for sequence comparison beyond large database searches.
  • To emphasize the importance of rigorous optimal alignment for verifying results from rapid search programs like FASTA and BLAST.
  • To demonstrate the feasibility of using dynamic programming on desktop computers for specific applications.

Main Methods:

Related Experiment Videos

  • Utilizing dynamic programming algorithms for sequence alignment.
  • Comparing the performance and limitations of dynamic programming against heuristic methods (FASTA, BLAST).
  • Discussing gap penalty models (g = rk and g = q+rk) and their implementation.

    • Main Results:

    • Dynamic programming algorithms are well-suited for calculating evolutionary distances and comparing sequences against profiles on desktop computers.
    • Rigorous alignment using dynamic programming can substantially extend alignments missed by heuristic methods that limit gaps.
    • Optimal alignment using dynamic programming can be completed within an hour on standard personal computers.

    Conclusions:

    • Dynamic programming offers a robust method for sequence alignment, complementing faster heuristic approaches.
    • Rigorous sequence comparison is crucial for accurate biological interpretation, especially when using rapid search tools.
    • Accessible software implementations make dynamic programming a practical tool for various bioinformatics applications on common hardware.