Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Related Concept Videos

Adjusting a Traverse

Adjusting a Traverse

In the site survey of a four-sided traverse, internal angles are essential to ensure geometric accuracy. The survey revealed that the sum of the measured internal angles was 359 degrees and 48 minutes, which is 12 minutes less than the expected 360 degrees. This discrepancy signals an error likely arising from measurement inaccuracies during the fieldwork.To rectify this error, the adjustment process involved distributing the 12-minute shortfall equally across the four internal angles. By...

You might also read

Related Articles

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

Sort by

Same author

Hash functions in nucleotide sequence analysis.

Genome research·2026

Same author

Estimation of substitution and indel rates via <i>k</i>-mer statistics.

Algorithms in bioinformatics : ... International Workshop, WABI ..., proceedings. WABI (Workshop)·2026

Same author

A k-mer-Based Estimator of the Substitution Rate Between Repetitive Sequences.

Algorithms in bioinformatics : ... International Workshop, WABI ..., proceedings. WABI (Workshop)·2026

Same author

Efficiency of Learned Indexes on Genome Spectra.

LIPIcs : Leibniz international proceedings in informatics·2026

Same author

The gift of novelty: repeat-robust <i>k</i>-mer-based estimators of mutation rates.

bioRxiv : the preprint server for biology·2026

Same author

Data Structures to Represent a Set of <math><mi>k</mi></math> -long DNA Sequences.

ACM computing surveys·2026

Same journal

Haplotype-aware long-read error correction.

Algorithms for molecular biology : AMB·2026

Same journal

Extension of partial atom-to-atom maps: uniqueness and algorithms.

Algorithms for molecular biology : AMB·2026

Same journal

Lossless pangenome indexing using tag arrays.

Algorithms for molecular biology : AMB·2026

Same journal

Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer.

Algorithms for molecular biology : AMB·2026

Same journal

Probing transcription factor subsets in gene regulatory networks.

Algorithms for molecular biology : AMB·2026

Same journal

Comparing the ability of embedding methods on metabolic hypergraphs for capturing taxonomy-based features.

Algorithms for molecular biology : AMB·2026

See all related articles

Search research articles

Related Experiment Video

Updated: Jun 27, 2025

High-Throughput Analysis of Optical Mapping Data Using ElectroMap

High-Throughput Analysis of Optical Mapping Data Using ElectroMap

Published on: June 4, 2019

ESKEMAP: exact sketch-based read mapping.

Tizian Schulz^1,2,3, Paul Medvedev^4,5,6

¹Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany. tizian.schulz@uni-bielefeld.de.

Algorithms for Molecular Biology : AMB

|May 4, 2024

Summary

This summary is machine-generated.

This study introduces an exact algorithm for sketch-based read mapping, finding all genomic locations above a similarity threshold. The new method improves recall compared to existing tools like minimap2.

Keywords:

Dynamic programming Exact algorithm Long-read mapping Sequence sketching

More Related Videos

Targeted DNA Methylation Analysis by Next-generation Sequencing

Targeted DNA Methylation Analysis by Next-generation Sequencing

Published on: February 24, 2015

Mapping RNA-RNA Interactions Globally Using Biotinylated Psoralen

Mapping RNA-RNA Interactions Globally Using Biotinylated Psoralen

Published on: May 24, 2017

Related Experiment Videos

Last Updated: Jun 27, 2025

High-Throughput Analysis of Optical Mapping Data Using ElectroMap

High-Throughput Analysis of Optical Mapping Data Using ElectroMap

Published on: June 4, 2019

Targeted DNA Methylation Analysis by Next-generation Sequencing

Targeted DNA Methylation Analysis by Next-generation Sequencing

Published on: February 24, 2015

Mapping RNA-RNA Interactions Globally Using Biotinylated Psoralen

Mapping RNA-RNA Interactions Globally Using Biotinylated Psoralen

Published on: May 24, 2017

Area of Science:

Bioinformatics
Computational Biology
Genomics

Background:

Read mapping identifies similar sequences between a sequencing read and a reference genome.
Traditional mappers use alignment scores; sketch-based mappers lack a precise problem formulation.
Existing sketch-based methods cannot find all mapping positions above a similarity threshold.

Purpose of the Study:

To formulate the problem of read mapping at the sequence sketch level.
To develop an exact algorithm for sketch-based read mapping.
To find all possible mapping positions for a read above a specified similarity score.

Main Methods:

Formulation of read mapping using sequence sketches.
Development of an exact dynamic programming algorithm.
Algorithm analysis with time and space complexity in terms of k-mers and sketch properties.

Main Results:

An exact algorithm finds all mapping hits above a similarity threshold.
The algorithm runs in O(|t| + |p| + occ) time and O(|t| + |p|) space.
In mapping long reads to the human Y chromosome, the algorithm achieved 0.88 recall versus minimap2's 0.76 at equivalent precision.

Conclusions:

The developed algorithm precisely addresses sketch-based read mapping.
This method successfully identifies all significant mapping positions, outperforming existing tools in recall.
The approach is particularly valuable for complex genomic regions like ampliconic sequences.