Related Experiment Video
Updated: Apr 7, 2026
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
Summary
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.
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.
Related Concept Videos
01:12Maximum 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
01:10Interference: 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...
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
01:02Long-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
01:05Maxam-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...
Challenges of the Maxam-Gilbert Method
The...
13.7K
01:32Chromatin 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
01:30Arithmetic 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