Related Experiment Video
Updated: Apr 29, 2026

Self-Assembly of Gamma-Modified Peptide Nucleic Acids into Complex Nanostructures in Organic Solvent Mixtures
Published on: June 26, 2020
Using the Sadakane compressed suffix tree to solve the all-pairs suffix-prefix problem
Maan Haj Rachid1, Qutaibah Malluhi1, Mohamed Abouelhoda2
1KINDI Lab for Computing Research, Qatar University P.O. Box 2713, Doha, Qatar.
Abstract:
The all-pairs suffix-prefix matching problem is a basic problem in string processing. It has an application in the de novo genome assembly task, which is one of the major bioinformatics problems. Due to the large size of the input data, it is crucial to use fast and space efficient solutions. In this paper, we present a space-economical solution to this problem using the generalized Sadakane compressed suffix tree. Furthermore, we present a parallel algorithm to provide more speed for shared memory computers. Our sequential and parallel algorithms are optimized by exploiting features of the Sadakane compressed index data structure. Experimental results show that our solution based on the Sadakane's compressed index consumes significantly less space than the ones based on noncompressed data structures like the suffix tree and the enhanced suffix array. Our experimental results show that our parallel algorithm is efficient and scales well with increasing number of processors.
Related Concept Videos
Sign Test for Matched Pairs
To conduct the sign test, we first calculate the differences in...
Interference: Path Lengths
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...
Distance Problem
¹H NMR: Pople Notation
A proton...
Arithmetic Sequences
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...

