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

Lagging Strand Synthesis

Lagging Strand Synthesis

Lagging Strand Synthesis

Lagging Strand Synthesis

During replication, the complementary strands in double-stranded DNA are synthesized at different rates. Replication first begins on the leading strand. Replication starts later, occurs more slowly, and proceeds discontinuously on the lagging strand.
There are several major differences between synthesis of the leading strand and synthesis of the lagging strand. 1) Leading strand synthesis happens in the direction of replication fork opening, whereas lagging strand synthesis happens in the...

Nomenclature of Alkenes

Nomenclature of Alkenes

The IUPAC naming system for alkenes replaces -an- with -en- in the corresponding parent alkanes. Accordingly, a simple alkene replaces the -ane suffix of the alkane with -ene.
As per the IUPAC rules, the longest carbon chain containing the maximum number of double bonds is identified as the parent chain and is numbered such that the doubly bonded carbon atoms receive the lowest possible numbers. The location of the double bond is indicated by the number of its first carbon atom. In branched...

Functional Groups

Functional Groups

Long-patch Base Excision Repair

Long-patch Base Excision Repair

Since the discovery of the two BER pathways, there has been a debate about how a cell chooses one pathway over the other and the factors determining this selection. Numerous in vitro experiments have pointed out multiple determinants for the sub-pathway selection. These are:

Pre-mRNA Processing: RNA Splicing

Pre-mRNA Processing: RNA Splicing

You might also read

Related Articles

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

Sort by

Same author

Faster run-length compressed suffix arrays.

Oasics : openaccess series in informatics·2026

Same authorSame journal

Prefix-free parsing for merging big BWTs.

International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)·2025

Same author

Movi 2: Fast and Space-Efficient Queries on Pangenomes.

bioRxiv : the preprint server for biology·2025

Same author

b-move: faster lossless approximate pattern matching in a run-length compressed index.

Algorithms for molecular biology : AMB·2025

Same author

Efficient Grammar Compression via RLZ-based RePair.

bioRxiv : the preprint server for biology·2025

Same author

Run-length compressed metagenomic read classification with SMEM-finding and tagging.

bioRxiv : the preprint server for biology·2025

Same journal

KeBaB: <i>k</i>-mer based breaking for finding long MEMs.

International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)·2025

Same journal

Data Structures for SMEM-Finding in the PBWT.

International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)·2024

Same journal

Space-time Trade-offs for the LCP Array of Wheeler DFAs.

International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)·2024

Same journal

KATKA: A KRAKEN-like tool with <math></math> given at query time.

International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)·2024

Same journal

Computing the original eBWT faster, simpler, and with less memory.

International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)·2024

See all related articles

Search research articles

Related Experiment Video

Updated: Jan 8, 2026

Curation of Computational Chemical Libraries Demonstrated with Alpha-Amino Acids

Curation of Computational Chemical Libraries Demonstrated with Alpha-Amino Acids

Published on: April 13, 2022

A simple grammar-based index for finding approximately longest common substrings.

Travis Gagie^1,2, Sana Kashgouli¹, Gonzalo Navarro^3,2

¹Faculty of Computer Science, Dalhousie University, Halifax, Canada.

International Symposium on String Processing and Information Retrieval : SPIRE ... : Proceedings. SPIRE (Symposium)

|December 15, 2025

Summary

This summary is machine-generated.

This study introduces an efficient data structure for finding approximate longest common substrings between a pattern and a text. The new index significantly speeds up pattern matching while maintaining high accuracy.

Keywords:

Approximately longest common substrings Grammar-based indexing alpha-balanced grammars

More Related Videos

Novel Sequence Discovery by Subtractive Genomics

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

Analysis of Termination of Transcription Using BrUTP-strand-specific Transcription Run-on TRO Approach

Analysis of Termination of Transcription Using BrUTP-strand-specific Transcription Run-on TRO Approach

Published on: March 12, 2017

Related Experiment Videos

Last Updated: Jan 8, 2026

Curation of Computational Chemical Libraries Demonstrated with Alpha-Amino Acids

Curation of Computational Chemical Libraries Demonstrated with Alpha-Amino Acids

Published on: April 13, 2022

Novel Sequence Discovery by Subtractive Genomics

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

Analysis of Termination of Transcription Using BrUTP-strand-specific Transcription Run-on TRO Approach

Analysis of Termination of Transcription Using BrUTP-strand-specific Transcription Run-on TRO Approach

Published on: March 12, 2017

Area of Science:

Computer Science
Algorithms
Data Structures

Background:

Efficiently finding common substrings between large texts and patterns is a fundamental problem in computer science.
Existing methods often face trade-offs between space complexity, query time, and accuracy.

Purpose of the Study:

To develop a space-efficient index for identifying substrings of a pattern that are also present in a given text.
To achieve a query time that is nearly linear in the pattern length while guaranteeing a significant fraction of the longest common substring.

Main Methods:

Construction of an O(g)-space index based on an alpha-balanced straight-line program for the text.
Utilizing the index to search for pattern substrings within a specified time complexity.

Main Results:

The proposed index allows finding a common substring of P and T with a length of at least (1-epsilon) fraction of the longest common substring.
This is achieved with high probability (w.h.p.) in O(m log^delta g) expected query time, using O(g) space.

Conclusions:

The study presents a novel approach to approximate longest common substring queries, offering a favorable balance between space and time efficiency.
The developed index provides a practical solution for applications requiring fast and accurate substring matching.