Replacing suffix trees with enhanced suffix arrays
Journal of Discrete AlgorithmsPublished 28 February 2004
Mohamed Abouelhoda, Stefan Kurtz, Enno Ohlebusch
Citations667
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This article shows how every algorithm that uses a suffix tree as data structure can systematically be replaced with an algorithm that use an enhanced suffix array and solves the same problem in the same time complexity.
Abstract
The suffix tree is one of the most important data structures in string processing and comparative genomics. However, the space consumption of the suffix tree is a bottleneck in large scale applications such as genome analysis. In this article, we will overcome this obstacle. We will show how every algorithm that uses a suffix tree as data structure can systematically be replaced with an algorithm that uses an enhanced suffix array and solves the same problem in the same time complexity. The generic name enhanced suffix array stands for data structures consisting of the suffix array and additional tables. Our new algorithms are not only more space efficient than previous ones, but they are also faster and easier to implement.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
NatureInitial sequencing and analysis of the human genome
24,579 Citations2001Eric S. Lander, Lauren Linton +250 more
The results of an international collaboration to produce and make freely available a draft sequence of the human genome are reported and an initial analysis is presented, describing some of the insights that can be gleaned from the sequence.
IEEE Transactions on Information TheoryA universal algorithm for sequential data compression
5,467 Citations1977J. Ziv, A. Lempel
The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable- to-block codes designed to match a completely specified source.
Algorithms on strings, trees, and sequences: computer science and computational biology
3,529 Citations1997Dan Gusfield
IEEE Transactions on Information TheoryCompression of individual sequences via variable-rate coding
3,452 Citations1978J. Ziv, A. Lempel
The proposed concept of compressibility is shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences.
Cambridge University Press eBooksAlgorithms on Strings, Trees and Sequences
3,045 Citations1997Dan Gusfield
Ukkonen’s method is the method of choice for most problems requiring the construction of a suffix tree, and it will be presented first because it is easier to understand.
Nucleic Acids ResearchREPuter: the manifold applications of repeat analysis on a genomic scale
2,794 Citations2001Stefan Kurtz
The wide scope of repeat analysis is circumscribes using applications in five different areas of sequence analysis: checking fragment assemblies, searching for low copy repeats, finding unique sequences, comparing gene structures and mapping of cDNA/EST sequences.
A Block-sorting Lossless Data Compression Algorithm
2,362 Citations1994Michael T. Burrows, D. J. Wheeler
A block-sorting, lossless data compression algorithm, and the implementation of that algorithm, that achieves speed comparable to algorithms based on the techniques of Lempel and Ziv, but obtains compression close to the best statistical modelling techniques.
SIAM Journal on ComputingSuffix Arrays: A New Method for On-Line String Searches
1,962 Citations1993Udi Manber, Gene Myers
A new and conceptually simple data structure, called a suffixarray, for on-line string searches is introduced in this paper, and it is believed that suffixarrays will prove to be better in practice than suffixtrees for many applications.
Linear pattern matching algorithms
1,810 Citations1973Peter Weiner
A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented and indicated how to solve several pattern matching problems, including some from [4] in linear time.
Algorithms on strings, trees, and sequences
1,723 Citations1997Dan Gusfield
Nucleic Acids ResearchFast algorithms for large-scale genome alignment and comparison
1,110 Citations2002Arthur L. Delcher
A suffix-tree algorithm that can align the entire genome sequences of eukaryotic and prokaryotic organisms with minimal use of computer time and memory is described and a method to align more distantly related genomes by detecting protein sequence homology is described.
Opportunistic data structures with applications
1,070 Citations2002Paolo Ferragina, Giovanni Manzini
A data structure whose space occupancy is a function of the entropy of the underlying data set is devised, which achieves sublinear space and sublinear query time complexity and is shown how to plug into the Glimpse tool.
Nucleic Acids ResearchAlignment of whole genomes
914 Citations1999Arthur L. Delcher, Simon Kasif +4 more
Using an efficient data structure called a suffix tree, the system is able to rapidly align sequences containing millions of nucleotides and should facilitate analysis of syntenic chromosomal regions, strain-to-strain comparisons, evolutionary comparisons and genomic duplications.
Lecture notes in computer scienceThe LCA Problem Revisited
739 Citations2000Michael A. Bender, Martı́n Farach-Colton
A very simple algorithm for the Least Common Ancestors problem is presented, dispelling the frequently held notion that optimal LCA computation is unwieldy and unimplementable.
Lecture notes in computer scienceLinear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications
465 Citations2001Toru Kasai, Gun-Ho Lee +3 more
It is shown that the algorithm is crucial to the effective use of block-sorting compression and a linear-time algorithm to simulate the bottom-up traversal of a suffix tree with a suffix array combined with the longest common prefix information is presented.
KU ScholarWorks (The University of Kansas)Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching Read More: http://epubs.siam.org/doi/abs/10.1137/S0097539702402354
435 Citations2005Roberto Grossi, Jeffrey Scott Vitter
Lecture notes in computer scienceSimple Linear Work Suffix Array Construction
405 Citations2003Juha Kärkkäinen, Peter Sanders
The skew algorithm for suffix array construction over integer alphabets that can be implemented to run in linear time using integer sorting as its only nontrivial subroutine is introduced.
Symposium on Discrete AlgorithmsFast algorithms for sorting and searching strings
398 Citations1997Jon Bentley, Robert Sedgewick
This work presents theoretical algorithms for sorting and searching multikey data, and derive from them practical C implementations for applications in which keys are character strings, and presents extensions to more complex string problems, such as partial-match searching.
Software Practice and ExperienceReducing the space requirement of suffix trees
333 Citations1999Stefan Kurtz
This work shows that suffix trees store various kinds of redundant information, and exploits these redundancies to obtain more space efficient representations, which can be constructed without extra space, and as fast as previous representations.
Finding maximal repetitions in a word in linear time
322 Citations2003Roman Kolpakov, Grégory Kucherov
This work proves a combinatorial result asserting that the sum of exponents of all maximal repetitions of a word of length n is bounded by a linear function in n, which implies that there is only a linear number of maximal repetition in a word.
Combinatorial Algorithms on Words
288 Citations1985Alberto Apostolico, Zvi Galil
The average-case Cost of the Brute force and the Knuth-Morris-Pratt String Matching Algorithm are compared and the Mellin integral Transform in the Analysis of Algorithms is compared.
The Myriad Virtues of Subword Trees
275 Citations1985Alberto Apostolico
Lecture notes in computer scienceSpace Efficient Linear Time Construction of Suffix Arrays
226 Citations2003Pang Ko, Srinivas Aluru
Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
200 Citations2000Roberto Grossi, Jeffrey Scott Vitter
The result presents for the first time an efficient index whose size is provably linear in the size of the text in the worst case, and for many scenarios, the space is actually sublinear in practice.
Lecture notes in computer scienceLinear-Time Construction of Suffix Arrays
196 Citations2003Dong Kyue Kim, Jeong Seop Sim +2 more
A linear-time algorithm to construct suffix arrays for integer alphabets, which do not use suffix trees as intermediate data structures during its construction, and implies that the time complexity of directly constructing suffix arrays matches that of constructing suffix trees.
AlgorithmicaSublinear approximate string matching and biological applications
186 Citations1994Wonil Chang, Eugene L. Lawler
This work gives an algorithm that is sublinear time0((n/m)k logbm) when the text is random andk is bounded by the threshold m/(logbm + O(1)).
SIAM Journal on ComputingCompressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
184 Citations2005Roberto Grossi, Jeffrey Scott Vitter
Symposium on Discrete AlgorithmsAn experimental study of an opportunistic index
168 Citations2001Paolo Ferragina, Giovanni Manzini
This index combines the compression algorithm proposed by Burrows and Wheeler with the suffix array data structure and is opportunistic in that it takes advantage of the compressibility of the input data by decreasing the space occupancy at no significant asymptotic slowdown in the query performance.
BioinformaticsEfficient multiple genome alignment
161 Citations2002Michael Höhl, Stefan Kurtz +1 more
New algorithms and a software tool 'Multiple Genome Aligner' (MGA for short) that efficiently computes multiple genome alignments of large, closely related DNA sequences.
Journal of Computer and System SciencesLinear time algorithms for finding and representing all the tandem repeats in a string
161 Citations2004Dan Gusfield, Jens Stoye
An O(|S|)-time algorithm that operates on the suffix tree T(S) for a string S, finding and marking the endpoint of every tandem repeat that occurs in S, improves and generalizes several prior efforts to efficiently capture large subsets of tandem repeats.
Symposium on Discrete AlgorithmsSuccinct representations of lcp information and improvements in the compressed suffix arrays
132 Citations2002Kunihiko Sadakane
Two succinct data structures are introduced for storing the information of lcp, the longest common prefix, between suffixes in the suffix array, and an improvement in the compressed suffix array which supports linear time counting queries for any pattern.
Lecture notes in computer scienceThe Enhanced Suffix Array and Its Applications to Genome Analysis
119 Citations2002Mohamed Abouelhoda, Stefan Kurtz +1 more
This paper presents a uniform framework that enables us to systematically replace every string processing algorithm that is based on a bottomup traversal of a suffix tree by a corresponding algorithm based on an enhanced suffix array (a suffix array enhanced with the lcp-table).
Lecture notes in computer scienceSpace-Economical Algorithms for Finding Maximal Unique Matches
29 Citations2002Wing-Kai Hon, Kunihiko Sadakane
This work shows space-economical algorithms for finding maximal unique matches (MUM's) between two strings which are important in large scale genome sequence alignment problems and proposes three algorithms for different inputs.
UnipiEprints Open Archive (Università di Pisa)On compressing and indexing data
22 Citations2002Paolo Ferragina, Giovanni Manzini
This paper designs two compressed data structures for the full-text indexing problem and exploits the interplay between two compressors: the Burrows-Wheeler algorithm and the LZ78 algorithm.
Computational biologyThe Pathological Consequences and Evolutionary Implications of Recent Human Genomic Duplications
9 Citations2000Christine L. O’Keefe, Evan E. Eichler
Gene duplications create families of related genes that have evolved to recognize a diverse array of odorant molecules and antigens, respectively and increase the number of niches that evolving species may occupy.