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

A space-efficient construction of the Burrows-Wheeler transform for genomic data.

Ross A Lippert1, Clark M Mobarry, Brian P Walenz

  • 1Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. lippert@math.mit.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|October 6, 2005
PubMed
Summary

This study introduces a more space-efficient algorithm for constructing compressed suffix arrays (CSAs), crucial for exact string matching in computational biology. The new method significantly reduces memory usage for small alphabets, making large-scale genome analysis more practical.

Related Concept Videos

You might also read

Related Articles

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

Sort by
Same author

Fully Phased Telomere-to-Telomere Assemblies for Thoroughbred Horse and Donkey Haplotypes derived from a Mule Illuminate the Peculiar Evolution of Equid Centromeres.

bioRxiv : the preprint server for biology·2026
Same author

The formation and propagation of human Robertsonian chromosomes.

Nature·2025
Same author

Verkko2 integrates proximity-ligation data with long-read De Bruijn graphs for efficient telomere-to-telomere genome assembly, phasing, and scaffolding.

Genome research·2025
Same author

The formation and propagation of human Robertsonian chromosomes.

bioRxiv : the preprint server for biology·2024
Same author

The complete sequence of a human Y chromosome.

Nature·2023
Same author

Telomere-to-telomere assembly of diploid chromosomes with Verkko.

Nature biotechnology·2023

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Data Structures

Background:

  • Exact string matching algorithms are vital in computational biology.
  • Suffix trees and suffix arrays are common data structures for these tasks.
  • Growing sequence databases necessitate more space-efficient exact matching approaches.

Purpose of the Study:

  • To develop a more space-efficient algorithm for constructing compressed suffix arrays (CSAs).
  • To reduce memory requirements for CSA construction, particularly for small alphabets like nucleotide sequences.
  • To demonstrate the practicality of the new CSA construction and querying implementation using real genome data.

Main Methods:

  • Implementation of a novel compressed suffix array (CSA) construction algorithm.

Related Experiment Videos

  • Focus on achieving asymptotic time and space bounds for CSA construction.
  • Utilizing the Burrows-Wheeler transform as the basis for the CSA.

    • Main Results:

    • The new implementation achieves asymptotic bounds for CSA construction and querying.
    • It uses 1/2 (1+|summation|)(1+epsilon) bits per character for small alphabets, a 2x space reduction for nucleotide sequences compared to prior methods.
    • Experimental results on publicly available genome data validate the approach's efficiency.

    Conclusions:

    • The developed CSA construction algorithm offers significant space savings for biological sequence data.
    • This advancement makes large-scale sequence analysis more feasible by reducing memory footprint.
    • The practical performance on genome data confirms the utility of this space-efficient approach.