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

Distance Corrections01:15

Distance Corrections

174
To achieve precise distance measurements, especially in surveying and construction, certain corrections must be applied to account for potential sources of error like the standardization errors, temperature variations, and slope adjustments.Standardization error emerges when measurement equipment undergoes changes, such as wear, repairs, or weather impacts. To address this, surveyors compare the equipment’s readings to a standard. This process identifies any deviation that might lead to...
174
Fixing Double-strand Breaks02:04

Fixing Double-strand Breaks

3.9K
3.9K
Fixing Double-strand Breaks02:04

Fixing Double-strand Breaks

13.6K
The double-stranded structure of DNA has two major advantages. First, it serves as a safe repository of genetic information where one strand serves as the back-up in case the other strand is damaged. Second, the double-helical structure can be wrapped around proteins called histones to form nucleosomes, which can then be tightly wound to form chromosomes. This way, DNA chains up to 2 inches long can be contained within microscopic structures in a cell. A double-stranded break not only damages...
13.6K
Improving Translational Accuracy02:07

Improving Translational Accuracy

12.8K
Base complementarity between the three base pairs of mRNA codon and the tRNA anticodon is not a failsafe mechanism. Inaccuracies can range from a single mismatch to no correct base pairing at all. The free energy difference between the correct and nearly correct base pairs can be as small as 3 kcal/ mol. With complementarity being the only proofreading step, the estimated error frequency would be one wrong amino acid in every 100 amino acids incorporated. However, error frequencies observed in...
12.8K
Improving Translational Accuracy02:07

Improving Translational Accuracy

3.3K
3.3K
Mismatch Repair01:36

Mismatch Repair

42.8K
Overview
42.8K

You might also read

Related Articles

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

Sort by
Same author

Fast Algorithms for Computing Jaro Similarity.

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

String correction using the Damerau-Levenshtein distance.

BMC bioinformatics·2019
Same author

Cache and energy efficient algorithms for Nussinov's RNA Folding.

BMC bioinformatics·2017
Same author

PMS6MC: A Multicore Algorithm for Motif Discovery.

Algorithms·2014
Same author

Multicore and GPU algorithms for Nussinov RNA folding.

BMC bioinformatics·2014
Same author

Pairwise sequence alignment for very long sequences on GPUs.

International journal of bioinformatics research and applications·2014
Same journal

NAP: an open source pipeline for cross-domain microbiome profiling using Nanopore sequencing-derived amplicon data.

BMC bioinformatics·2026
Same journal

SurvGME: an R package for survival analysis with graphical and measurement error models.

BMC bioinformatics·2026
Same journal

SimMapNet: a Bayesian framework for gene regulatory network inference using gene ontology similarities as external hint.

BMC bioinformatics·2026
Same journal

Dual channel drug-drug interactions extraction based on cross attention.

BMC bioinformatics·2026
Same journal

FeSseqdb: a curated sequence-level database and interpretable machine learning framework for identifying iron-sulfur proteins.

BMC bioinformatics·2026
Same journal

Benchmarking DNA barcode decoding strategies under high error rates.

BMC bioinformatics·2026
See all related articles

Related Experiment Video

Updated: Nov 26, 2025

Quantifying Intermembrane Distances with Serial Image Dilations
07:45

Quantifying Intermembrane Distances with Serial Image Dilations

Published on: September 28, 2018

6.6K

Linear space string correction algorithm using the Damerau-Levenshtein distance.

Chunchun Zhao1, Sartaj Sahni2

  • 1Department of Computer and Information Science and Engineering, University of Florida, Gainesville, 32611, FL, USA. zhaochunchun@gmail.com.

BMC Bioinformatics
|December 10, 2020
PubMed
Summary
This summary is machine-generated.

New algorithms for Damerau-Levenshtein (DL) distance computation achieve linear space complexity. These methods significantly reduce runtime for calculating sequence similarity and edit operations in biological sciences.

Keywords:
Damerau-Levenshtein distanceEdit distanceLinear spaceString correction

More Related Videos

Rare Event Detection Using Error-corrected DNA and RNA Sequencing
10:36

Rare Event Detection Using Error-corrected DNA and RNA Sequencing

Published on: August 3, 2018

12.4K
Proofreading and DNA Repair Assay Using Single Nucleotide Extension and MALDI-TOF Mass Spectrometry Analysis
11:08

Proofreading and DNA Repair Assay Using Single Nucleotide Extension and MALDI-TOF Mass Spectrometry Analysis

Published on: June 19, 2018

10.0K

Related Experiment Videos

Last Updated: Nov 26, 2025

Quantifying Intermembrane Distances with Serial Image Dilations
07:45

Quantifying Intermembrane Distances with Serial Image Dilations

Published on: September 28, 2018

6.6K
Rare Event Detection Using Error-corrected DNA and RNA Sequencing
10:36

Rare Event Detection Using Error-corrected DNA and RNA Sequencing

Published on: August 3, 2018

12.4K
Proofreading and DNA Repair Assay Using Single Nucleotide Extension and MALDI-TOF Mass Spectrometry Analysis
11:08

Proofreading and DNA Repair Assay Using Single Nucleotide Extension and MALDI-TOF Mass Spectrometry Analysis

Published on: June 19, 2018

10.0K

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Analysis

Background:

  • Damerau-Levenshtein (DL) distance is crucial for comparing biological sequences (DNA, RNA, proteins).
  • Existing algorithms, while effective, have high space complexity (O(mn)).
  • Previous research introduced space-efficient algorithms (O(s*min{m,n}+m+n)) for DL distance and edit sequences.

Purpose of the Study:

  • To develop algorithms for Damerau-Levenshtein (DL) distance with linear space complexity.
  • To create methods for determining the optimal edit sequence (trace) in linear space.
  • To improve the speed and space efficiency of DL distance computation.

Main Methods:

  • Development of novel algorithms with asymptotic linear space complexity.
  • Implementation and testing on diverse computational platforms (Xeon E5 2603, I7-x980, Xeon E5 2695).
  • Comparative analysis against existing state-of-the-art algorithms.

Main Results:

  • Linear space algorithms were successfully developed for DL distance and optimal trace computation.
  • Experimental results demonstrate significant speed improvements over previous algorithms.
  • Algorithms show reduced space usage while maintaining or improving computational speed.

Conclusions:

  • The new linear-space algorithms offer substantial improvements in both space efficiency and runtime.
  • Runtime reductions of up to 57.4% were observed for DL distance and edit sequence computation.
  • Multi-core implementations further enhanced performance, reducing runtime by up to 59.3%.