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 Concept Videos

Evolutionary Relationships through Genome Comparisons02:54

Evolutionary Relationships through Genome Comparisons

6.5K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
6.5K
Maxam-Gilbert Sequencing01:05

Maxam-Gilbert Sequencing

11.7K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
11.7K
Sanger Sequencing01:57

Sanger Sequencing

762.9K
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
762.9K
Modern Molecular Taxonomy01:29

Modern Molecular Taxonomy

311
Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...
311
Next-generation Sequencing03:00

Next-generation Sequencing

94.8K
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
94.8K
Multi-species Conserved Sequences02:51

Multi-species Conserved Sequences

4.4K
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale  studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
4.4K

You might also read

Related Articles

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

Sort by
Same author

Promera: a unified model for biomolecular structure prediction, filtering, and design.

bioRxiv : the preprint server for biology·2026
Same author

KuPID: Kmer-based Upstream Preprocessing of Long Reads for Isoform Discovery.

bioRxiv : the preprint server for biology·2026
Same author

Evolutionary dynamics under phenotypic uncertainty.

bioRxiv : the preprint server for biology·2026
Same author

Profile of David Baker, Demis Hassabis, and John Jumper: 2024 Nobel laureates in chemistry.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same author

Learning the language of protein-protein interactions.

Nature communications·2026
Same author

Single-cell and spatial profiling highlights TB-induced myofibroblasts as drivers of lung pathology.

The Journal of experimental medicine·2026
Same journal

Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction.

IEEE transactions on information theory·2026
Same journal

Theoretical Guarantees for Sparse Principal Component Analysis based on the Elastic Net.

IEEE transactions on information theory·2025
Same journal

Uniform Convergence of Deep Neural Networks With Lipschitz Continuous Activation Functions and Variable Widths.

IEEE transactions on information theory·2025
Same journal

Kernel Stein Discrepancy on Lie Groups: Theory and Applications.

IEEE transactions on information theory·2024
Same journal

Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms.

IEEE transactions on information theory·2024
Same journal

Non-Asymptotic Guarantees for Reliable Identification of Granger Causality via the LASSO.

IEEE transactions on information theory·2024
See all related articles

Related Experiment Video

Updated: Oct 29, 2025

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.6K

Levenshtein Distance, Sequence Comparison and Biological Database Search.

Bonnie Berger1, Michael S Waterman2, Yun William Yu3

  • 1Department of Mathematics and Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139 USA, and also with the Department of Computer Science and AI Lab, Massachusetts Institute of Technology, Cambridge, MA 02139 USA.

IEEE Transactions on Information Theory
|July 14, 2021
PubMed
Summary
This summary is machine-generated.

Levenshtein edit distance is crucial for biological sequence alignment and database searching. Modern optimizations leverage its mathematical properties for significantly faster similarity searches in large genomic datasets.

Keywords:
Levenshtein distancedynamic programmingmetric entropysequence comparisonsimilarity search

More Related Videos

Novel Sequence Discovery by Subtractive Genomics
09:40

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

8.9K
Informatic Analysis of Sequence Data from Batch Yeast 2-Hybrid Screens
09:14

Informatic Analysis of Sequence Data from Batch Yeast 2-Hybrid Screens

Published on: June 28, 2018

7.3K

Related Experiment Videos

Last Updated: Oct 29, 2025

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.6K
Novel Sequence Discovery by Subtractive Genomics
09:40

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

8.9K
Informatic Analysis of Sequence Data from Batch Yeast 2-Hybrid Screens
09:14

Informatic Analysis of Sequence Data from Batch Yeast 2-Hybrid Screens

Published on: June 28, 2018

7.3K

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Levenshtein edit distance is fundamental for sequence alignment and biological database similarity searches.
  • Dynamic programming algorithms historically computed Levenshtein distance and sequence alignments.
  • Heuristics derived from these algorithms are used in bioinformatics software like BLAST for database searching.

Purpose of the Study:

  • To review the historical and current role of Levenshtein edit distance in bioinformatics.
  • To explain the evolution of algorithms from dynamic programming to modern optimizations.
  • To highlight how mathematical properties of Levenshtein distance enable accelerated similarity searches.

Main Methods:

  • Review of dynamic programming algorithms for Levenshtein distance and sequence alignment.
  • Description of heuristic development for bioinformatics software (e.g., BLAST).
  • Analysis of mathematical properties (metric entropy, fractional dimensionality) for optimization.

Main Results:

  • Levenshtein distance is a cornerstone of sequence alignment and similarity searching.
  • Algorithms evolved from dynamic programming to heuristics used in widely adopted software.
  • Modern genomic data volumes necessitate advanced local alignment techniques.
  • Mathematical formulation as a metric enables significant acceleration of biological similarity search.

Conclusions:

  • Levenshtein distance remains central to biological sequence analysis.
  • Advancements in algorithms and computational methods have dramatically improved search efficiency.
  • Leveraging the metric properties of Levenshtein distance is key to handling large-scale genomic data.
  • Optimized similarity search accelerates discovery in biological contexts.