Titlebook: String Processing and Information Retrieval; 17th International S Edgar Chavez,Stefano Lonardi Conference proceedings 2010 Springer Berlin

BOOST

On the Hardness of Counting and Sampling Center Stringsom each string in .. The . problem aims to determine the number of unique center strings for a given set of strings . and input parameters ., ℓ, and .. We show . is impossible to solve exactly or even approximately in polynomial time, and that restricting . so that any one of the parameters ., ℓ, or

extrovert

Counting and Verifying Maximal Palindromesh palindrome is represented by a pair (., .), where . is the center and . is the radius of the palindrome. We say that two strings . and . are pal-distinct if .(.) ≠ .(.). Firstly, we describe the number of pal-distinct strings, and show that we can enumerate all pal-distinct strings in time linear

漂亮才会豪华

Identifying SNPs without a Reference Genome by Comparing Raw Readsspecies. However, while single nucleotide polymorphisms (SNPs) are almost routinely identified in model organisms, the detection of SNPs in non model species remains very challenging due to the fact that almost all methods rely on the use of a reference genome. We address here the problem of identif

Androgen

Dynamic Z-Fast Trieslopment of y-fast tries [13]. The dynamic z-fast trie is a very simple, uniform data structure: given a set . of . variable-length strings, it is formed by a standard compacted trie on . (with two additional pointers per node), endowed with a dictionary of size . − 1. With this simple setup, the dyn

Conquest

Improved Fast Similarity Search in Dictionaries and a query word ., we would like to retrieve all words from . that can be transformed into . with . or less edit operations. We present data structures that support fault tolerant queries by generating an index. On top of that, we present a generalization of the method that eases memory consumptio

glamor

Training Parse Trees for Efficient VF Codingtching but moderate compression ratios. Compression ratio of VF codes depends on the parse tree that is used as a dictionary. We propose a method that trains a parse tree by scanning an input text repeatedly, and we show experimentally that it improves the compression ratio of VF codes rapidly to th

Mutter

欲望

Faster Compressed Dictionary Matchingn within . efficiently. When . contains a total of . characters drawn from an alphabet of size ., Hon et al. (2008) gave an .-bit index which supports a query in .(|.| (log.. + log.) + .) time, where .> 0 and . denotes the .th order entropy of .. Very recently, Belazzougui (2010) proposed an elegant

EVEN

Range Queries over Untangled Chainsementation is 2. + .(.) words. The experimental results show that this structure is competitive with the state of the art. We also present an alternative construction algorithm for our structure, which in practice outperforms the original proposal by orders of magnitude.

Conquest

Multiplication Algorithms for Monge Matricesasses. The theoretical and empirical analysis shows that MMT operates in near optimal space and time. Hence we give further insight into an open problem proposed by Landau. The resulting algorithms are relevant for bio-informatics, namely because Monge matrices occur in string alignment problems.