5 citations · 6 across the 4 of their papers we have counts for
9 papers
Tailoring r-index for metagenomics
Dustin Cobas, Veli Mäkinen, Massimiliano Rossi
A basic problem in metagenomics is to assign a sequenced read to the correct species in the reference collection. In typical applications in genomic epidemiology and viral metageno…
Linear Time Construction of Indexable Founder Block Graphs
Veli Mäkinen, Bastien Cazaux, Massimo Equi +2
We introduce a compact pangenome representation based on an optimal segmentation concept that aims to reconstruct founder sequences from a multiple sequence alignment (MSA). Such f…
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu
We consider the following string matching problem on a node-labeled graph : given a pattern string , decide whether there exists a path in whose concatenation of no…
Chaining with overlaps revisited
Veli Mäkinen, Kristoffer Sahlin
Chaining algorithms aim to form a semi-global alignment of two sequences based on a set of anchoring local alignments as input. Depending on the optimization criteria and the exact…
On the Complexity of Exact Pattern Matching in Graphs: Determinism and Zig-Zag Matching
Massimo Equi, Roberto Grossi, Alexandru I. Tomescu +1
Exact pattern matching in labeled graphs is the problem of searching paths of a graph that spell the same string as the given pattern . This basic problem can be…
On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree
Massimo Equi, Roberto Grossi, Veli Mäkinen
Exact pattern matching in labeled graphs is the problem of searching paths of a graph that spell the same string as the pattern . This basic problem can be found…