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 alignment accuracy

I Holmes1, R Durbin

  • 1Sanger Centre, Wellcome Trust Genome Campus, Hinxton, Cambridge, England. ihh,rd@sanger.ac.uk

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|October 17, 1998
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

Introgression dynamics of sex-linked chromosomal inversions shape the Malawi cichlid radiation.

Science (New York, N.Y.)·2025
Same author

Overview of the early campaign diagnostics for the SPARC tokamak (invited).

The Review of scientific instruments·2024
Same author

Overview of the neutron diagnostic systems for the SPARC tokamak.

The Review of scientific instruments·2024
Same author

Neutronics simulations for the design of neutron flux monitors in SPARC.

The Review of scientific instruments·2024
Same author

Upgrades to the ion cyclotron emission diagnostic on the DIII-D tokamak.

The Review of scientific instruments·2021
Same author

Perceptions of anthrax in livestock from Victorian dairy farmers in the Goulburn-Murray region of Victoria, Australia.

Australian veterinary journal·2019
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

Standard sequence alignment algorithms have accuracy limits. This study models these limits using an edge wander approximation and provides methods to predict and improve alignment accuracy, outperforming traditional dynamic programming.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Sequence alignment algorithms are crucial for biological research.
  • Existing methods, like global dynamic programming, possess inherent statistical limitations affecting alignment accuracy.
  • Accurate sequence alignments are fundamental for understanding evolutionary relationships and functional genomics.

Purpose of the Study:

  • To quantify the accuracy limitations of standard global dynamic programming for biological sequence alignment.
  • To develop a predictive model for alignment accuracy based on sequence divergence and scoring schemes.
  • To introduce a novel algorithm for constructing optimal accuracy alignments.

Main Methods:

  • Utilized simulations to measure the accuracy of the global dynamic programming method.

Related Experiment Videos

  • Employed an 'edge wander' approximation to model the distribution of optimal scoring paths near gaps.
  • Developed a method to calculate the expected accuracy of a given alignment.

    • Main Results:

    • Demonstrated that alignment accuracy can be reasonably modeled by the 'edge wander' approximation.
    • Provided a predictive table for accuracy values using common scoring schemes (PAM, BLOSUM) and sequence divergences.
    • Showcased that the optimal accuracy alignment algorithm significantly surpasses standard dynamic programming in simulated experiments.

    Conclusions:

    • The 'edge wander' approximation effectively models the accuracy limitations of dynamic programming alignment.
    • Predictive tools and novel algorithms can enhance the accuracy of biological sequence alignments.
    • Improved alignment accuracy has significant implications for downstream biological analyses.