1,721,175 research outputs found
StringMasters 2012 & 2013 Special Issue - volume 1 (Editorial)
No full textEditorial for the special issue on the StringMasters workshops 2012 and 2013, which took place in London, Rouen, Verona, and Prague
Combinatorial Pattern Matching, 16th Annual Symposium, CPM 2005, Jeju Island, Korea, June 19-22, 2005, Proceedings Springer 2005
No full textDatasets used in "Fast phylogenetic inference from typing data"
No full textReal datasets used in the paper "Fast phylogenetic inference from typing data", by João A Carriço, Maxime Crochemore, Alexandre P Francisco, Solon P Pissis, Bruno Ribeiro-Gonçalves, and Cátia Vaz, Algorithms for Molecular Biology 13 (1), 1-14, 2018. Check the paper for more information on the datasets
A Constant-Space Comparison-Based Algorithm for Computing the Burrows-Wheeler Transform
No full textWe introduce the problem of computing the Burrows- Wheeler Transform (BWT) using just O(1) additional space. Our in-place algorithm does not need the explicit storage for the suffix sort array and the output array, as typically required in previous work. It relies on the combinatorial properties of the BWT, and runs in O(n2) time in the comparison model using O(1) extra memory cells, apart from the array of n cells storing the n characters of the input text. We also discuss some time-space trade-offs for the inverse algorithm to obtain the text from the given BWT. \ 2013 Springer-Verlag.</p
Relative FM-Indexes
No full textIntuitively, if two strings S-1 and S-2 are sufficiently similar and we already have an FM-index for S-1 then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for S-2. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems
I/O-efficient dictionary search with one edit error
No full textThis paper studies the 1-error dictionary search problem in external memory. The input is a set D of strings whose characters are drawn from a constant-size alphabet. Given a string q, a query reports the ids of all strings in D that are within 1 edit distance from q. We give a structure occupying O(n/B) blocks that answers a query in O(1 + m/wB + k/B) I/Os, where n is the total length of all strings in D, m is the length of q, k is the number of ids reported, w is the size of a machine word, and B is the number of words in a block
Towards Distance-Based Phylogenetic Inference in Average-Case Linear-Time
Full text linkComputing genetic evolution distances among a set of taxa dominates the running time of many phylogenetic inference methods. Most of genetic evolution distance definitions rely, even if indirectly, on computing the pairwise Hamming distance among sequences or profiles. We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given Hamming distance threshold. This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method
Applied combinatorics on words
No full textA collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé, With a preface by Berstel and Perri
- …
