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

Space-efficient whole genome comparisons with Burrows-Wheeler transforms.

Ross A Lippert1

  • 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
|May 11, 2005
PubMed
Summary
This summary is machine-generated.

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

The u-series: A separable decomposition for electrostatics computation with improved accuracy.

The Journal of chemical physics·2020
Same author

Equipartition and the Calculation of Temperature in Biomolecular Simulations.

Journal of chemical theory and computation·2015
Same author

Accurate and efficient integration for molecular dynamics simulations at constant temperature and pressure.

The Journal of chemical physics·2013
Same author

A common, avoidable source of error in molecular dynamics integrators.

The Journal of chemical physics·2007
Same author

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

Journal of computational biology : a journal of computational molecular cell biology·2005
Same author

Finding anchors for genomic sequence comparison.

Journal of computational biology : a journal of computational molecular cell biology·2005

A new compressed suffix array (CSA) data structure significantly reduces memory requirements for genome alignment. This breakthrough enables whole-mammalian genome comparisons on standard workstations with limited RAM.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Mammalian genome alignment is crucial for comparative genomics.
  • Existing time-efficient data structures like suffix trees demand excessive memory (O(n log n) space), exceeding typical workstation capabilities.
  • High memory usage limits large-scale whole-genome comparative projects.

Purpose of the Study:

  • To introduce a novel, space-efficient data structure for mammalian genome alignment.
  • To enable whole-genome comparisons on resource-constrained hardware.
  • To present an implementation demonstrating practical application and performance.

Main Methods:

  • Development of a compressed suffix array (CSA) using the Burrows-Wheeler transform.
  • Implementation of the CSA data structure (bbbwt) for exact match computation.

Related Experiment Videos

  • Comparative analysis of the CSA's time and space efficiency against traditional methods.

    • Main Results:

    • The CSA achieves O(n) space complexity, significantly reducing memory footprint compared to suffix trees.
    • The bbbwt implementation aligns mammalian genomes on systems with < 2 GB RAM.
    • The CSA-based approach offers superior performance over other data structures in terms of space efficiency.

    Conclusions:

    • The compressed suffix array offers a viable solution for memory-intensive genome alignment tasks.
    • This data structure democratizes whole-genome comparative analysis by lowering hardware barriers.
    • The bbbwt implementation demonstrates the practical feasibility and efficiency of the CSA for large-scale genomic studies.