20 citations · 52 across the 18 of their papers we have counts for
25 papers
Pangenome Optimization via Elastic Degenerate Strings
Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti +1
An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be nat…
Quantum Pattern Matching in Generalised Degenerate Strings
Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen
A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set…
Adaptive encodings for small and fast compressed suffix arrays
Diego Díaz-Domínguez, Veli Mäkinen
Compressed suffix arrays (CSAs) index large repetitive collections and are key in many text applications. The r-index and its derivatives combine the run-length Burrows-Wheeler Tra…
Finding Maximal Exact Matches in Graphs
Nicola Rizzo, Manuel Cáceres, Veli Mäkinen
We study the problem of finding maximal exact matches (MEMs) between a query string and a labeled graph . MEMs are an important class of seeds, often used in seed-chain-exte…
Elastic Founder Graphs Improved and Enhanced
Nicola Rizzo, Massimo Equi, Tuukka Norri +1
Indexing labeled graphs for pattern matching is a central challenge of pangenomics. Equi et al. (Algorithmica, 2022) developed the Elastic Founder Graph () representi…
From Bit-Parallelism to Quantum String Matching for Labelled Graphs
Massimo Equi, Arianne Meijer - van de Griend, Veli Mäkinen
Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor , where is the computer word size. A classic example is computing the edit distanc…
Chaining of Maximal Exact Matches in Graphs
Nicola Rizzo, Manuel Cáceres, Veli Mäkinen
We show how to chain maximal exact matches (MEMs) between a query string and a labeled directed acyclic graph (DAG) to solve the longest common subsequence (LCS) prob…
Linear Time Construction of Indexable Elastic Founder Graphs
Nicola Rizzo, Veli Mäkinen
Pattern matching on graphs has been widely studied lately due to its importance in genomics applications. Unfortunately, even the simplest problem of deciding if a string appears a…
Algorithms and Complexity on Indexing Founder Graphs
Massimo Equi, Tuukka Norri, Jarno Alanko +3
We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this proble…
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…
Assembling Omnitigs using Hidden-Order de Bruijn Graphs
Diego Díaz-Domínguez, Djamal Belazzougui, Travis Gagie +3
De novo DNA assembly is a fundamental task in Bioinformatics, and finding Eulerian paths on de Bruijn graphs is one of the dominant approaches to it. In most of the cases, there ma…
Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time
Tuukka Norri, Bastien Cazaux, Dmitry Kosolobov +1
Given a threshold and a set of haplotype sequences, each having length , the minimum segmentation problem for founder reconstruction…
Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics
Romeo Rizzi, Massimo Cairo, Veli Mäkinen +2
Covering alignment problems arise from recent developments in genomics; so called pan-genome graphs are replacing reference genomes, and advances in haplotyping enable full content…
Linear-time string indexing and analysis in small space
Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen +1
The field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array (CSA) by Grossi and Vitter (STOC 2000) and the FM-index by Fe…
Fully Dynamic de Bruijn Graphs
Djamal Belazzougui, Travis Gagie, Veli Mäkinen +1
We present a space- and time-efficient fully dynamic implementation de Bruijn graphs, which can also support fixed-length jumbled pattern matching.
Interval scheduling maximizing minimum coverage
Veli Mäkinen, Valeria Staneva, Alexandru Tomescu +1
In the classical interval scheduling type of problems, a set of jobs, characterized by their start and end time, need to be executed by a set of machines, under various constra…
A Novel Combinatorial Method for Estimating Transcript Expression with RNA-Seq: Bounding the Number of Paths
Alexandru I. Tomescu, Anna Kuosmanen, Romeo Rizzi +1
RNA-Seq technology offers new high-throughput ways for transcript identification and quantification based on short reads, and has recently attracted great interest. The problem is…
Pattern Kits
Travis Gagie, Kalle Karhu, Juha Kärkkäinen +2
Suppose we have just performed searches in a self-index for two patterns and and now we want to search for their concatenation \A B); how can we best make use of our previo…
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…