Publications

Here is a list of publications of the Algorithmic Bioinformatics Lab.

Best paper awards

Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian, Myuji Matsuda, and Simon J. Puglisi
Height-Bounded Lempel-Ziv Encodings
32nd Annual European Symposium on Algorithms (ESA 2024)
Best Paper Award in Track B of ESA 2024
Andreas Grigorjew, Fernando H. C. Dias, Andrea Cracco, Romeo Rizzi, Alexandru I. Tomescu
Accelerating ILP solvers for Minimum Flow Decompositions through search space and dimensionality reductions
SEA 2024 - 22nd International Symposium on Experimental Algorithms, Leibniz International Proceedings in Informatics (LIPIcs) 301, 14:1--14:19, 2024
Runner-up for the Best Paper Award at SEA 2024 (i.e. 2nd place)
Manuel Cáceres
Minimum Chain Cover in Almost Linear Time
ICALP 2023: 31:1-31:12
Best Student Paper Award at ICALP 2023
Jarno Alanko, Simon J. Puglisi, Jaakko Vuohtoniemi
Small Searchable κ-Spectra via Subset Rank Queries on the Spectral Burrows-Wheeler Transform
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23)
Best Paper Award at ACDA 2023
Manuel Cáceres
Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond
CPM 2023: 7:1-7:19
Best Paper Award at CPM 2023
Sebastian S. Schmidt, Jarno N. Alanko
Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time
Algorithms for Molecular Biology 18(1): 5 (2023)
Best Paper Award at WABI 2022

Additional selected publications

Careen Foord, Andrey D. Prjibelski, Wen Hu, Lieke Michielsen, Andrea Vandelli, Oleksandr Narykov, Brian Evans, Justine Hsu, Natan Belchikov, Julien Jarroux, Yi He, Elizabeth M. Ross, Iman Hajirasouliha, Gian G. Tartaglia, Dmitry Korkin, Alexandru I. Tomescu, Hagen U. Tilgner
A spatial long-read approach at near-single-cell resolution reveals developmental regulation of splicing and polyadenylation sites in distinct cortical layers and cell types
Nature Communications 16(1), 8093, 2025
Nicola Rizzo, Manuel Cáceres, Veli Mäkinen
Exploiting uniqueness: seed-chain-extend alignment on elastic founder graphs
Bioinformatics, Volume 41, Issue Supplement_1, Pages i265–i274, 2025
Proceedings paper from ISMB 2025
Francisco Sena, Romeo Rizzi, Alexandru I. Tomescu
Safe Sequences via Dominators in DAGs for Path-Covering Problems
ESA 2025 - European Symposium on Algorithms (Track B), 55:1--55:17, 2025

Cáceres, Manuel, Cairo, Massimo, Grigorjew, Andreas, Khan, Shahbaz, Mumey, Brendan, Rizzi, Romeo, Tomescu, Alexandru I., Williams, Lucia
Width Helps and Hinders Splitting Flows
ACM Transactions on Algorithms 20(2), Article No.: 13, 2024 (Extended version of ESA 2022 paper)
Nicola Rizzo, Massimo Equi, Tuukka Norri, Veli Mäkinen
Elastic founder graphs improved and enhanced
Theoretical Computer Science, Volume 982, 8 January 2024, 114269

Andrey D. Prjibelski, Alla Mikheenko, Anoushka Joglekar, Alexander Smetanin, Julien Jarroux, Alla L. Lapidus and Hagen U. Tilgner
Accurate isoform discovery with IsoQuant using long reads
Nature Biotechnology volume 41, pages 915–918 (2023)
Andreas Grigorjew, Artur Gynter, Fernando Dias, Benjamin Buchfink, Hajk-Georg Drost*, Alexandru I. Tomescu*
Sensitive inference of alignment-safe intervals from biodiverse protein sequence clusters using EMERALD
Genome Biology 24, 168, 2023 (*Equal contribution. Selected for talk at ISMB 2023)
Sebastian Schmidt, Shahbaz Khan, Jarno Alanko, Giulio E. Pibiri, Alexandru I. Tomescu
Matchtigs: minimum plain text representation of kmer sets
Genome Biology 24, 136, 2023 (Selected for talk at ISMB 2022)
Andrea Cracco, Alexandru I. Tomescu
Extremely fast construction and querying of compacted and colored de Bruijn graphs with GGCAT
Genome Research 33, 1198--1207, 2023 (Short abstract at RECOMB 2023)
Jun Ma, Manuel Cáceres, Leena Salmela, Veli Mäkinen, Alexandru I. Tomescu
Chaining for accurate alignment of erroneous long reads to acyclic variation graphs
Bioinformatics 39(8), 2023.
()
Borja Freire, Susana Ladra, José R. Paramá, and Leena Salmela
ViQUF: De novo viral quasispecies reconstruction using unitig-based flow networks
IEEE/ACM Transactions on Computational Biology and Bioinformatics 20:1550-1562, 2023.
()

Shahbaz Khan, Alexandru I. Tomescu
Optimizing the Safe Flow Decompositions in DAGs
ESA 2022 - European Symposium on Algorithms (Track A), 72:1--72:17, 2022
Fernando H. C. Dias, Lucia Williams, Brendan Mumey, Alexandru I. Tomescu
Fast, Flexible, and Exact Minimum Flow Decompositions via ILP
RECOMB 2022 - 26th Annual International Conference on Research in Computational Molecular Biology, Lecture Notes in Computer Science 13278, 230--245, 2022
Shahbaz Khan, Milla Kortelainen, Manuel Cáceres, Lucia Williams, Alexandru I. Tomescu
Safety and Completeness in Flow Decompositions for RNA Assembly
RECOMB 2022 - 26th Annual International Conference on Research in Computational Molecular Biology, Lecture Notes in Computer Science 13278, 177--192, 2022
Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu
Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
SODA 2022 - ACM-SIAM Symposium on Discrete Algorithms, 359-376, 2022
Riku Walve, Simon J. Puglisi, and Leena Salmela
Space-efficient indexing of spaced seeds for accurate overlap computation of raw optical mapping data
IEEE/ACM Transactions on Computational Biology and Bioinformatics 19:2454–2462, 2022.
()

Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu, Elia C. Zirondelli
Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time
ICALP 2021 - 48th International Colloquium on Automata, Languages, and Programming (Track A), LIPIcs 198, 43:1--43:18, 2021
Kristoffer Sahlin, Veli Mäkinen
Accurate spliced alignment of long RNA sequencing reads
Bioinformatics, Volume 37, Issue 24, Pages 4643–4651, 2021
Borja Freire, Susana Ladra, José R. Paramá, and L. Salmela
Inference of viral quasispecies with a paired de Bruijn graph
Bioinformatics 37(4):473-481, 2021.

Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, Veli Mäkinen
Linear-time String Indexing and Analysis in Small Space
ACM Transactions on Algorithms (TALG), Volume 16, Issue 2, Article No.: 17, Pages 1 - 54, 2020
Veli Mäkinen, Alexandru I. Tomescu, Anna Kuosmanen, Topi Paavilainen, Travis Gagie, Rayan Chikhi
Sparse Dynamic Programming on DAGs with Small Width
ACM Transactions on Algorithms (TALG), Volume 15, Issue 2, Article No.: 29, Pages 1 - 21, 2019
Massimo Equi, Roberto Grossi, Veli Mäkinen, Alexandru I. Tomescu
On the Complexity of String Matching for Graphs
ICALP 2019 - 46th International Colloquium on Automata, Languages and Programming (Track A), LIPIcs 132, 55:1-55:15, 2019

All publications