Dynamic construction of trie-based automata for approximate K-mer matching on heterogeneous CPU-GPU systems

Abstract

In recent decades, mapping of a variety of species' genomes has taken place. With the proliferation of advanced and specialized hardware architectures such as GPUs, the process has been greatly accelerated. GPUs may accelerate core algorithms used for k-mer matching and alignment but they only play a part in a bigger system. The research contained in this thesis covers the development of a heterogeneous system that utilizes the CPU and GPU to provide a powerful dynamic system. The core content of this thesis describes a way to locate similar k-mers within a single stream in DNA bases. It achieves this by using the CPU to dynamically construct a trie-based automata structure while the GPU provides the k-mer matching mechanism. It will cover the implementation and optimization of GPU kernels used for k-mer matching, implementation of 2 intermediate automata structures operated on by the CPU, and a way to utilize CUDA Streams to hide latency within the system.