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 (79)
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
This page was built for publication: Replacing suffix trees with enhanced suffix arrays
