Graph Neural Network Meets de Bruijn Genome Assembly

The genome assembly problem, which involves reconstructing the sequence of nucleotides in a DNA molecule from its short, error-prone substrings called reads, is one of the most extensively studied computational problems in biology. The majority of existing solutions for this problem rely on representing input reads in the form of an assembly graph, where each vertex and edge represents a sequence of nucleotides, and the genome corresponds to a path in this graph. However, assembly graphs often contain millions of erroneous edges due to read errors, which significantly complicates the graph analysis. Traditionally, these erroneous edges are detected and removed using a variety of heuristics. However, these heuristics often require manual parameter tuning. In this paper, we propose a novel approach to detect erroneous edges in a specific type of assembly graph called the de Bruijn graph. We employ a graph neural network-based architecture to detect these erroneous edges, replacing the corresponding heuristic step in traditional genome assembly algorithms. To overcome the lack of datasets with known ground truth, we simulate realistic read sets using error profiles learned from real reads. We propose a new method for erroneous edge classification in de Bruijn graph that relies on Graph Neural Networks. In our experiments, we demonstrate that the new method can reliably replace a more complicated heuristic approach and reduce the overall execution time.

In 2023 International Symposium on Image and Signal Processing and Analysis (ISPA)