Related Experiment Video
Updated: Jun 30, 2026
08:48
Stretching Short Sequences of DNA with Constant Force Axial Optical Tweezers
Published on: October 13, 2011
Accelerating String Comparison in RLZ Compressed Sequences via LCE Jumps
Rahul Varki1, Christina Boucher1
1Department of Computer and Information Science and Engineering, University of Florida, Gainesville, Florida, USA 32611.
Biorxiv : the Preprint Server for Biology
|June 29, 2026
Summary
This study introduces an algorithmic framework for sorting sequences of Relative Lempel-Ziv (RLZ) factors, enhancing compressed data construction. RLZ sorting achieved significant speedups, advancing its use as a foundation for efficient data representation.
Area of Science:
- Computer Science
- Data Compression
- Algorithms
Background:
- Relative Lempel-Ziv (RLZ) is effective for compressing large, repetitive data.
- Existing methods lack efficient primitives for compressed construction.
- RLZ is primarily an archival format, not a tractable representation.
Purpose of the Study:
- To develop an algorithmic framework for comparing and sorting RLZ factors.
- To enable efficient compressed construction using RLZ.
- To advance RLZ from an archival format to a workable representation.
Main Methods:
- Introduced a framework for structural comparison and lexicographical sorting of RLZ factor sequences.
- Characterized conditions for direct factor comparisons and RLZ-specific shortcuts.
- Developed a method for extending truncated factors to right-maximal matches.
Main Results:
- RLZ sorting demonstrated speedups of up to 3.93x compared to character-based sorting.
- The framework enables recovery of matching statistics from RLZ parses.
- Established efficient primitives for compressed construction using RLZ.
Conclusions:
- The proposed framework enhances the utility of RLZ for compressed data construction.
- RLZ sorting provides significant performance improvements over traditional methods.
- This work lays the foundation for using RLZ as a basis for advanced compressed data structures.
Related Concept Videos
01:05Maxam-Gilbert Sequencing
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...
01:30Arithmetic Sequences
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 term...
01:22Compacting Factor test
The compacting factor test is a method used to assess the workability of concrete. It is especially suitable for concrete mixes containing aggregates up to one and a half inches in size. This test involves specialized equipment consisting of two truncated cone-shaped hoppers and a cylinder, all with polished interior surfaces to minimize friction.
The procedure begins by placing concrete into the upper hopper without any compaction. Once filled, the bottom door of this hopper is opened,...
The procedure begins by placing concrete into the upper hopper without any compaction. Once filled, the bottom door of this hopper is opened,...
01:19Routh-Hurwitz Criterion II
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first column of the Routh...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first column of the Routh...
01:26Convergence of Sequences
A sequence is a function defined on the natural numbers that assigns a value to each index. It can be understood as an ordered list of terms generated one after another. In mathematical analysis, an important question is whether the terms of a sequence approach a single real number as the index becomes very large. When this happens, the sequence is said to converge, and the value approached is called the limit. From a graphical perspective, convergence means that the plotted terms approach a...
01:28Comparison Tests
An infinite series composed of positive terms may either approach a finite value or increase without bound. Determining which outcome occurs is a central task in calculus, and comparison tests provide structured methods for making this determination. Rather than evaluating a series directly, these tests relate it to another series whose behavior is already known, allowing conclusions to be drawn through logical comparison.The direct comparison test applies to series with positive terms. If each...