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

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

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...

You might also read

Related Articles

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

Sort by

Same author

Building genomic data structures from compressed representations using prefix-free parsing.

Genome research·2026

Same author

Faster run-length compressed suffix arrays.

Oasics : openaccess series in informatics·2026

Same author

Scalable and comprehensive mosaic variant calling using DRAGEN.

medRxiv : the preprint server for health sciences·2026

Same author

RAmpSim: A Thermodynamic Simulator for Hybridization Capture in Metagenomic Sequencing.

bioRxiv : the preprint server for biology·2025

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

Toward security-aware portable sequencing.

Nature communications·2025

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

See all related articles

Search research articles

Home
Computing The Original Ebwt Faster, Simpler, And With Less Memory.

Home
Computing The Original Ebwt Faster, Simpler, And With Less Memory.

Related Experiment Video

Author Spotlight: Advancing the Study of Brain-Heart Interplay with a Comprehensive EEGLAB Plugin for Multimodal Signal Analysis

Author Spotlight: Advancing the Study of Brain-Heart Interplay with a Comprehensive EEGLAB Plugin for Multimodal Signal Analysis

Published on: April 26, 2024

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

Christina Boucher¹, Davide Cenzato², Zsuzsanna Lipták²

¹Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, United States.

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

|May 14, 2024

View abstract on PubMed

Summary

This summary is machine-generated.

This study introduces a new linear-time algorithm for the extended Burrows-Wheeler Transform (eBWT), crucial for genomic sequence analysis. The novel method, pfpebwt, significantly speeds up the construction of eBWT for large genomic collections, improving efficiency and memory usage.

Keywords:

Data compression Data structures design and analysis Pattern matching SAIS algorithm Theory of computation extended BWT omega-order prefix-free parsing

More Related Videos

Guidelines and Experience Using Imaging Biomarker Explorer IBEX for Radiomics

Guidelines and Experience Using Imaging Biomarker Explorer IBEX for Radiomics

Published on: January 8, 2018

Author Spotlight: Accelerating Research on Bacterial Extracellular Vesicles Separation and Heterogeneity

Author Spotlight: Accelerating Research on Bacterial Extracellular Vesicles Separation and Heterogeneity

Published on: September 1, 2023

Related Experiment Videos

Author Spotlight: Advancing the Study of Brain-Heart Interplay with a Comprehensive EEGLAB Plugin for Multimodal Signal Analysis

Author Spotlight: Advancing the Study of Brain-Heart Interplay with a Comprehensive EEGLAB Plugin for Multimodal Signal Analysis

Published on: April 26, 2024

Guidelines and Experience Using Imaging Biomarker Explorer IBEX for Radiomics

Guidelines and Experience Using Imaging Biomarker Explorer IBEX for Radiomics

Published on: January 8, 2018

Author Spotlight: Accelerating Research on Bacterial Extracellular Vesicles Separation and Heterogeneity

Author Spotlight: Accelerating Research on Bacterial Extracellular Vesicles Separation and Heterogeneity

Published on: September 1, 2023

Area of Science:

Bioinformatics
Computational Biology
String Algorithms

Background:

The Burrows-Wheeler Transform (BWT) is vital for genomic data analysis, enabling compression and substring queries.
The extended Burrows-Wheeler Transform (eBWT) was defined to handle collections of strings, maintaining order independence.
Existing eBWT methods often disregard the original order-independent property, necessitating improved algorithms.

Purpose of the Study:

To present a novel, linear-time algorithm for constructing the original extended Burrows-Wheeler Transform (eBWT).
To develop an efficient method for computing the BWT of a single string without special symbols or Lyndon rotations.
To enable the construction of eBWT on large genomic sequence collections by combining the new eBWT algorithm with prefix-free parsing (PFP).

Main Methods:

A new linear-time algorithm for the original eBWT construction, avoiding preprocessing steps.
A linear-time algorithm for single-string BWT computation, omitting end-of-string symbols and Lyndon rotations.
Integration of the eBWT algorithm with a prefix-free parsing (PFP) variation for large-scale genomic data.

Main Results:

The developed algorithm (pfpebwt) achieves the fastest construction times for eBWT on large genomic collections, with speedups up to 7.6x.
Peak memory usage of pfpebwt is at most 2x that of the second-best method.
Compared to methods reporting suffix array samples, pfpebwt offers a 57.1x improvement in peak memory.

Conclusions:

The new eBWT construction algorithm is efficient and practical for analyzing large genomic datasets.
pfpebwt provides a significant advancement in speed and memory efficiency for genomic sequence analysis tasks.
The publicly available source code facilitates further research and application of these improved BWT algorithms.