The Algorithmic Bioinformatics group at the Department of Computer Science has had success at the ALGO 2022 algorithmics meeting, where they received the WABI 2022 Best Paper award.
The prize for the best research article of the Workshop on Algorithms in Bioinformatics conference (WABI) was awarded to the research conducted in the Graph Algorithms team led by Associate Professor Alexandru Tomescu. The title of the article is "Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time", and it was written by doctoral student Sebastian Schmidt and doctoral researcher Jarno Alanko.
High-throughput sequencing is a technology reading DNA or RNA sequences. For example, it was used to first assemble the SARS-CoV-2 genome in 2020, which was the basis of the mRNA vaccines in use today. This technology is mainstream in research, but in the near future it can also be crucial in, for example, personalized cancer therapies. The data produced by such technologies is huge, and there is a need both to quickly analyze this data, and to compress it for storage and later use.
The winning paper gives an efficient algorithm for finding a minimum representation of a set of given strings (k-mers), with various bioinformatics applications, such as compression, or speeding up different other bioinformatics data structures or data analyses. This problem was previously believed to be computationally hard. It was not previously known if this problem could be solved optimally and efficiently, which the paper of Schmidt and Alanko now shows.
