Replacing suffix trees with enhanced suffix arrays
From MaRDI portal
Publication:876707
DOI10.1016/S1570-8667(03)00065-0zbMath1115.92303WikidataQ56485241 ScholiaQ56485241MaRDI QIDQ876707
Stefan Kurtz, Mohamed Ibrahim Abouelhoda, Enno Ohlebusch
Publication date: 26 April 2007
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Searching and sorting (68P10) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)
Related Items
An external-memory algorithm for string graph construction, Engineering a lightweight external memory suffix array construction algorithm, On succinct representations of binary trees, Lightweight LCP construction for very large collections of strings, An improved algorithm for the all-pairs suffix-prefix problem, Construction of Aho Corasick automaton in linear time for integer alphabets, Computing suffix links for suffix trees and arrays, CROCHEMORE'S REPETITIONS ALGORITHM REVISITED: COMPUTING RUNS, Suffix-sorting via Shannon-Fano-Elias codes, A fast algorithm for the all-pairs suffix-prefix problem, Locating maximal approximate runs in a string, Kings, Name Days, Lazy Servants and Magic, Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis, Succinct Non-overlapping Indexing, Tighter Bounds for the Sum of Irreducible LCP Values, Faster repetition-aware compressed suffix trees based on block trees, Optimal in-place suffix sorting, The principles of informational genomics, On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case, Property Suffix Array with Applications in Indexing Weighted Sequences, Large-scale detection of repetitions, Indexing a sequence for mapping reads with a single mismatch, String matching with alphabet sampling, Searching for smallest grammars on large sequences and application to DNA, Fast, practical algorithms for computing all the repeats in a string, Finding range minima in the middle: approximations and applications, String Covering: A Survey, Bidirectional search in a string with wavelet trees and bidirectional matching statistics, Computational graph pangenomics: a tutorial on data structures and their applications, Motif trie: an efficient text index for pattern discovery with don't cares, The longest common substring problem, Note on the greedy parsing optimality for dictionary-based text compression, An Online Algorithm for Finding the Longest Previous Factors, Better External Memory LCP Array Construction, Using static suffix array in dynamic application: case of text compression by longest first substitution, Fast profile matching algorithms - A survey, Counting suffix arrays and strings, Practical compressed suffix trees, Alphabet-independent algorithms for finding context-sensitive repeats in linear time, DARN! A weighted constraint solver for RNA motif localization, Full-Text Indexes for High-Throughput Sequencing, DNA-Seq Error Correction Based on Substring Indices, The affix array data structure and its applications to RNA secondary structure analysis, Tighter bounds for the sum of irreducible LCP values, Lempel-Ziv Factorization Revisited, Sparse and Truncated Suffix Trees on Variable-Length Codes, Burrows-Wheeler transform and LCP array construction in constant space, Spectral concepts in genome informational analysis, \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity, Engineering parallel string sorting, On-line construction of compact suffix vectors and maximal repeats, Inducing enhanced suffix arrays for string collections, Kernel-based machine learning for fast text mining in R, On space efficient two dimensional range minimum data structures, Computing longest previous factor in linear time and applications, Computing regularities in strings: a survey, Unnamed Item, Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem, Wee LCP, Longest repeats with a block of \(k\) don't cares, Indexing and querying character sets in one- and two-dimensional words, Succinct non-overlapping indexing, Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays, The exact multiple pattern matching problem solved by a reference tree approach, Online Suffix Tree Construction for Streaming Sequences, Permuted Longest-Common-Prefix Array, Finding all maximal perfect haplotype blocks in linear time, Locally Compressed Suffix Arrays, Faster entropy-bounded compressed suffix trees, IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS, THE VIRTUAL SUFFIX TREE, Sliding suffix tree, Space efficient linear time construction of suffix arrays, Faster online computation of the succinct longest previous factor array, LCP Array Construction in External Memory, Faster Compressed Suffix Trees for Repetitive Collections, String inference from longest-common-prefix array, Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies, Suffix trays and suffix trists: structures for faster text indexing
Uses Software
Cites Work
- Sublinear approximate string matching and biological applications
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Suffix Arrays: A New Method for On-Line String Searches
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Linear-Time Construction of Suffix Arrays
- Space Efficient Linear Time Construction of Suffix Arrays
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Algorithms on Strings, Trees and Sequences
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
