
Algorithms and Complexity on Indexing Founder Graphs
We study the problem of matching a string in a labeled graph. Previous r...
read it

Tailoring rindex for metagenomics
A basic problem in metagenomics is to assign a sequenced read to the cor...
read it

Linear Time Construction of Indexable Founder Block Graphs
We introduce a compact pangenome representation based on an optimal segm...
read it

Graphs cannot be indexed in polynomial time for subquadratic time string matching, unless SETH fails
We consider the following string matching problem on a nodelabeled grap...
read it

Conditional Indexing Lower Bounds Through SelfReducibility
We provide a general technique to turn a conditional lower bound result ...
read it

Chaining with overlaps revisited
Chaining algorithms aim to form a semiglobal alignment of two sequences...
read it

On the Complexity of Exact Pattern Matching in Graphs: Determinism and ZigZag Matching
Exact pattern matching in labeled graphs is the problem of searching pat...
read it

On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree
Exact pattern matching in labeled graphs is the problem of searching pat...
read it

Assembling Omnitigs using HiddenOrder de Bruijn Graphs
De novo DNA assembly is a fundamental task in Bioinformatics, and findin...
read it

Minimum Segmentation for Pangenomic Founder Reconstruction in Optimal Time
Given a threshold L and a set R = {R_1, ..., R_m} of m haplotype sequenc...
read it
Veli Mäkinen
is this you? claim profile