Publications - Graph Algorithms and Bioinformatics
Here is a list of publications of the Graph Algorithms and Bioinformatics Group.
Best paper awards
- 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)
(view)
- Manuel Cáceres
Minimum Chain Cover in Almost Linear Time
ICALP 2023: 31:1-31:12
Best Student Paper Award at ICALP 2023
(view)
- 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
(view)
- 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
(view)
Selected publications
- 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)
(view)
- 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)
(view)
- 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)
(view)
- Manuel Cáceres
Minimum Chain Cover in Almost Linear Time
ICALP 2023: 31:1-31:12
Best Student Paper Award at ICALP 2023
(view)
- 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
(view)
- 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)
(view)
- 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)
(view)
- 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)
(view)
- 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
(view)
- 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
(view) (preprint)
- 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
(view) (preprint)
- 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
(view) (preprint)
- 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
(view) (preprint)
- 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
(view) (extended version)
- 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
(view)
All publications