Related Experiment Video
Updated: Apr 26, 2026
08:21
Curation of Computational Chemical Libraries Demonstrated with Alpha-Amino Acids
Published on: April 13, 2022
2.5K
An Elegant Algorithm for the Construction of Suffix Arrays
Sanguthevar Rajasekaran1, Marius Nicolae1
1Dept. of Computer Science and Engineering, Univ. of Connecticut, Storrs, CT, USA.
Journal of Discrete Algorithms (Amsterdam, Netherlands)
|July 22, 2014
Summary
We introduce a new, simple, and efficient algorithm for suffix array construction that runs in linear time with high probability. This algorithm is easily parallelizable and offers significant speedups for string processing tasks.
Area of Science:
- Computer Science
- Bioinformatics
- Data Structures
Background:
- Suffix arrays are crucial data structures for string processing in diverse fields.
- Existing suffix array construction algorithms (SACAs) have limitations in practical efficiency.
- There is a need for faster and more efficient SACAs.
Purpose of the Study:
- To present a novel, elegant, and efficient algorithm for suffix array construction.
- To develop a parallelizable algorithm for suffix array construction.
- To introduce RadixSA, an algorithm with improved worst-case runtime.
Main Methods:
- Developed a new linear-time suffix array construction algorithm (SACA) with high probability.
- Proved a lemma on ℓ-mers of random strings for potential independent applications.
- Introduced RadixSA, an algorithm utilizing the new SACA, with O(n log n) worst-case runtime.
Main Results:
- The new SACA is one of the simplest known and offers a new approach to construction.
- The algorithm is easily parallelizable, with implementations on various parallel models.
- RadixSA demonstrates competitive performance, ranking among the fastest algorithms in empirical comparisons.
Conclusions:
- The presented algorithm offers a theoretically sound and practically efficient solution for suffix array construction.
- The RadixSA algorithm and its underlying techniques have the potential to accelerate other SACAs.
- The freely available C++ source code facilitates adoption and further research.
More Related Videos
Related Concept Videos
01:30Arithmetic Sequences
340
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...
340
01:15Construction of Frequency Distribution
9.9K
A frequency distribution table can be constructed using the steps given below.
First, make a table with two columns—one with the title of the data that needs to be organized, and the other column for frequency. [Draw a third column for tally marks if needed]. Then, take a look at the items given in the data set and decide if an ungrouped frequency distribution table or a grouped frequency distribution table would be more suitable. If there are large sets of different values, then it is...
First, make a table with two columns—one with the title of the data that needs to be organized, and the other column for frequency. [Draw a third column for tally marks if needed]. Then, take a look at the items given in the data set and decide if an ungrouped frequency distribution table or a grouped frequency distribution table would be more suitable. If there are large sets of different values, then it is...
9.9K
01:05Maxam-Gilbert Sequencing
10.5K
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...
10.5K
01:57Sanger Sequencing
800.5K
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
800.5K
02:27Preparation of Alkynes: Alkylation Reaction
9.2K
Introduction
Alkylation of terminal alkynes with primary alkyl halides in the presence of a strong base like sodium amide is one of the common methods for the synthesis of longer carbon-chain alkynes. For example, treatment of 1-propyne with sodium amide followed by reaction with ethyl bromide yields 2-pentyne.
Alkylation of terminal alkynes with primary alkyl halides in the presence of a strong base like sodium amide is one of the common methods for the synthesis of longer carbon-chain alkynes. For example, treatment of 1-propyne with sodium amide followed by reaction with ethyl bromide yields 2-pentyne.
9.2K
01:22Sums of Power
196
In definite integration, Riemann sums approximate the area under a curve by dividing it into subintervals and summing the areas of rectangles. When these approximations follow predictable numerical patterns, such as arithmetic or polynomial sequences, sum formulas offer a more efficient and accurate way to compute the result. In particular, the sum of consecutive integers, squares, and cubes plays an essential role in simplifying these calculations, especially when dealing with uniform...
196