74 citations · 157 across the 11 of their papers we have counts for
12 papers · 1 filter
Wheeler maps
Andrej Baláz, Travis Gagie, Adrián Goga +4
Motivated by challenges in pangenomic read alignment, we propose a generalization of Wheeler graphs that we call Wheeler maps. A Wheeler map stores a text and an assignme…
Haplotype-aware graph indexes
Jouni Sirén, Erik Garrison, Adam M. Novak +2
The variation graph toolkit (VG) represents genetic variation as a graph. Each path in the graph is a potential haplotype, though most paths are unlikely recombinations of true hap…
RLZAP: Relative Lempel-Ziv with Adaptive Pointers
Anthony J. Cox, Andrea Farruggia, Travis Gagie +2
Relative Lempel-Ziv (RLZ) is a popular algorithm for compressing databases of genomes from individuals of the same species when fast random access is desired. With Kuruppu et al.'s…
Indexing Variation Graphs
Jouni Sirén
Variation graphs, which represent genetic variation within a population, are replacing sequences as reference genomes. Path indexes are one of the most important tools for working…
Burrows-Wheeler transform for terabases
Jouni Sirén
In order to avoid the reference bias introduced by mapping reads to a reference genome, bioinformaticians are investigating reference-free methods for analyzing sequenced genomes.…
Relative Suffix Trees
Andrea Farruggia, Travis Gagie, Gonzalo Navarro +2
Suffix trees are one of the most versatile data structures in stringology, with many applications in bioinformatics. Their main drawback is their size, which can be tens of times l…
Relative Select
Christina Boucher, Alexander Bowe, Travis Gagie +2
Motivated by the problem of storing coloured de Bruijn graphs, we show how, if we can already support fast select queries on one string, then we can store a little extra informatio…
Document Counting in Practice
Travis Gagie, Aleksi Hartikainen, Juha Kärkkäinen +3
We address the problem of counting the number of strings in a collection where a given pattern appears, which has applications in information retrieval and data mining. Existing so…
Reusing an FM-index
Djamal Belazzougui, Travis Gagie, Simon Gog +2
Intuitively, if two strings and are sufficiently similar and we already have an FM-index for then, by storing a little extra information, we should be able to reu…
Document Retrieval on Repetitive Collections
Gonzalo Navarro, Simon J. Puglisi, Jouni Sirén
Document retrieval aims at finding the most important documents where a pattern appears in a collection of strings. Traditional pattern-matching techniques yield brute-force docume…
Indexing Finite Language Representation of Population Genotypes
Jouni Sirén, Niko Välimäki, Veli Mäkinen
With the recent advances in DNA sequencing, it is now possible to have complete genomes of individuals sequenced and assembled. This rich and focused genotype information can be us…
Sampled Longest Common Prefix Array
Jouni Sirén
When augmented with the longest common prefix (LCP) array and some other structures, the suffix array can solve many string processing problems in optimal time and space. A compres…