This summer three publications from the group Algorithmic Bioinformatics were awarded at different international conferences.
In Small Searchable κ-Spectra via Subset Rank Queries on the Spectral Burrows-Wheeler Transform postdoctoral researcher Jarno Alanko, professor Simon Puglisi and research assistant Jaakko Vuohtoniemi introduce the Spectral Burrows-Wheeler Transform (SBWT), a static representation of the k-length substrings of a genomic collection (k-spectrum). In the publication, the team also proposed different succinct representations of the SBWT and experimentally demonstrate their dominance to the state-of-the-art. The work was presented at the 2nd SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 23) and received the best paper prize.
In Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond doctoral researcher Manuel Caceres shows algorithms solving the string matching problem between a string and a directed acyclic graph (DAG), a fundamental problem in pangenomics and modern bioinformatics. While the problem admits a quadratic lower-bound, the algorithms developed by the doctoral researcher run in linear time for an broad class of DAGs: k-funnels. The work was presented at the 34th Annual Symposium on Combinatorial Pattern Matching (CPM 23) and it was chosen as the best paper.
Finally, in Minimum Chain Cover in Almost Linear Time doctoral researcher Manuel Caceres shows a fast algorithm to find a decomposition of a DAG into a minimum number of chains (path in the transitive closure) or minimum chain cover (MCC). Finding an MCC is a fundamental problem with applications to pangenomics and multi-assembly. The algorithm developed by the doctoral researcher is the first to run in almost linear time in the size of the DAG. The work was presented at the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023) and received the best student paper award of track A.