G²OAT seminar: Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests

When

11. 3. 2024
13:00 – 14:00

Where

Room TH:A-1247

Thákurova 7, Prague 6

Dominika Draesslerová from the Department of Theoretical Computer Science, FIT CTU, will speak at the regular Monday seminar of the G²OAT group. During her talk, she will discuss using MEMs and compressed representations like KATKA kernel for taxonomic classification, balancing compression and accuracy.

Event website

Abstract

For taxonomic classification, we are asked to index the genomes in a phylogenetic tree such that later, given a DNA read; we can quickly choose a small subtree likely to contain the genome from which that read was drawn. Although popular classifiers such as Kraken use k -mers, recent research indicates that using maximal exact matches (MEMs) can lead to better classifications. For example, we can:

  • Build an augmented FM-index over the genomes in the tree concatenated in left-to-right order;
  • For each MEM in a read, find the interval in the suffix array containing the starting positions of that MEM’s occurrences in those genomes;
  • Find the minimum and maximum values stored in that interval;
  • Take the lowest common ancestor (LCA) of the genomes containing the characters at those positions.

This solution is practical, however, only when the total size of the genomes in the tree is fairly small. In this paper, we consider applying the same solution to three lossily compressed representations of the genomes’ concatenation:

  • A KATKA kernel, which discards characters that are not in the first or last occurrence of any k m a x -tuple, for a parameter k m a x ;
  • A minimizer digest;
  • A KATKA kernel of a minimizer digest.

With a test dataset and these three representations of it, simulated reads and various parameter settings, we checked how many reads’ longest MEMs occurred only in the sequences from which those reads were generated (“true positive” reads). For some parameter settings, we achieved significant compression while only slightly decreasing the true-positive rate.

The person responsible for the content of this page: Bc. Veronika Dvořáková