GnnDebugger: GNN based error correction in De Bruijn Graphs Authors: Marijo Šimunović, Lovro Vrček, Mile Šikić, Anton Bankevich Published: 2026 ABSTRACT BackgroundModern sequencing technologies have enabled the reconstruction of complete mammalian genomes from telomere to telomere. However, scaling this achievement to thousands of species and population-level studies remains a challenge. Key bottlenecks include the low quality of the draft assemblies and the high coverage requirements. In particular, reconstructing complete and accurate sequences of both haplotypes in diploid genomes is especially difficult since the sequencing depth is not always sufficient to properly reconstruct diverged regions. We aim to explore the use of machine learning, specifically graph neural networks, for scalable error correction in De Bruijn Graphs, addressing the limitations of existing heuristic methods in genome assembly.ResultsInspired by the success of neural networks in extracting patterns from the data on a massive scale, we introduce a method for correcting errors in De Bruijn Graphs using Graph Neural Networks. Our model provides a reliable classification of edges into correct and erroneous, especially for diploid genomes with coverage depth 35 and lower. We demonstrate that these predictions can guide the downstream read error correction algorithm and genome assembly, ultimately allowing for more accurate genome assembly.ConclusionsMachine learning methods have the potential to replace heuristic methods commonly used in genome assembly. Learning-based approaches can enhance the performance of existing assemblers in challenging scenarios and facilitate adaptation to newly sequenced species. Background The goal of genome assembly algorithms is to generate high-quality genome sequences from error-prone read sets. The two fundamental approaches used for genome assembly are the Overlap-Layout-Consensus (OLC) and the De Bruijn Graph (DBG) based assembly. Initially designed for different types of data—OLC for Sanger sequencing and DBG for Illumina sequencing—these methods were successfully adapted to PacBio high-fidelity (HiFi) reads in modern assemblers [4, 9, 17, 28, 35, 48]. Both OLC and DBG approaches construct a graph representation of the sequencing data—assembly graph. Genome chromosomes correspond to paths in assembly graphs. We refer to the collection of these paths as genome path. Errors in reads impact genome assembly differently for OLC and DBG approaches. In overlap graphs, vertices represent reads and edges represent overlaps between read sequences. Errors in reads necessitate consideration of imperfect overlaps, increasing the amount of spurious links between reads originating from distant parts of the genome. Error correction is typically addressed in a preliminary stage, before the assembly graph is built [9, 28]. In DBGs, vertices represent k-mers derived from reads, edges correspond to (k + 1)-mers derived from reads, and every edge connects its prefix to its suffix. Naturally, the sequence of k-mers in the genome represents a path in de Bruijn graph. Finding this path becomes the goal of genome assembly. Key advantage of the DBG over the OLC approach, (k + 1)-mer overlaps (edges) being implicitly known from the read set and the computationally costly overlap phase not being required, made DBG-based assemblers [3, 8, 43, 57] preferred option for sequencing projects in the age of NGS reads. However, because of the way how they are constructed, DBGs can have a complicated structure and significantly more nodes and edges than OLC graphs. To reduce memory requirements, different strategies, like hashing [10] or Bloom-filters [4] are utilized. The unbranching paths in de Bruijn Graphs are traditionally collapsed into single edges, with lengths defined by the number of (k + 1)-mers in the initial path. Sequencing errors generate incorrect (k + 1)-mers, adding erroneous vertices and edges. The collapsing process typically compresses erroneous (k + 1)-mers originating from the same read error into a single edge. Depending on where the errors in reads occur, they may result in different error motifs. Tips are formed when errors appear near start or end of a read and look like dead-end divergences from the main path. Bubbles are paths that diverge and converge, caused by errors in the middle of the read (or by a polymorphism in the target). The graph structure is further complicated by the repeats that cause frayed-rope patterns (convergence followed by divergence in path). Additionally, tandem repeats can induce appearance of cycles in graphs. Long reads come with new opportunities and challenges for genomic assembly [20]. Usage of longer reads can improve assembly of longer repetitive genomic regions, centromeric and telomeric regions and improve haplotype phasing. However, high complexity of these regions, systematic elevated error rate of HiFi reads in low complexity regions, as well as highly variable read length pose a specific challenge for DBGs. Recently, [4, 17, 34] showed that DBGs can be utilized even in the context of long reads. Frequently, errors are first corrected, and only then are the reads used to construct the assembly graph. This can be done in combination with short reads (hybrid) or using only long reads (non-hybrid) [58]. Many successful genome assembly tools [3, 4, 17, 57] build an assembly graph from uncorrected reads and rely upon graph-based correction, which classifies edges as either correct (part of the genome path) or erroneous (arising from sequencing errors). Regardless of the approach, most error correction relies on ad-hoc heuristics. A common strategy involves experts analyzing assembly graphs to identify typical data patterns and translating them into the particular genome assembly subroutine, such as detection and removal of tips and bulges [25]. This process is labor-intensive and hard to scale to a wide variety of different species or a wider range of coverage in sequencing experiments. The most straightforward way to classify edges into correct and erroneous is to measure the read support of a given edge. Edges with average coverage by reads below a given threshold are declared erroneous. Unfortunately, this approach produces both false positive and false negative results. First, systematic errors in low-complexity regions—known artifacts of HiFi reads [54]—can lead to high support for erroneous edges. Second, low coverage and high error rates in such regions often result in insufficient support for correct edges (see Supplementary Data 1). An additional challenge is presented by diploid genome sequencing with low coverage. Genome coverage is divided into two haplomes. As a result, many regions are statistically expected to lack sufficient data for reliable reconstruction. However, by combining data from both haplomes, in most cases, it is still possible to reconstruct the genome sequence. Unfortunately, this approach often fails for regions with high divergence between haplomes. A recent study [59] has shown that assemblies of highly divergent immunoglobulin loci are often incomplete (containing only one haplome sequence) or even incorrect. We argue that overlooking this issue would hinder many future genome assembly applications, particularly in population genomics. Reconstructing only a single haplome of a genome would favor haplotypes with simpler structure, potentially obscuring complex structural variations in the genome. Machine learning-based approaches have been successful in uncovering hidden patterns in the data and are capable of performing various tasks at the near-human level [18, 49]. Recently, Graph Neural Networks (GNNs) [40] have been gaining popularity in domains with unstructured data. The application of GNNs is not always straightforward. They are known to suffer from over-smoothing, when predicted values depend solely on the local neighborhood of a node or edge, or over-squashing, when information needs to propagate along longer ranges [1]. Despite the drawbacks, these models have been successfully applied in various domains [11, 19, 23, 56]. Given the abundance of high-quality annotated data, ML can solve hard problems in the domain of biology [16]. The recent completion of high-quality assembly references [22, 29, 52] provides an opportunity to utilize ML methods in genome assembly. GnnDebugger is a GNN-based approach for detection of structural inconsistencies—“bugs”—in assembly graphs. GnnDebugger is designed to detect true edges in the DBG assembler, rather than serving as a standard read-level error correction tool. It leverages generic edge-level features (length and coverage) alongside graph topology to infer the edge multiplicity, defined as the number of times genome path traverses the edge in the DBG. These predictions can be utilized to improve the detection and correction of errors in reads, a crucial condition for the success of assemblers that use PacBio HiFi long reads. We provide a method to create training data automatically, without the need for human labelers, and a model for predicting edge multiplicities. The GNN-based approach improves the performance of error detection in low-coverage setting where the heuristics struggle. We demonstrate the effectiveness of this method by integrating the outputs of the ML model into an existing DBG assembler, replacing the heuristic algorithm’s output, and consequently improving assembly results. Related work Machine learning methods have been utilized in bioinformatics to solve various problems, such as nanopore sequence basecalling [31], methylation detection [46], protein structure prediction [16], protein-protein reactions [42] or drug responses [41]. However, the adoption in the area of genome assembly has so far been very limited. For example, in [47], Conditional Random Fields have been used to predict arc multiplicities in DBGs using short reads. Another example is filtering out errouneous NGS reads using classical machine learning algorithms [38]. Recently, reinforcement learning has been used in ralphi framework [5] for haplotype reconstruction from ONT long reads. Similarly, in [55], graph coloring via neural network is used for haplotype phasing. Most of these methods are developed in isolation, without considering integration in full genome assembly pipelines. Adjacently, the DBG has been used as a base data representation for modeling the interactions in non-coding RNA [53]. In addition to the sequence information, additional structural information is added, enabling simultaneous prediction of RNA interactions, disease associations and subcellular localization, using GNNs. Another hindrance to using ML in genome assembly is the lack of standardized practices. Each genome assembler has its particular way of building the graph and resolving errors that are rarely compatible with other assemblers. This lack of interoperability makes it harder to adopt the improvements from one assembler to the others and to define a standardized feature set on which ML techniques could be applied. In the domain of OLC-based assembly, the GNNome Framework [51] recently demonstrated the potential of GNNs to unravel overlap graphs and correctly identify genome paths. Data samples for training were generated using the existing assemblers. Large assembly graphs were partitioned into smaller graphs with varying cluster sizes, and boundary nodes were masked during the training. A bidirectional GNN with residual connections based on residual convolutional architecture [6] was used to predict most probable correct path through the graph. To the best of our knowledge, graph neural networks have not yet been used in DBG-based genome assemblers. The purpose of this study is to investigate the application of GNNs for scalable and data-driven error correction in DBGs, providing a systematic alternative to heuristic methods. Leveraging the inherent structure of the assembly graphs and edge-level features, our goal is to improve the accuracy and robustness of genome assembly, specifically in challenging graph regions, demonstrating the potential of machine learning to advance the field. Methods Problem description We use the graph neural network model to predict the multiplicities of edges in the assembly graph. Although downstream analysis uses only binary classification: multiplicity is 0 (erroneous edge) or multiplicity is at least 1 (correct edge), we have observed that solving a more complex problem of multiplicity estimation results in a more accurate classification. This approach outperforms the alternative based on simple binary training criterion [45]. The binary classification can be used as a guide for graph-based error correction algorithms. However, classification errors may result in fragmented assembly or even assembly errors. Figure 1 illustrates how errors in edge classification can result in a fragmented assembly even when one of the haplomes is reconstructed. Given enough samples with low coverage, we can use neural networks to learn the error patterns in such error hotspots, avoiding the need to explicitly parameterize the decision algorithm. Consequently, improved edge classification reduces the number of errors and results in improved assembly. See Supplementary Data 2 for more detailed examples from the test set.Fig. 1Comparison of GnnDebugger with coverage-based LJA criterion. a Diploid reference has been sampled with the occasional errors in sequencing reads and DBG is created. The arrow in the graph marks the edge where the sequencing errors cause increase of coverage in erroneous edge. The coverage of correct edge is decreased. b Heuristic method will mark all edges with coverage of 1 as false (left). The GNN predicts multiplicities based on the coverage feature, the predictions above threshold t=0.5 are marked reliable (full line) and erroneous (dashed line) otherwise (right). c The reads are aligned against the cleaned graph. The error in reads (marked with red cross) caused the increase of coverage in graph which was erroneously predicted as correct by heuristic (left). d The graph is resolved. The error in edge prediction caused the collapse of the diplodity (left). The diploidity is preserved with correct prediction made by GnnDebugger. e Final assembly result is improved via improved error detection Comparison of GnnDebugger with coverage-based LJA criterion. a Diploid reference has been sampled with the occasional errors in sequencing reads and DBG is created. The arrow in the graph marks the edge where the sequencing errors cause increase of coverage in erroneous edge. The coverage of correct edge is decreased. b Heuristic method will mark all edges with coverage of 1 as false (left). The GNN predicts multiplicities based on the coverage feature, the predictions above threshold t=0.5 are marked reliable (full line) and erroneous (dashed line) otherwise (right). c The reads are aligned against the cleaned graph. The error in reads (marked with red cross) caused the increase of coverage in graph which was erroneously predicted as correct by heuristic (left). d The graph is resolved. The error in edge prediction caused the collapse of the diplodity (left). The diploidity is preserved with correct prediction made by GnnDebugger. e Final assembly result is improved via improved error detection Datasets We use a highly accurate HG002 assembly to create datasets without resorting to laborious and expensive manual labeling. Each data sample is an assembly graph of a given unique set of input reads. We trained our model using two types of input reads: one, generated by simulating reads from a reference genome and the other, obtained by down-sampling a real read set. To simulate reads, we utilize the PbSim3 simulator [30]. First, we create simulation profiles from the sequencing reads of CHM13 reference [29]. We simulate training and validation samples from different simulation profiles. In addition to simulated reads, we also utilize the HiFi reads which were used to create the HG002 assembly. Real reads are first mapped to respective chromosomes from references. We downsample the reads with different random seeds to generate graphs with varying coverage rates (see Table SI 5). For our experiments, we always create a graph from a single diploid reference chromosome. For each assembly graph, we export edge index, edge features and multiplicity information. The edge features consist of edge coverage and edge length vectors. Coverage of an edge is the measure of its support by input reads. Formally, in de Bruijn Graphs the coverage of a (k+1)-mer is defined as the number of times it is present in input reads. Edge coverage is defined as the average coverage of all (k+1)-mers in it. Here, we describe our approach for labeling of the graph samples. Let count(x, s) be a function that returns the number of occurrences of a string x in a string s, with |x| ≪ |s| and where || denotes string length operator. Let G represent the assembly graph, R the reference genome as set of chromosomes c, where each chromosome c is represented with a unique chromosome nucleotide string \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta _c$$\end{document}, and C the homopolymer-compression function. For an edge e ∈ G, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s_e$$\end{document} denote the nucleotide string of an edge e, and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Theta _R = \{ \theta _c \mid c \in R \}$$\end{document} denote set of unique chromosome sequences of reference R. The homopolymer-compressed (HPC) sequence of a sequence s is C(s). Then the label L(e) for edge e:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} L(e) = \sum _{\theta \in \Theta _R} \text {count}(C(s_e), C(\theta )) \end{aligned}$$\end{document}is the total count of occurrences of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(s_e)$$\end{document} in a set of HPC chromosomes strings of R. Therefore, L(e) is the multiplicity of the HPC edge in the HPC genome reference. The multiplicity is equal to zero if the edge does not appear in the reference, or a positive integer number if it appears one or more times in the reference. The main advantage of this labeling procedure is that it can be completely automated. One disadvantage is that occasionally, the edge can be labeled as false positive or false negative due to errors in the reference genome. Even highly curated benchmark datasets are known to have mislabeled data [26]. While errors in the test set can destabilize error benchmarks, our goal is not just to improve multiplicity prediction, but also the final assembly. Hence, we conducted additional evaluations with standard quality measures used in genomic assembly to evaluate the effectiveness of our method. Once the graph is assembled, we export the graph data in a format suitable for training and testing within the PyTorch framework [2, 12]. All datasets used in the article are available at [44]. Data transformations The following transformations are applied to the data submitted to the model. For nodes, we add in-degree and out-degree counts. For edges, we normalize the length feature using Z-Score normalization. During the graph-based error correction, assemblers call the error correction routines iteratively. As the assembly graph goes through multiple corrections, the edge lengths change. Normalizing the length makes the model less sensitive to these variations. We also add two additional features, both boolean in nature: one indicating single- or multi-edge attribute and the other, marking the tips of the graph. We added the boundary edge feature due to significant coverage variability in those regions, where read support is typically lower. In addition to the node and edge features, we incorporate a global graph coverage estimation feature for the given input graph. GNN only processes small neighborhood of each respective edge and cannot derive this information from local features. The typical coverage distribution in the read sets we analyzed and used in our research is bimodal. Most of the coverage values cluster around the first, higher peak, which corresponds to the coverage per haplome. The second peak is caused by homozygote regions of the two strands of the chromosome. We calculate a histogram of coverage values with 100 bins. Then, we detect the first peak, ignoring the bins with a coverage below 5 per haplome and use the 10 points surrounding the peak as a feature. Coverage less than 8 per haplome was not used in our generated datasets or in evaluation experiments. It is worth noting that there might be species where the coverage distribution will not follow this pattern, and other strategies should also be considered. We leave this for future investigations. Model We use the model from [51] as an architectural basis and adapt input and output stages to the particularities of the DBG-based genome assembly approach. The model comprises an embedding stage, which converts input node and edge features into high-dimensional embedding vectors. Residual gated graph neural network A core part of the model is a GNN using a message passing mechanism [13]. Unlike most existing GNN architectures [37], this model has been adapted to work bidirectionally, so that predictions are made based on both upstream and downstream edge neighborhoods. This is important for the following reasons. The multiplicity of edges is maintained through the graph [33] except in the case of sequencing errors and therefore needs to be in concordance with multiplicity of both incoming and outgoing edges. The assembly graph is constructed as a directed graph. If we did not use bidirectional architecture, the edge would only receive the information from the incoming and not from the outgoing edges. We used four-layered network in our implementation. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {A}}_{1}$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {A}}_{2}$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {A}}_{3}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {B}}_{1}$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {B}}_{2}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {B}}_{3}$$\end{document} are learnable linear transformations. The node and edge embeddings h and e are passed into the graph neural network. Each GNN layer returns an updated embedding tuple (h, e), which is either passed into the next layer or regressor:1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbf{e} = \mathbf{e}_{j \rightarrow i} + \mathbf{e}_{i \rightarrow j} + \mathbf{e} \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf{e}_{y \rightarrow x}$$\end{document} is directional update of an edge internal state:2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbf{e}_{y \rightarrow x} = \text {ReLU}(\text {LayerNorm}( \mathbf{B}_1 \cdot \mathbf{e}_{y \rightarrow x} + \mathbf{B}_2 \cdot \mathbf{h}_y + \mathbf{B}_3 \cdot \mathbf{h}_x)) \end{aligned}$$\end{document} Similarly, node internal states are updated as:3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbf{h} = \text {ReLU}(\text {LayerNorm}((\mathbf {A_1 \cdot h} + {\mathbf {h}}_{fw} + {\mathbf {h}}_{bw})) + \mathbf{h} \end{aligned}$$\end{document}For a single node i, with internal state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf{h}_i$$\end{document} forward and backward updates \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {h}}_{ifw}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbf {h}}_{ibw}$$\end{document} are given by:4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbf{h}_{ifw} = \sum _{j \in \mathcal {N}_{out}(i)} \mathbf {A_2 \cdot h}_{i} \odot \sigma _{i \rightarrow j} \end{aligned}$$\end{document}and5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbf{h}_{ibw} = \sum _{k \in \mathcal {N}_{in}(i)} \mathbf {A_3 \cdot h}_{i} \odot \sigma _{k \rightarrow i} \end{aligned}$$\end{document}where ⊙ is the Hadamard product. The gate σ is calculated as the value of a sigmoid function of the edge feature of the incoming (or outgoing) edge divided by the values of the sigmoid functions of the edge feature for all incoming (or outgoing) edges. Finally, a regressor stage predicts the edge multiplicity value. The regressor incorporates a Multi-Layer Perceptron block that takes the graph coverage estimation feature, converting it to a high-dimensional embedding. The graph feature aids the network in calibrating the multiplicity predictions to the variations in input read set coverage:6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \mathbf{g} = \text {RepeatInterleave}(\mathbf{W}_{g2} \cdot \text {ReLU}(\mathbf{W}_{g1} \cdot \mathbf{x}_{graph}), edge\_index) \end{aligned}$$\end{document}Edge, node and graph features are concatenated into a single feature from which the final predicted value is calculated. The network has in total 260546 parameters. Encoder and regressor implementation details and the image of the model pipeline containing full data flow are available in Supplementary Data 3. Objective The main output of the graph-based error correction procedure is a boolean decision on whether the edge is reliable. Therefore, an equivalent approach would be to utilize an objective for binary classification, as in [51]. Initially, we reduced the ground truth multiplicity targets to binary choice by applying the boolean operator to the multiplicity value of the respective edges. However, collapsing multiplicity values results in a loss of valuable information that neural network can learn. Furthermore, multiplicity value predictions offer opportunities to improve the error correction and resolution of repeats in the graph [32]. Therefore, we decided to model our problem as a regression task. Our loss function combines Huber loss [15] and an additional regularization term, which we call Flow factor. The loss function is defined as:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} L(\hat{m}, m)&= \alpha \cdot L_{\text {Huber}}(\hat{m}, m) + \beta \cdot F(\hat{m}) \end{aligned}$$\end{document}where m and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{m}$$\end{document} are ground truth and predicted multiplicity value, respectively. α and β are hyperparameters. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{Huber}$$\end{document} is Huber loss of the predicted edge multiplicity with parameter δ =3.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} L_{Huber}(\hat{m}, m) = {\left\{ \begin{array}{ll} \frac{1}{2} (\hat{m} - m)^2 & \text {if } |\hat{m} - m| \le \delta \\ \delta \cdot (|\hat{m} - m| - \frac{1}{2} \delta ) & \text {otherwise} \end{array}\right. } \end{aligned}$$\end{document}We use Huber loss in favor of MSE loss because the former is more sensitive to the miss-predictions of small multiplicities (up to the δ ), which is really important as we set the decision boundary of whether the edge is correct or incorrect between 0 and 1. Using a linear loss term outside of the δ range reduces the sensitivity to outliers caused by repeats in the reference. Quadratic loss values would have a huge impact on the loss value without much benefit to the process of detecting erroneous edges. The idea of using flow is not new in DBG applications [32]. It is also used in [47] to train CRFs for multiplicity prediction. Additionally, it has been used for algorithmic reasoning based on GNNs [27]. Unlike the previous works, we use it with a little twist. It is not a loss term in a classical sense as we are not comparing the predicted values to a ground truth. It is a regularization term that favors preserving the flow in the graph. The flow loss of a single node v is defined as:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} F(v)&= \left| M_{\text {in}}(v) - M_{\text {out}}(v) \right| \end{aligned}$$\end{document}where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M_{in}(v)$$\end{document} is a sum of multiplicities incoming from the neighboring nodes of node v and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M_{out}(v)$$\end{document} is a sum of the multiplicities outgoing to the neighboring nodes of node v in directed graph G.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} M_{\text {in}}(v)&= \sum _{u \in \mathcal {N}_{\text {in}}(v)} m(u, v) \\ M_{\text {out}}(v)&= \sum _{w \in \mathcal {N}_{\text {out}}(v)} m(v, w) \end{aligned}$$\end{document}The total flow is then reduced by dividing it by the number of nodes N in the graph. The flow factor is important due to the way on how we create ground truth values for multiplicity. A small percentage of the edges, depending on the species, will have erroneous ground truth values. For example, homopolymer compression is going to make query of form “ACCCCTGTAT” hit the reference position with nucleotides “TACTGTATA”. Therefore, the misprediction will result in a lower penalty if the flow of the multiplicities in the local neighborhood of the node is preserved and presents a relaxation to the absolute prediction objective of the Huber loss. We recommend α =0.3 and β =0.7 as default settings based on the error analysis of the assemblies (see Tables SI 1 and SI 2). Results Evaluation setup LJA genome assembly algorithm The described methods could be applied to any DBG-based assembly algorithm. For the purposes of this research, the La Jolla Assembler (LJA) [4] was chosen based on the following considerations. First, LJA is currently the only genome assembly tool for HiFi reads that uses classic DBG instead of its sparse version. In this way, we avoid additional result variation caused by the choice of “anchor” k-mers [35]. Second, LJA does not use preliminary read correction, entirely relying on graph error correction, which removes the necessity of adjusting for possible bias and artifacts of preliminary error correction. Finally, the modular design of LJA allows the simple incorporation of alternative edge classification methods into its pipeline. MowerDBG module that is responsible for error correction in LJA uses algorithm 1 to correct errors in both the de Bruijn graph and reads. First, mowerDBG classifies edges into correct and erroneous based on their coverage and additional ad-hoc heuristics. Then, it attempts to reroute the paths of reads in the graph that go through erroneous edges. If all paths visiting erroneous edge are successfully rerouted, the edge is removed from the graph. Therefore, identifying reliable edges is the cornerstone of the mowerDBG algorithm. Algorithm 1mowerDBG Iteration(Graph, Reads) mowerDBG Iteration(Graph, Reads) The algorithm 1 is applied several times during the error correction process, each with a different modification of step 5. In case there are multiple possible ways to correct a read, additional information (paths of other reads, edit distance, known patterns of errors in HiFi reads) may be used to make the choice. The parameters of this choice are changed from iteration to iteration to make the most reliable corrections first and to resolve more complex cases only after the majority of errors in the graph and in reads are already fixed. In total, this procedure is called 6 times during the assembly pipeline with 2 different values of k (501 and 5001). To test the impact of the proposed edge classification on genome assembly results, we preserve the pipeline and parameters of the LJA error correction procedure but replace step 1 of each iteration with the criterion we developed using the GNN approach. We evaluated assemblies based on assembly contiguity (NG50), number of contigs (LG50), rate of duplications in the assembly (Duplication ratio), structural errors (misassemblies), and mismatch/indel rate (mismatches and indels per 100Kbp). For precise descriptions of these metrics refer to [14]. Evaluation metrics were calculated using Quast-LG tool [24]. Unfortunately, no existing tool (including Quast-LG) can reliably detect structural errors in diploid genomes. Similarity between haplomes is confusing for assembly evaluation. We still report structural errors to emphasize the importance of assembly accuracy, but these values should be considered unreliable. Training We trained models in our experiments for 300 epochs. The training data consists of 804 graphs in the training data (around 197 million edges), created from the chromosomes 4, 7, 8, 10, 11, 12, 17 and 20, respectively, and 334 graphs in the validation set, created from chromosomes 5, 16 and 19 (around 77 million edges), respectively (see SI 4, SI 5 for more details). Graphs were generated from read sets with coverage values from 8 to 17 per haplome. We used both uncorrected and semi-corrected reads (after 2 and 4 error corrections by mowerDBG). The network was trained using WAdam [21] optimizer with learning rate lr=0.0005 in combination with ReduceLROnPlateu scheduler from the Pytorch library, which decreases the learning rate with factor=0.95 if the validation error does not decrease for patience=10 epochs. The GNN has 4 layers, with receptive field of 8 due to bidirectionality. Unless noted otherwise, internal hidden feature dimensions are set to 92. The same objective used in training was employed to measure validation set error for model selection. Evaluation stages We first compared the performance of the GnnDebugger with the heuristic method implemented in LJA (see step 1 in Algorithm 1. For the evaluation of binary metrics (accuracy, precision, recall) we generated test datasets (see SI 5 for more details) from reads mapped to HG002 chromosomes 3, 9, 18 and 21. We also tested our approach with two different k-mer settings: k=501, and k=5001. These values correspond to default parameters used in the LJA pipeline. The coverage of testing datasets ranges from 10 to 15 per haplome (20 to 30 for two haplomes). In addition, we generated a test set with coverage 21 per haplome for which the model was not trained. For each coverage, there were 14 graph samples tested. For the full assembly evaluation, we replace the heuristic method with GnnDebugger. The LJA constructs the assembly graph, exports it in the expected format [2, 12] and calls the inference procedure. The predicted multiplicities are read back into the LJA and assigned to the respective edges. For compatibility with the heuristic, we convert the multiplicity value to a boolean value based on the configurable threshold between 0 and 1 (see Supplementary Data 5 for recommended threshold settings). Based on these predictions, LJA partitions the paths in the graph and tries to reroute them to correct the errors in the reads. For complete genome assembly, we used 3 diploid read sets from T2T-Primates project: P. Troglodytes, P. Abelii and P. Pygmaeus. The reads were downsampled to coverages 12, 15 and 21 per haplome, effectively creating nine different evaluation samples. Finally, we conduct a series of model ablations to better understand the effect of various architectural decisions and data transformations. Comparison with heuristic The GnnDebugger significantly increases the accuracy and recall metrics while maintaining a similar performance on the precision metric (Fig. 2). The heuristic outputs only binary values, so we performed the following conversion of the multiplicity predictions: Every prediction value higher than the threshold (t=0.90) is converted to true value, i.e. we mark an edge as reliable and false, i.e. unreliable otherwise. The threshold is chosen to have a similar precision metric for k=501, which makes it easier to compare other metrics, and is kept the same for k=5001 datasets. In Fig. 2, we can see that the median precision metric is similar for both the heuristic and the ML method, but the heuristic method has a much higher variance. The reason why heuristic has such high precision is a high cutoff threshold for coverage values. This means that there will be a very small number of false positive decisions, the trade-off being that many correct edges are false negatives. This has two drawbacks. One is that the error correction algorithms are pretty complicated in order to recover as much as possible of the reads information. The other is that the heterozygosity information often gets lost during the correction. We can demonstrate this by postprocessing all edges with average coverage less than 2.5 as false (green boxes in Fig. 2). This results in further increase in precision at the cost of accuracy and recall loss. As the coverage decreases from 15 to 10, there is a significant drop of the accuracy—median accuracy drops 18% for the heuristic method, while the median accuracy of GnnDebugger only slightly (1.3%) decreases. The similar is the case for the recall. We can see that for the value of coverage 21, the metrics for heuristic equals the GNN model. In the case of the graph with kmer size 5001 we notice a similar pattern, with the difference that even for coverage 21 the GnnDebugger performs much better. The reason why the heuristic performs worse here is also connected to the properties of the graph. Longer kmer value means more unique edges with smaller coverage.Fig. 2Accuracy, precision and recall metrics for DBG with k=501 (left) and k=5001 (right). Coverage values are given per haplome. The LJA (heuristic) error detection is threshold based. The GnnDebugger method uses a GNN network to classify the edges. GnnDebugger-PP marks all edges with average coverage below 2.5 as erroneous in a postprocessing step Accuracy, precision and recall metrics for DBG with k=501 (left) and k=5001 (right). Coverage values are given per haplome. The LJA (heuristic) error detection is threshold based. The GnnDebugger method uses a GNN network to classify the edges. GnnDebugger-PP marks all edges with average coverage below 2.5 as erroneous in a postprocessing step Most false positive mispredictions have small coverage values. Therefore, depending on the error rates of the assembler, we can easily further decrease the false positive rate by simply setting the edge reliability predictions in the range from 0 to 1 and small coverage to 0. However, performing such an operation has a detrimental effect, as there is substantial heterozygosity loss. In our experiments for full assembly, removal of false positives at the cost of removing true positives with small coverage had a negative effect on the error rates in assembly. Supplementary Data 9 contains comparison of the heuristics with GnnDebugger and two attention-based GNN models [7, 50] on the test data created from recent I002C [39] assembly. Evaluating results of complete assembly pipeline We compared the results of LJA with the heuristic method (LJA) to the implementation relying on GNN detections (LJA-GnnDebugger). Additionally, we evaluated two other state-of-the-art assemblers, Hifiasm and Verkko, on the same read sets. Note that the Hifiasm does not output a completely compatible diploid assembly with those produced by LJA and Verkko. We used a haplotype-resolved processed unitig graph without small bubbles (*.bp.p_utg.gfa file), most similar to the output of the other two tools.Fig. 3Evaluation of contiguity and accuracy of assemblies for Pan Troglodytes (top), Pongo Pygmaeus (middle) and Pongo Abelii (bottom) for coverages 12, 15 and 21 per haplome, respectively. Mismatches and indels are calculated per 100kbp Evaluation of contiguity and accuracy of assemblies for Pan Troglodytes (top), Pongo Pygmaeus (middle) and Pongo Abelii (bottom) for coverages 12, 15 and 21 per haplome, respectively. Mismatches and indels are calculated per 100kbp Figure 3 shows the metrics from the full assembly of Pan Troglodytes, Pongo Pygmaeus and Pongo Abelii references, respectively. In all experiments, we can see that the NG50 metrics and LG50 metrics are improved using the ML-based method. Hifiasm, and especially Verkko, have a bit higher duplication ratio in comparison to both versions of LJA assemblers. For coverage 15 per haplome, the number of misassemblies is comparable between LJA-GnnDebugger implementation and hifiasm. For lower coverage, the assembly quickly becomes very fragmented and unreliable. Verkko exhibited poor results on most parameters, which can be explained by Verkko focus on the hybrid assembly of PacBio HiFi and Oxford Nanopore reads. More detailed metrics are available in Supplementary Data 7. LJA-GnnDebugger showed a significant advantage over LJA on almost all metrics and datasets. For assemblies with higher read coverage (21 per haplome) the LJA assembler with the ML based error correction improves assembly metrics over other assemblers in most of the evaluated cases. Therefore, the assembly quality significantly benefits from GnnDebugger. With very high coverage ( 50x) the performance is similar to the performance of heuristic (see Fig. SI 7). While we primarily focused on the improvement of assembly results in primates, we run additional evaluations on some non-primate diploid genomes. Note that these genomic references are still not complete and the results of the evaluations should be interpreted with caution. For the details, see Supplementary Data 8. On haploid genomes, we did not see significant benefits in performance over the heuristic. See Supplementary Data 10 for more details. Model ablations Fig. 4Model ablations for graphs built with kmer=501 (left) and kmer=5001 (right). The model without ablations is shown in blue. SingleLayerNet: The model is trained using a single GNN layer so that the network only sees the immediate 1-hop neighborhood (orange). PartialEdgeFeatures: removes edge features for multi-edge detection and tip detection (green). NoCoverageEstimate: removes the graph coverage estimation attribute (brown). HiddenFeature16: uses only 16 hidden features (purple). NoLengthSLcaling: does not use edge length scaling (pink) Model ablations for graphs built with kmer=501 (left) and kmer=5001 (right). The model without ablations is shown in blue. SingleLayerNet: The model is trained using a single GNN layer so that the network only sees the immediate 1-hop neighborhood (orange). PartialEdgeFeatures: removes edge features for multi-edge detection and tip detection (green). NoCoverageEstimate: removes the graph coverage estimation attribute (brown). HiddenFeature16: uses only 16 hidden features (purple). NoLengthSLcaling: does not use edge length scaling (pink) The training was performed using the same dataset and the same optimization parameters as the baseline model, including the random seed. Figure 4 illustrates the performance of the models with various configurations. The removal of multiple layers leads to a general loss of performance. Notably, there was a significant drop in accuracy and recall metrics for the out-of-distribution samples when using a graph with k-mer size 501. Similarly, removing additional edge features (multi-edge and tip) leads to a performance drop except for the recall metric in graphs with k-mer size of 5001. The overall effect of the global graph coverage attribute was challenging to estimate. For the graph with k-mer size 501 there was a slight improvement in accuracy and recall metrics, but precision was lower and exhibited much larger variation. Conversely, we observed a general improvement across all metrics for the graph with k-mer size of 5001. When the hidden feature size was decreased to 16, the model performance was similar to the baseline, suggesting that there is a redundant capacity to increase the size of the training dataset and incorporating additional reference species. Discussion ML based techniques have been able to improve the performance of many algorithms that have been relying on hand-crafted heuristics. There are, however, many hindrances to ML-adoption in genome assembly. An obvious problem is the lack of standardized data representations of genome assembly. Even though assembly graphs are a common denominator of most approaches, each genome assembler implements its own graph construction and error correction methods, making reusability and interoperability hard or even impossible. We tackled the problem of missing datasets for training and established a base architecture and learning objective for error correction in DBG based assemblers. We have shown how the ML-based approach can improve the detection and correction of errors in DBG-based assembly on low-coverage reads where traditional heuristic-based approaches face difficulties. Although our method uses very generic features, namely coverage and length of edges combined with topological information, it is still not guaranteed that other DBG assemblers will be able to provide this information for the ML algorithm. An additional challenge arises from the limitations of genome assembly evaluation methods. The lack of tools to precisely detect structural errors in an assembly by comparing it to a reference raises significant concerns about the quality of mass-produced assembly results. We hope to bring attention to these issues and spur a discussion in the direction of more theoretically grounded approaches in building assembly graphs and statistically based error correction methods, and establishing standardized interfaces and benchmark datasets for testing of each approach. Limitations While the GNN-based method improves upon the existing heuristics method, several limitations need to be addressed in future research. Our training data set was derived exclusively from the genomes of a single species. The lack of diversity limits model generalization. To enhance the robustness and applicability of our method, it is essential to expand the dataset with samples from various species. Furthermore, the training samples were generated from reads of isolated chromosomes, which means that the acrocentric nature of certain chromosomes is not represented in the training data. This could affect the model’s performance on species with such characteristics. Certain parts of the assembly graphs are easier to resolve than others. Identifying subgraphs in assembly graphs that contribute more significantly to the learning process could speed up the training process. As GNNs have not been extensively used in genome assembly, there may be more suitable architectures for this specific problem. Exploring alternative architectures could potentially yield better results and more efficient genome assembly. Lastly, performance optimizations were not within the focus of our research. See Tables SI 12 and SI 13 for more details on current performance and hardware requirements. Conclusion We introduced the GnnDebugger, a GNN-based approach for correcting errors in de Bruijn Graphs constructed from PacBio HiFi reads. Despite significant progress in machine learning, integration into genome assembly pipelines has remained limited due to the absence of standardized datasets and evaluation frameworks. We demonstrated that GNNs can be effectively applied within the context of existing assembly tools, highlighting their potential to improve the accuracy of long-read assembly. We underscore the need for more unified benchmarks to facilitate further adoption of learning-based methods in the domain of genome assembly. Our future research will focus on improving the quality of the training data. Our ablation studies showed that there is further research potential in identifying appropriate data features and model architectures for specific error detection problems. We also would like to try design error correction procedures that shall better utilize multiplicity predictions. Additional file Supplementary Material. Supplementary Material.