Replacing suffix trees with enhanced suffix arrays

By Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch. J. Discrete Algorithms, 2004

775 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/4ca9ea95a0a9846965e86619e646d9ca36930c18

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

Fast Mapping of Short Sequences with Mismatches, Insertions and Deletions Using Index Structures (2009, methodology): “A method computing the a - child of a suffix interval in constant time is described in [2].”
LTRharvest, an efficient and flexible software for de novo detection of LTR retrotransposons (2008, methodology): “The software tool LTRharvest maps the enhanced suffix array into the main memory and begins searching for maximal exact repeats, using the linear time algorithm of [20].”
Spamming botnets: signatures and characteristics (2008, methodology): “For example, based on our metric, a signature AB[1-8]{1,1} is much more specific than [A-Z0-9]{3,3} even though they are of the same length.”
Machine Translation without Words through Substring Alignment (2012, methodology): “We perform the calculation of these statistics using enhanced sufﬁx arrays, a data structure that can efﬁciently calculate all substrings in a corpus (Abouelhoda et al., 2004).”
Linear work suffix array construction (2006, background): “In many applications [Manber and Myers 1993; K¨arkk¨ainen 1995; Kasai et al. 2001; Abouelhoda et al. 2002, 2004], the suf.x array needs to be augmented with the longest common pre.x array lcp that stores the length of the longest common pre.x of SAi and SAi+1 in lcp[i].”
TopHat: discovering splice junctions with RNA-Seq (2009, neutral): “Availability: TopHat is free, open-source software available from http://tophat.cbcb.umd.edu Contact: cole@cs.umd.edu Supplementary information: Supplementary data are available at Bioinformatics online.”
SeqAn An efficient, generic C++ library for sequence analysis (2008, background): “It is the primary index data structure in SeqAn and based on an enhanced suffix array [43].”
Compressed full-text indexes (2007, background): “Hence the search takes worst case time O(m log n) (this can be lowered to O(m + log n) by using more space to store the length of the longest common prefixes between consecutive suffixes [Manber and Myers 1993; Abouelhoda et al. 2004]).”
Adaptive seeds tame genomic sequence comparison. (2011, background): “A suffix tree (Gusfield 1997) or enhanced suffix array (Abouelhoda et al. 2004) would have the fastest theoretical (asymptotic worst-case) run time, but these structures need much memory and we are not sure if they can be adapted to spaced seeds.”
N-gram IDF: A Global Term Weighting Scheme Based on Information Distance (2015, methodology): “First, we use enhanced suffix array [1] (as an alternative of suffix tree) to enumerate valid N-grams of any length.”
Space efficient linear time construction of suffix arrays (2003, methodology): “[2,3] have improved this to O (|P |) time using additional linear time preprocessing, thus making the suffix array based algorithm su In fact, many problems involving top-down or bottom-up traversal of suffix trees can be solved with the same asymptotic run-time bounds using suffix arrays [1–3].”
CRISPRCasFinder, an update of CRISRFinder, includes a portable version, enhanced performance and integrates search for Cas proteins (2018, background): “2 which is itself based on Vmatch version 2.3 (21) (http://www.vmatch.de/) to identify the CRISPR repeats.”
CpGAVAS, an integrated web server for the annotation, visualization, analysis, and GenBank submission of completely sequenced chloroplast genome sequences (2012, methodology): “In step 4, the inverted repeats are identified using the vmatch software tool with default parameters [23].”