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

Maximum Size of Aggregate01:12

Maximum Size of Aggregate

1.0K
The maximum size of aggregate is defined as the aperture of the sieve retaining 15 percent or more of the particles present in the aggregate sample. The aggregate's maximum size impacts the concrete's water requirement, workability, and strength. Larger aggregates reduce the surface area needing cement paste coverage, which can lower water needs, thereby allowing a decrease in the water-to-cement ratio when the desired workability and richness of the mix are to be maintained, which can...
1.0K
Interference: Path Lengths01:10

Interference: Path Lengths

2.5K
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...
2.5K
Long-patch Base Excision Repair01:02

Long-patch Base Excision Repair

8.3K
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:
8.3K
Maxam-Gilbert Sequencing01:05

Maxam-Gilbert Sequencing

13.7K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
13.7K
Chromatin Packaging01:32

Chromatin Packaging

20.3K
Each human somatic cell contains 6 billion base pairs of DNA. Each base pair is 0.34 nm long, meaning each diploid cell contains a staggering 2 meters of DNA. This long DNA strand is packed inside a nucleus measuring only 10-20 microns in diameter with the help of specialized DNA-binding proteins called histones. Together they form a compact DNA-protein complex called chromatin. The chromatin is further compacted into higher-order structures. The highest level of compaction is achieved during...
20.3K
Arithmetic Sequences01:30

Arithmetic Sequences

313
An arithmetic sequence is a structured arrangement of numbers where each term is derived by adding a constant value, known as the common difference, to the previous term. This consistent pattern allows for the efficient computation of any term within the sequence as well as the cumulative sum of multiple terms. The formula for finding the nth term of an arithmetic sequence is:Here, aₙ represents the nth term of the sequence, a is the first term, d is the common difference, and n is the...
313

You might also read

Related Articles

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

Sort by
Same author

RLBWT-Based LCP Computation in Compressed Space for Terabase-Scale Pangenome Analysis.

bioRxiv : the preprint server for biology·2026
Same author

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 author

Prefix-free parsing for merging big BWTs.

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

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
See all related articles

Related Experiment Video

Updated: Apr 7, 2026

Design and Synthesis of a Reconfigurable DNA Accordion Rack
07:44

Design and Synthesis of a Reconfigurable DNA Accordion Rack

Published on: August 15, 2018

7.6K

Faster run-length compressed suffix arrays.

Nathaniel K Brown1, Travis Gagie2, Giovanni Manzini3

  • 1Department of Computer Science, Johns Hopkins University, USA.

Oasics : Openaccess Series in Informatics
|April 6, 2026
PubMed
Summary
This summary is machine-generated.

This study optimizes the run-length compressed suffix array (RLCSA) for faster pattern searching. The enhanced RLCSA achieves logarithmic time complexity for finding suffix array intervals, improving text indexing and pattern matching efficiency.

Keywords:
Run-length compressed suffix arraysTheory of computation → Pattern matchinginterpolative codingtwo-level indexing

More Related Videos

DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers
08:00

DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers

Published on: October 25, 2017

7.4K
Determining 3'-Termini and Sequences of Nascent Single-Stranded Viral DNA Molecules during HIV-1 Reverse Transcription in Infected Cells
13:07

Determining 3'-Termini and Sequences of Nascent Single-Stranded Viral DNA Molecules during HIV-1 Reverse Transcription in Infected Cells

Published on: January 30, 2019

10.0K

Related Experiment Videos

Last Updated: Apr 7, 2026

Design and Synthesis of a Reconfigurable DNA Accordion Rack
07:44

Design and Synthesis of a Reconfigurable DNA Accordion Rack

Published on: August 15, 2018

7.6K
DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers
08:00

DNA Nanotubes as a Versatile Tool to Study Semiflexible Polymers

Published on: October 25, 2017

7.4K
Determining 3'-Termini and Sequences of Nascent Single-Stranded Viral DNA Molecules during HIV-1 Reverse Transcription in Infected Cells
13:07

Determining 3'-Termini and Sequences of Nascent Single-Stranded Viral DNA Molecules during HIV-1 Reverse Transcription in Infected Cells

Published on: January 30, 2019

10.0K

Area of Science:

  • Computer Science
  • Data Structures
  • Algorithms

Background:

  • Suffix arrays and their compressed variants are crucial for efficient string processing.
  • The Burrows-Wheeler Transform (BWT) is a key component in compressed text indexing.
  • Existing run-length compressed suffix arrays (RLCSA) offer space efficiency but can be improved for query speed.

Purpose of the Study:

  • To develop an optimized run-length compressed suffix array (RLCSA) with faster query times.
  • To enhance the efficiency of finding suffix array (SA) intervals for pattern matching.
  • To explore the implications of the improved RLCSA for two-level indexing and maximal exact match heuristics.

Main Methods:

  • Storing a run-length compressed suffix array (RLCSA) in O(r log(n/r) + r log σ + σ) bits.
  • Achieving O(log r_a + log log n) time for finding the SA interval of aP.
  • Modifying the RLCSA to achieve O(log r_a) time for finding the SA interval of aP by replacing rank queries with select queries.

Main Results:

  • An RLCSA structure is presented that supports finding the SA interval for aP in O(log r_a + log log n) time.
  • A modified RLCSA achieves O(log r_a) time for finding the SA interval of aP without increasing asymptotic space.
  • The study reviews two-level indexing and discusses potential improvements using the faster RLCSA.

Conclusions:

  • The optimized RLCSA significantly speeds up pattern searching operations.
  • The proposed modifications offer a practical improvement for compressed text indexing.
  • Further research can leverage these advancements for more efficient string matching algorithms.