Results 31 to 40 of about 14,384 (164)
Efficient computation of absent words in genomic sequences
BMC Bioinformatics, 2008 Background Analysis of sequence composition is a routine task in genome research. Organisms are characterized by their base composition, dinucleotide relative abundance, codon usage, and so on.
Herold Julia +2 more
doaj +1 more source
On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching [PDF]
, 2016 We present parallel algorithms for exact and approximate pattern matching with suffix arrays, using a CREW-PRAM with $p$ processors. Given a static text of length $n$, we first show how to compute the suffix array interval of a given pattern of length $m$
Fischer, Johannes +2 more
core +2 more sources
Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Companion Volume, Short Papers on XX - NAACL '07, 2007 Suppose we have a large dictionary of strings. Each entry starts with a figure of merit (popularity). We wish to find the k-best matches for a substring, s, in a dictinoary, dict. That is, grep s dict | sort -n | head -k, but we would like to do this in sublinear time.
Kenneth Church +2 more
openaire +1 more source
Variable-order reference-free variant discovery with the Burrows-Wheeler Transform
BMC Bioinformatics, 2020 Background In [Prezza et al., AMB 2019], a new reference-free and alignment-free framework for the detection of SNPs was suggested and tested. The framework, based on the Burrows-Wheeler Transform (BWT), significantly improves sensitivity and precision ...
Nicola Prezza +3 more
doaj +1 more source
Structator: fast index-based search for RNA sequence-structure patterns
BMC Bioinformatics, 2011 Background The secondary structure of RNA molecules is intimately related to their function and often more conserved than the sequence. Hence, the important task of searching databases for RNAs requires to match sequence-structure patterns. Unfortunately,
Will Sebastian +4 more
doaj +1 more source
New Algorithms for Position Heaps
, 2013 We present several results about position heaps, a relatively new alternative to suffix trees and suffix arrays. First, we show that, if we limit the maximum length of patterns to be sought, then we can also limit the height of the heap and reduce the ...
A. Ehrenfeucht +7 more
core +1 more source
Detecting One-variable Patterns [PDF]
, 2017 Given a pattern $p = s_1x_1s_2x_2\cdots s_{r-1}x_{r-1}s_r$ such that $x_1,x_2,\ldots,x_{r-1}\in\{x,\overset{{}_{\leftarrow}}{x}\}$, where $x$ is a variable and $\overset{{}_{\leftarrow}}{x}$ its reversal, and $s_1,s_2,\ldots,s_r$ are strings that contain
A Amir +17 more
core +1 more source
Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space [PDF]
, 2019 Indexing highly repetitive texts - such as genomic databases, software repositories and versioned text collections - has become an important problem since the turn of the millennium.
Gagie, Travis +2 more
core +3 more sources
Counting Suffix Arrays and Strings
Theoretical Computer Science, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Schürmann, Klaus-Bernd, Stoye, Jens
openaire +3 more sources
External memory BWT and LCP computation for sequence collections with applications
Algorithms for Molecular Biology, 2019 Background Sequencing technologies produce larger and larger collections of biosequences that have to be stored in compressed indices supporting fast search operations.
Lavinia Egidi +3 more
doaj +1 more source