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

Interference: Path Lengths

Interference: Path Lengths

Consider two sources of sound, that may or may not be in phase, emitting waves at a single frequency, and consider the frequencies to be the same.
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...

Discrete-Time Fourier Series

Discrete-Time Fourier Series

The Discrete-Time Fourier Series (DTFS) is a fundamental concept in signal processing, serving as the discrete-time counterpart to the continuous-time Fourier series. It allows for the representation and analysis of discrete-time periodic signals in terms of their frequency components. Unlike its continuous counterpart, which utilizes integrals, the calculation of DTFS expansion coefficients involves summations due to the discrete nature of the signal.
For a discrete-time periodic signal x[n]...

Fast Fourier Transform

Fast Fourier Transform

The Fast Fourier Transform (FFT) is a computational algorithm designed to compute the Discrete Fourier Transform (DFT) efficiently. By breaking down the calculations into smaller, manageable sections, the FFT significantly reduces the computational complexity involved. Direct computation of an N-point DFT requires N2 complex multiplications, whereas the FFT algorithm needs only (N/2)log⁡2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...

Properties of DTFT I

Properties of DTFT I

In signal processing, Discrete-Time Fourier Transforms (DTFTs) play a critical role in analyzing discrete-time signals in the frequency domain. Various properties of the DTFTs such as linearity, time-shifting, frequency-shifting, time reversal, conjugation, and time scaling help understand and manipulate these signals for different applications.
The linearity property of DTFTs is fundamental. If two discrete-time signals are multiplied by constants a and b respectively, and then combined to...

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 authorSame journal

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

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

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: Jun 17, 2025

Author Spotlight: Introduction to Active Probe Atomic Force Microscopy with Quattro-Parallel Cantilever Arrays

Author Spotlight: Introduction to Active Probe Atomic Force Microscopy with Quattro-Parallel Cantilever Arrays

Published on: June 13, 2023

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

Nicola Cotumaccio^1,2, Travis Gagie², Dominik Köppl³

¹GSSI, Italy.

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

|August 7, 2024

Summary

This summary is machine-generated.

We introduce a novel sampling technique for Longest Common Prefix (LCP) arrays on Wheeler Deterministic Finite Automata (DFAs). This method enables efficient LCP array access with reduced space complexity, improving matching statistics computation.

Keywords:

LCP array Matching statistics Variable-order de Bruijn graphs Wheeler graphs de Bruijn graphs

More Related Videos

DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers

DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers

Published on: October 25, 2017

Quasi-light Storage for Optical Data Packets

Quasi-light Storage for Optical Data Packets

Published on: February 6, 2014

Related Experiment Videos

Last Updated: Jun 17, 2025

Author Spotlight: Introduction to Active Probe Atomic Force Microscopy with Quattro-Parallel Cantilever Arrays

Author Spotlight: Introduction to Active Probe Atomic Force Microscopy with Quattro-Parallel Cantilever Arrays

Published on: June 13, 2023

DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers

DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers

Published on: October 25, 2017

Quasi-light Storage for Optical Data Packets

Quasi-light Storage for Optical Data Packets

Published on: February 6, 2014

Area of Science:

Theoretical Computer Science
Data Structures and Algorithms
Stringology and Automata Theory

Background:

The Longest Common Prefix (LCP) array, crucial for string processing, has been generalized to Wheeler Deterministic Finite Automata (DFAs).
Existing LCP array storage for Wheeler DFAs requires O(n) bits, which can be space-inefficient compared to compact DFA representations like BOSS.
Efficient computation of matching statistics on Wheeler DFAs is hindered by the space requirements of the LCP array.

Purpose of the Study:

To develop a space-efficient method for accessing LCP array entries in Wheeler DFAs.
To establish a space-time tradeoff for computing matching statistics on Wheeler DFAs.
To improve the time complexity for navigating variable-order de Bruijn graphs using augmented BOSS representations.

Main Methods:

A novel sampling technique is proposed to enable logarithmic time access to LCP array entries.
This technique requires only a linear number of bits for storage, significantly reducing space complexity.
The BOSS representation of de Bruijn graphs is augmented to achieve faster navigation of variable-order de Bruijn graphs.

Main Results:

The proposed sampling technique allows LCP array access in O(log n) time while using only O(n) bits of space.
A new space-time tradeoff is achieved for computing matching statistics on Wheeler DFAs.
Navigation of variable-order de Bruijn graphs is improved to logarithmic time complexity in n, outperforming previous linear bounds.

Conclusions:

The developed sampling technique offers a practical solution for space-efficient LCP array management in Wheeler DFAs.
This research provides significant improvements in computing matching statistics and navigating de Bruijn graphs.
The findings contribute to the development of more compact and faster data structures for automata and graph representations.