Genome Sequence Reconstruction Using Gated Graph Convolutional Network
Authors: Lovro Vrček
Robert Vaser
Thomas Laurent
Mile Sikic
Xavier Bresson
Venue: ICLR 2022 Submitted (2022)
Keywords: genome assembly
graph neural networks
assembly graph
path finding

Abstract: A quest to determine the human DNA sequence from telomere to telomere started three decades ago and was finally finished in 2021. This accomplishment was a result of a tremendous effort of numerous experts with an abundance of data, various tools, and often included manual inspection during genome reconstruction. Therefore, such method could hardly be used as a general approach to assembling genomes, especially when the assembly speed is important. Motivated by this achievement and aspiring to make it more accessible, we investigate a previously untaken path of applying geometric deep learning to the central part of the genome assembly---untangling a large assembly graph from which a genomic sequence needs to be reconstructed. A graph convolutional network is trained on a dataset generated from human genomic data to reconstruct the genome by finding a path through the assembly graph. We show that our model can compute scores from the lengths of the overlaps between the sequences and the graph topology which, when traversed with a greedy search algorithm, outperforms the greedy search over the overlap lengths only. Moreover, our method reconstructs the correct path through the graph in the fraction of time required for the state-of-the-art de novo assemblers. This favourable result paves the way for the development of powerful graph machine learning algorithms that can solve the de novo genome assembly problem much quicker and possibly more accurately than human handcrafted techniques.

Under review as a conference paper at ICLR 2022
GENOME SEQUENCE RECONSTRUCTION USING GATED GRAPH CONVOLUTIONAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
A quest to determine the human DNA sequence from telomere to telomere started three decades ago and was finally finished in 2021. This accomplishment was result of a tremendous effort of numerous experts with an abundance of data, var- ious tools, and often included manual inspection during genome reconstruction. Therefore, such method could hardly be used as a general approach to assem- bling genomes, especially when the assembly speed is important. Motivated by this achievement and aspiring to make it more accessible, we investigate a previ- ously untaken path of applying geometric deep learning the central part of the genome rieembly-untnneee quence needs be reconstructed. A graph convolutional network trained on a dataset generated from human genomic data to reconstruct the genome by finding a path through the assembly graph. We show that our model can compute scores from the lengths of the overlaps between the sequences and the graph topology which, when traversed with greedy search algorithm, outperforms the greedy search over the overlap lengths only. Moreover, our method reconstructs the cor- rect path through the graph in the fraction of time required for the state-of-the-art de novo assemblers. This favourable result paves the way for the development of powerful graph machine learning algorithms that can solve the de novo genome assembly problem much quicker and possibly more accurately than human hand- crafted techniques.
large assembly graph from which genomic se-
INTRODUCTION
Fast and accurate de novo genome assembly is one of the most difficult problems in bioinformatics and it remains unsolved to this day. It focuses on reconstructing the original genomic sequence from sample of shorter overlapping fragments, called reads, without any prior knowledge about the original sequence. The first major achievement of de novo genome assembly happened in the finished, effort that took over a decade and cost billions of dollars (Lander et al. 2001). The reported results of the project were that 99% of the genome had been reconstructed with less than 400 gaps. Unfortunately, that was entirely correct, as only the cuchromatic portion of the genome was considered while the heterochromatin was left include centromeres, telomeres. and tandem gene
early 2000s when the Human Genome Project
out. When the heterochromatin regions-whit arrays-are are also taken into account, the final result is that more than 5% of the entire genome was either missing or incorrect.
Since then, the sequencing technologies have improved significantly in many ways, but most notably in terms of the lengths and accuracies of the reads they produce. At the forefront of the latest sequencing technologies are the HiFi reads developed by PacBio /Wnnger et al. 2019) and the ultra- long reads by Oxford Nanopore Technologies (Jain et al. 2018). both of which were crucial for the most recent breakthrough in the field of de novo genome assembly- full reconstruction of the entire human genome, with no regions left unsolved (Nurk et al., 2021). Nevertheless, this was enabled not only by the latest sequencing technologies, but also by tremendous effort of numerous researchers and bioinformaticians who used various de novo assembly tools and manually inspected large genomic regions.
One of the more common approaches to de novo genome assembly, which was also the one used in the recent reconstruction of the human genome, is the Overlap-LLaoout-Coom Consennessss (OLC) paradigm.

---

Under review as a conference paper at ICLR 2022
An assembly graph of one part of chromosome 11, containing the repetitive region. A zoomed-in in view of the repetitive region can be seen the right. In the graph, orange nodes represent nodes taken for the optimal genome reconstruction, while the blue nodes should be avoided. Figure generated with Graphia (Freeman et al. 2020).
Figure I:
In the Overlap phase, the reads in the sample mapped onto each other in an all-versus-all manner in order to find overlaps between them. All reads that are entirely contained in other reads are removed from further processing. From the rest of the overlapped reads, an assembly graph is built-a directed graph in which nodes represent reads and edges represent the suffix-prefix overlaps between the reads. In the Layout phase, the assembly graph is simplified in order to find a path through it that would reconstruct the original genome. Finally, in the Consensus phase, all the reads are aligned to the reference in order to clean the assembly sequence errors that happened during the rest of the process.
In an ideal scenario, the Layout phase would be formulated as finding a Hamiltonian path over the assembly graph-visit every node in the graph exactly once. However, due to imperfect read qualities, sequencing artifacts, and repetitive genomic regions, finding a Hamiltonian path is usually possible and an unknown number of nodes and edges has to be removed. Because of this, instead of finding a path through the graph directly, modern assemblers rely on heuristics to simplify the entire graph, by iteratively removing nodes and edges deemed unnecessary, such removing transitive edges, trimming tips, and popping bubbles (Li] 2016; Vaser & Šikić 2021). Frequently, however, the assembly graphs are highly complex, and even this is not a straightforward task, as some regions cannot be simplified by the current heuristics. One such region can be seen in Figure T on the right. For lack of a better method, these complex regions are cut out of the graph, and we left with multiple fragments of the original genome instead of the continuous sequence. To this day, the problem of fragmentation continues to plague all the existing assemblers.
The central part of reconstructing the full human genome was untangling these complex regions in the assembly graph instead of cutting them. This approach required an abundance of data, various tools, and a detailed manual inspection of certain regions and individual reads. Reproducing such efforts on new genomes seems infeasible, and thus fast and accurate de novo genome assembly remains elusive.
In this work, we propose novel approach to de novo genome assembly, one based on deep learn- ing and finding path through the graph instead of relying on handcrafted heuristics to simplify the graph. We train non-autoregressive model based on gated graph convolutional network (Gat- edGCN) introduced by Bresson& & Laurent (201)) that takes an assembly graph and outputs a score for each edge. These scores can then be used guide search algorithm over the graph, producing a path that represents the reconstructed genome. Our idea illustrated in Figure where the orange nodes represent the nodes traversed in the optimal path, and blue the ones that should be avoided. For
2

---

Under review as a conference paper at ICLR 2022
this, create synthetic dataset of reads from the real human genomic data, and generate assem- bly graphs prior to any simplification steps in order to avoid any errors such simplifications might produce. We believe, this approach could reduce the fragmentation of the reconstructed genomes as well as the runtime of the assembly process, since some simplification steps can be time-consuming. Thus, make both the codes" and the data") available for other researchers use and join in on tackling the de novo genome assembly using deep learning.
Lately, graph neural networks have been applied to variety of biological problems, ranging from drug design (Stokes et al. 2020) and protein interactions (Gainza et al. 2020), to predicting anti- cancer foods (Gonzalez et al., 202I). However, to the best of our knowledge edge, the only work based on geometric deep learning that addresses de novo genome assembly is Vreek et al. (2020), which more of a proof-of-concept work that simulates the deterministic simplification algorithms in the Layout phase, instead of tackling the tangled regions themselves. Moreover, the data used in Vrček al. 2020) was completely synthetic, not generated from the biological sequences. Here, we go step further by starting with the complete human genome and focusing one of the main problems in genome assembly.
The rest of the paper is composed as follows: In Section we describe the dataset preparation, in Section 3 we formulate the problem mathematically, in Section | we describe the architecture of the used model, in Section 5 we state the performed experiments, and in Section 6 we discuss the results. Finally, Section concludes this paper.
2 DATASET
Generating the dataset can roughly be separated into three tasks. First, simulate the genomic data from the human genome. Second, we adapt an existing tool for de novo genome assembly. Raven Vaser & Sikić, 2021), to build an assembly graph for each set of reads. Finally, we implement an algorithm that leverages the information stored during the read-simulation phase and finds ground truth path through an assembly graph. We use these paths as the supervision signal during the training phase.
2.1 SIMULATING READS
To simulate the reads faithfully, we start with the recently reconstructed human genome, called CHM13 (Nurk et al. 2021), which consists of one chromosome from each of 23 pairs of human chromosomes. In the assembly process, each chromosome would ideally be represented by a single realistic case,
component of the large disconnected graph of the entire human genome, but several chromosomes could be connected into single component. Starting from a simpler scenario, we isolated one chromosome and split it into shorter "mini-references" each 2 million base pairs (bp) long.
During the sequencing process of the real samples, information about the ordering of the reads and their position on the genome is lost. This is the main reason why we are not using sequenced human data, but simulate our own by sampling the reads from the mini-references. Thus, we are able to store the positional information for each read, which allows us to construct the ground-truth path for training.
The reads are simulated by mimicking the sequencing process. The mini-reference is sampled in manner that each base of the mini-reference is covered approximately 20 times, which represents the number of times genomes are sampled from a normal distribution with the mean value of 20,000 and the standard deviation of 1,500. These values real PacBio HiFi reads. In contrast to sequencers, we introduce no errors to the simulated data to facilitate. Considering that the average accuracies of the real PacBio reads usually over 99.5% and that there are tools that perform error correction of reads (Cheng et al. 2021) the assumption of errorless reads
copied and fragmented prior sequencing. The lengths of the reads
determined empirically that the simulated reads would resemble the
too far-fetched.
'Code: https: / aannymmuus.....////// 4open. sci /ttpe///ggg--eenoe-eeeoooooooooe ruct on 4462
Data: currently available under supplementary materials
3

---

Under review as a conference paper at ICLR 2022
2.2 GENERATING GRAPHS
Once the reads are simulated, we can construct the graphs. For this purpose, we use an adapted version of Raven, an assembler that follows the OLC paradigm and can output the assembly graphs different stages of the Layout phase [Vaser & Šikić, 2021). Additionally, keep only the perfect overlaps between the reads. Therefore, unless two reads have a suffix and prefix which are matching in all the bases, they will not be connected with an edge in the assembly graph.
required Raven to
At the end of the Overlap phase, the assembly graph is constructed. We output the generated graph at the start of the Layout phase, prior to any simplification algorithm applied, in order to avoid errors that can occur during the simplification steps. The end result of this entire process 50 graphs, each containing around 3,500 nodes and 50,000 edges. Considering that the reads are perfect and the similarity score of each overlap 1.0, we only rely on overlap lengths as edge features, and use no node features (or rather, we specify feature of each node to be 1). A possible approach would be to encode the genomic sequences with a ID-CNN and use the read-sequence encodings as node features and wverlap-sequence encodings work. Therefore, in order to train on the generated graphs, the last thing needed is the supervision signal a ground-truth path for each graph.
additional edge features, but we leave that for future
2.3 GROUND- PATHS
A ground-truth path is a path in the assembly graph that produces the longest length of the recon- structed genome. For this, we utilize the positional information that was stored for each read during the sampling process and implement an algorithm resembling depth-first search, with an additional preference for successor nodes that are closer to the current node on the mini-reference. The neigh- bors that don't 't share position on the mini-reference with the current node are avoided. Although the reads and the overlaps in the created graphs are both perfect, connections between the distant genomic regions can still exist. The main culprits for this are repetitive regions, regularly found in telomeres, centromeres, and highly duplicated ribosomal RNA genes.
In way. this algorithm can be described as an exhaustive search with oracle. Even though the oracle-the reads' positions on the be optimal, we noticed cases when the length of the reconstruction was less than of the original mini- reference. There are two reasons for this. First, during the Overlap phase, all the reads are trimmed, which slightly reduces them in length. Since the ends of the mini-reference are covered only by the ends of the reads, trimming the reads necessarily leads to loss of information. Second, and the more interesting case, happens due to an error during the Overlap phase resulting in fragmented assembly graph. This occurs even though the sampled reads can cover the entire mini-reference (apart from few bases on either end). We believe this happen due to a combination of repetitive regions and discarding of reads completely contained inside the other reads. However, more analysis is needed to make a definite claim.
that the reconstructed genome will
FORMULATING THE PROBLEM
Let GVV E) be the graph obtained from a set of reads R. A node i V, represents read r; E R. while an edge i + j E F represents a suffix-prefix overlap between reads and ry. For a node i in the graph G. there exists node feature x; E Rd,, while for an edge i + j exists an edge feature Zij E Rd., where d, and de are the dimensionalities of the node and edge features, respectively.
Given such a graph, our objective is to identify the sequence of nodes (i.e., a path), which recon- structs the genome optimally:
arg max RecLen(i,, (o1)...,5))
where RecLen is the length of the reconstructed genome for the given node sequence. Finding such path in exact manner would be NP-hard problem, so need to reformulate objective in a probabilistic way: given graph G(V, E), identify a sequence of nodes which maximizes the conditional probability that the chosen sequence optimal:
4

---

Under review as a conference paper at ICLR 2022
P(i.....,h in is optimal (9) =
(2)
P(i i7 (9) P((2 = 12 9 =1)
P(in = 19.... i- -
(3)
n-1
II P(i++1= = G i1)
II
Pin
(4)
In the last line, introduce two approximations. First, assume that the conditional probability of choosing the correct next node depends only on the current node and not on all the previous choices. Second, the exact conditional probabilities are unknown, and thus approximate them with scores Pij 2 P(i++1 = j 9, 2 = i). Therefore, our task comes down to finding a way to compute the scores Pij so that they would resemble the real conditional probabilities as much as possible. We propose two approaches:
Naive approach. Considering that the current setting we use no node features and use only overlap length as the edge features, naive approach would be to normalize overlap lengths over the neighborhood:
len(i +
Pij Σi-gy len(i j")
(5)
where, for sake of simpler notation, len(é j) denotes the length of the overlap between reads r; and rj. Longer overlap between two reads indicates that they might be closer on the reference and thus the lesser chance of making error in the traversal.
GNN approach. The second approach is based on training graph neural network to compute the scores. We deem that such a model, with enough data and expressive power, might be able to leverage the topology of the graph and thus produce scores of higher quality.
Once these scores are computed, a search algorithm guided by these scores can be run on the graph. In this work, we consider greedy search which will always choose the highest score. This implies that, in case the scores don't faithfully represent the conditional probabilities, the chosen sequence of nodes will certainly be suboptimal. Different choices of search algorithms are also possible, e.g., beam search, but we leave that for future work. Notice that, in a setting where scores are predicted with the naive approach, and the search algorithm greedy, the entire task comes down greedily choosing edges with the longest overlap.
4 MODEL ARCHITECTURE
The proposed model for obtaining the probability scores is non-autoregressive and can be split into three parts-encodee processor, and decoder.
Encoder. A layer that transforms node features x; Rd and edge features zıj E Iede into the d-dimensional node and edge representations. As stated in Section 2 we use x; = 1.0 and zij = len(i j). thus making d, de 1. Encoder for both node and edge features is single linear layer:
h = Wix; + by E Rd
ejj W2zy + bo IR.d
where h. is the initial node representation of the node i, ei, is the initial representation of the edge i + j. and W1 dxdd W2 E dddd. by, by E I are learnable parameters.
The main part of the network consists of multiple GNN layers. For this task, modify the GatedGCN (Bresson & Laurent 2017) to perform on directed graphs by including the informa- tion from both the predecessors and successors of every node. In addition to the original GatedGCN, we include the edge feature representations, and use a dense attention map 7i for the edge gates, as proposed in Bresson & Laurent 2019); Joshi al. 2019).
Processor.
5

---

Under review as a conference paper at ICLR 2022
h
bl
eik
h
f.41
iik
b,++
ji
hj
f141 ej(
Cjk
bI++
hg
Figure 2: Left: updating the edge representations, both forward (blue) and backward (magenta).
Right: Updating the node representation (green).
The motivation for using this layer comes mainly from its performance on the Traveling Salesman Problem (Joshi et al. 2019). Since the problem of finding the optimal walk on the assembly graph is similar to that of TSP, it makes sense to reuse the architecture. In addition, it was shown that the GatedGCN outperforms many other models in several tasks (Dwivedi et al. 2020), which gives us further reason to use this architecture.
Since we are working with the directed graphs, we will distinguish between the messages passed along the edges (forwards), and in the opposite direction of the edges (backwards). Thus, we will also use two sets of edge representations at layer I, forward edge representations efj fd Rd and
backward edge representations Egj E Rdd For the initial values of both of them, we choose the initial edge representation obtained from the encoder, e b.l = Eij = e.g. Accordingly, we also use forward and backward edge gates layer I, v/f.² and Tij respectively.
Let now node be the node whose representation we want to update, and let its representation after layer be h/. Also, let all the predecessors of node be denoted with j and all its successors with k. Then, in the layer I + 1, the node and edge representations will be:
h,+1 = h4 + ReLU BN
A/M
+
Σ
Abb + Σ
b1+1 Mik
o Abth.)
E IRd
(8)
j=H
1-
f1+1
f.1 ji
+ ReLU
BN Bloff
Bhhg + BBht) E Rdd
b1+1 %k 6s + ReLU BN
Ceea + +CM + C.hh) E Rdd
(10)
where all A, B, C E R learnable parameters, ReLU stands for rectified linear unit BN for batch normalization, and @ for Hadamard product. The edge gates are defined as:
(cf))
b.
Cik
off' Σy- +
6.1 Tik
(II)
En a
Cak
+
where o is the sigmoid function, and e is a small value in order to avoid division by zero. This rather complicated updating procedure is illustrated in Figure 2

---

Under review as a conference paper at ICLR 2022
Decoder. A multi-laye perceptron (MLP) decodes the obtained representations into the probabil- ity scores. Probability score Pik, for traversing an edge i - k is computed from node representations of nodes i and k well both forward and backward edge representations of the edge i + k, all after the final GatedGCN layer I::
Pik MLP(1/ h ll efft"
e )
(12)
where (- [I) is the concatenation operator.
5 EXPERIMENTS
5.1 TRAINING
Processing of a graph during one training epoch is done iteratively. In a single iteration, the graph is fed to the model providing with scores for all the edges. We start the traversal from the starting node of the ground-truth path and take w steps, where w is a hyperparameter and we refer to it as the walk length. In each step, best successor is predicted from their probability scores, while the correct next node is obtained from the ground-trutt path. The cross-entropy loss is computed over the current node's successors, followed by teacher forcing where we choose the successor given by the ground-truth as the next node. This is repeated for w; after which the copmuted losses are avereged, the backpropagation is performed, and the next iteration starts, continuing from the last visited node. This is repeated until the end of the ground-truth walk. It is important to notice that, while computing the loss, the number candidates in each step can vary, as the number of successors also varies.
The training was performed on a dataset consisting of 50 graphs with a 30/10/10 rrann/vaiiatiion/esst split. Each graph had about 3,500 nodes and 50,000 edges, all of them generated from 2 Mbp mini- references coming from chromosome 11. We used Adam optimizer (Kingma & Ba 2014), with the inital learning learning rate of 10-4. We also decay the learning rate multiplying by with 0.9 in case there was no improvement in the validation loss for 5 epochs. The evaluation metric used during training keep track of the learning process was the accuracy of predicting the best next neighbor, which we also refer to as the local reconstruction metric. The entire training was done on a single Nvidia A A100 GPU.
Node-level prediction accuracy. Predicting the best successor is the only metric used during the training, since it is easy to calculate the corresponding loss and accuracy. In a way, the better the model follows the ground-truth, the better it should reconstruct the entire sequence. However, there are some situations where choosing the incorrect node makes no difference (e.g.. transitive edges such
k; when there also exist i j and j k), well situations where choosing the correct node is crucial (e.g., dead-end nodes). Therefore, even though used for training, this is not the best metric for genome assembly in general. Still we expect certain transferability between the local and the global task, and this approach simplifies the training significantly. In addition, we also perform teacher forcing during the validation and testing-even though the model makes a mistake, we will put it back on the right path for the sake of easier evaluation of the training process.
5.2 INFERENCE
At inference, the predictions are performed not performed iteratively, but all in one go-we we feed the graph to the model and find the path with greedy algorithm, depending the probability scores. The greedy algorithm runs until it reaches a node without outgoing edges or all of the node's successors have already been visited. Since there is no good option for choosing the starting node, we run the greedy search from all the nodes that have in-degree zero and choose the longest walk. At inference, we cannot evaluate the performance by the accuracy of choosing the best next neighbor, since there is no ground-truth -tuth. Moreover, genome assemblers usually work in a completely different way, so this would make the comparison against them impossible. Therefore, we evaluate our model on two other tasks length of the reconstruction and the execution time.
Reconstructed sequence length. We measure the reconstructed length as the percentage of the original mini-reference length from which the graph was generated. This metric is robust to errors
7

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison of GNN, naive approach, Raven, and exhaustive search.
2 Mbp
5 Mbp
10 Mbp
Method
length [%]]
time [s]
length [%]]
time [s]
length [%6]
time [s]
ES"
99.79 + 0.16
2.5 = 0.1
95.82 + 14.67
7.5 = 1.1
95.93 + 13.94
23.0 5.0
Greedy
93.50 + 17.88
0.2 = 0.0
90.21 + 24.01
0.7 + 0.1
82.11 + 33.14
1.4 + 0.6
Raven
90.85 1 26.74
18.0 1 0.5
93.68 1 17.25
65.0 2.0
95.92 1 13.96
131.0 - 5.0
GNN
99.20 + 1.86
0.5 = 0.1
93.51 + 18.31
1.4 = 0.3
95.73 + 13.90
3.0 = 0.4
while choosing transitive edges, but harshly punishes choosing dead-end nodes and wrong paths in general. Ideally, the length ratio would be 1, but it is expected that it will be slightly less due to the way the reads are simulated and processed prior to the Layout phase (e.g., trimming of reads mentioned in Section 2.3
Execution time. the time needed for the model to process the graph and the search algorithm to find the best path through it. All the experiments related to execution time were performed on a single Intel Xeon E5-2698 v4 CPU.
One the main pitfalls for many assemblers is their execution time. We evaluate
Benchmark. We benchmark model the mentioned tasks against three other approaches. First, the naive approach where the scores are calculated as normalized overlap lengths, as proposed 3 This approach comes down to rumning greedy algorithm over the overlap lengths, and thus refer to as the greedy in the next section. Second approach is the one used for obtaining the ground-truth paths explained in Section 2.33 the exhaustive search with oracle. Finally, also compare the developed model against an existing assembler Raven, which was used to generate the
assembly graphs in Section 2.2
6
RESULTS
The results reported here were obtained by the best-performing model, which had 8 GatedGCN layers, latent dimension 32, and the walk length was 10. The MLP classifier consisted of a single layer. During training this model achieved 99.90% accuracy the test and upon deeper inspection, we noticed that the errors mostly consisted of traversing transitive edges.
Table shows the evaluation results of our model (GNN) benchmarked against greedy approach, Raven, and exhaustive search with oracle (ES*). For the reported lengths, first the percentage of the reconstruction was calculated for each graph, after which all the percentages were averaged. With the aim to test how our model scales to larger graphs, and thus larger genomes, we trained it on graphs generated from Mьр mini-references, and evaluate on graphs generated from 2, 5, and 10 Mbp mini-references. The number of nodes and edges scaled linearly with the length of the mini- reference. For the evaluation on graphs generated from Mbp mini-reference, we reuse the graphs from the test set, coming from chromosome 11. Additionally, we cut chromosome 10 into Mbp mini-references and chromosome into Mbp mini-references. There was no particular reason for choosing the chromosomes 10, 11, and 12.
GNN vs ES The developed GNN-based method doesn't manage to reconstruct the genomes as well as the exhaustive search, but does not fall far behind either. The difference comes from the cases where our model got stuck in dead-end node, similarly to what happened the greedy algorithm.
GNN vs Greedy. We notice that our model consistently outperforms the greedy algorithm in terms of reconstructed length. This means that the model managed to leverage the graph topology in order to avoid some pitfalls where the greedy algorithm got stuck, such as dead-end nodes. The greedy algorithm is slightly faster than model, which comes as surprise. Interestingly, the difference
8

---

Under review as a conference paper at ICLR 2022
in execution times is relatively small, mainly because the neural network used is also relatively small so a single forward pass through can be efficiently done on a single CPU.
GNN vs Raven. We notice that Raven slightly outperforms the GNN model on the two larger datasets, but on the 2 Mbp dataset falls behind even the greedy approach. After more thorough analysis, we noticed that Raven underperformed on only one graph, while on all the other graphs in that dataset it was good the GNN. The graph which Raven failed came from highly repetitive region, and since Raven tries to simplify the graph by removing nodes and edges, it ends up cutting the graph into numerous fragments, the longest one being only around 15% of the original mini-reference. GNN managed to correctly find a path through that graph. This a critical result, as the repetitive regions are the main reason why the assemblers fail accurately reconstruct genomes. At the same time, our method clearly outperforms Raven in terms of speed.
Generalization. We show that the model performs well consistently over graphs of different sizes, both in terms of accuracy and speed. Yet, human chromosomes are up 250 Mbp long, definite conclusion on how it would perform in such a setting cannot be made.
7 CONCLUSION
In this work, we introduce novel approach solving de novo genome assembly based graph neural networks and finding a path through the assembly graph. We created a dataset of assembly graphs based real human genomic data which the developed model was trained and evaluated. The model was also evaluated against a naive greedy approach, an exhaustive search using the positional information reads, and an existing genome assembler Raven (Vaser & Šikić 2021). was shown that it consistently outperforms the greedy approach in terms of reconstructed length and Raven in terms of execution speed. More interestingly, it was shown that the model outperformed Raven when given highly complex graph from a repetitive region.
These results are particularly promising to solve challenging regions more accurately and in far less time than the existing assemblers can. Future work will investigate the proposed technique on sequenced instead of generated data, with the ultimate aim of using it as tool for untangling the assembly graphs to reduce the fragmentation and the execution time. We believe that combining path- funh-finding techniques with deep learning will play major role in improving de novo genome assembly.
REPRODUCIBILITY STATEMENT
All the codes and the data used in this paper are made available, apart from the simulated reads due to their size, but the reads are not necessary for reproducing the results clude the assembly graphs built from those reads. The human reference genome CHM13 which used to generate the mini-references, /ttEss:/giithe com/ ma rimarbbl/oo /CMM
in-
explained in Section 2 is publicly available here: 3, The codes used to simulate the reads from the mini- references are available together with the rest of the code here hatps: http///noonmmous. 4oper. science/r www.nnnnnn----eeeoonooo-----eee reconst ruct 1 oon- 4462 For generating assembly graphs we used an adapted version Raven assembler, which is available here: https:: /aannooooouu.... bebeensscinnce. weaeeennerr/aaeenneeeeee raven-D&F7 In order to make the efforts to reproduce our results as eas- ily as possible, we also make available the dataset we used for training and evaluation, as well as the best performing model- both available as supplementary material (this includes the assembly graphs and additional information). The instructions to help reproduce the results are available with the rest of the code.
REFERENCES
Xavier Bresson and Thomas Laurent. arXhv:1711.07553. 2017.
Residual
gated graph convnets.
arXiv preprint
Xavier Bresson and Thomas Laurent. A two-step graph convolutional decoder for molecule gener- ation. arXiv preprint arXiv: 1rXiv:1906.03412 2019.

---

Under review as a conference paper at ICLR 2022
Haoyu Cheng, Gregory T Concepcion, Xiaowen Feng, Haowen Zhang, and Heng Li. Haplotype- resolved de novo assembly using phased assembly graphs with hifiasm. Nature Methods, 18(2): 170-175, 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.0098: 2020.
Thomas Freeman, Sebastian Horsewell, Anirudh Patir, Josh Harling-Lee, Tim Regan, Barbara B Shih, James Prendergast, David A Hume, and Tim Angus. Graphia: A platform for the graph- based visualisation and analysis of complex data. bioRxiv, 2020.
Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodola, D Boscaini, MM Bronstein, and BE Correia. Deciphering interaction fingerprints from protein molecular surfaces using geo- metric deep learning. Nature Methods, 17(2): 192, 2020.
Guadalupe Gonzalez, Shunwang Gong, Ivan Laponogov, Michael Bronstein, and Kirill Veselkov. Predicting anticancer hyperfoods with graph convolutional networks. Human Genomics, 15(1): 1-12, 2021.
Miten Jain, Sergey Koren, Karen H Miga, Josh Quick, Arthur Rand, Thomas Sasani, John R Tyson, Andrew D Beggs, Alexander T Dilthey, Ian T Fiddes, et al. Nanopore sequencing and assembly of human genome with ultra-long reads. Nature biotechnology, 36(4):338-345, 2018.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 1906000000 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:14/2.6980 2014.
Eric S Lander, Lauren M Linton, Bruce Birren, Chad Nusbaum, Michael C Zody, Jennifer Baldwin, Keri Devon, Ken Dewar, Michael Doyle, William FitzHugh, et al. Initial sequencing and analysis of the human genome. 2001.
Heng Li. Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences. Bioinformatics, 32(14):203-2210, 2016.
Sergey Nurk, Sergey Koren, Arang Rhie, Mikko Rautiainen, Andrey V. Bzikadze, Alla Mikheenko, Mitchell R. Vollger, Nicolas Altemose, Lev Uralsky, Ariel Gershman, Sergey Aganezov, Savan- nah J. Hoyt, Mark Diekhans, Glennis A. Logsdon, Michael Alonge, Stylianos E. Antonarakis, Matthew Borchers, Gerard G. Bouffard, Shelise Y. Brooks, Gina V. Caldas, Haoyu Cheng, Chen- Shan Chin, William Chow, Leonardo G. de Lima, Philip C. Dishuck, Richard Durbin, Tatiana Dvorkina, Ian T. Fiddes, Giulio Formenti, Robert S. Fulton, Arkarachai Fungtammasan, Erik Gar- rison, Patrick G.S. Grady, Tina A. Graves-Lindsay, Ira M. Hall, Nancy F. Hansen, Gabrielle A. Hartley, Marina Haukness, Kerstin Howe, Michael W. Hunkapiller, Chirag Jain, Miten Jain, Erich D. Jarvis, Peter Kerpedjiev, Melanie Kirsche, Mikhail Kolmogorov, Jonas Korlach, Milinn Kremitzki, Heng Li, Valerie V. Maduro, Tobias Marschall, Ann M. McCartney, Jennifer Mc- Daniel, Danny E. Miller, James C. Mullikin, Bugene W. Myers, Nathan D. Olson, Benedict Paten, Paul Peluso, Pavel A. Pevzner, David Porubsky, Tamara Potapova, Evgeny I. Rogaev, Jeffrey A. Rosenfeld, Steven L. Salzberg. Valerie A. Schneider, Fritz J. Sedlazeck, Kishwar Shafin, Colin J. Shew, Alaina Shumate, Yumi Sims, Arian F. A. Smit, Daniela C. Soto, Ivan Sović, Jessica M. Storer, Aaron Streets, Beth A. Sullivan, Françoise Thibaud-Nissen. James Tor- rance, Justin Wagner, Brian P. Walenz, Aaron Wenger, Jonathan M. D. Wood, Chunlin Xiao, Stephanie M. Yan, Alice C. Young, Samantha Zarate, Urvashi Surti, Rajiv C. McCoy, Megan Y. Dennis, Ivan A. Alexandrov, Jennifer L. Gerton, Rachel J. O'Neill, Winston Timp, Justin M. Zook, Michael C. Schatz, Evan E. Eichler, Karen H. Miga, and Adam M. Phillippy. The complete sequence of human genome. bioRxiv, 2021. doi: 10. 10.110012022.000 15w....0.......99 URL https: // //www.birrx.t http://wwww......ooooo//////////
05 4457798
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz. Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Aloom-Ackermand et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-702. 2020.
10

---

Under review as a conference paper at ICLR 2022
Robert Vaser and Mile Šikić. Time-and memory efficceee genome assembly with raven. Nature Computational Science, 1(5):332-336, 2021.
Lovro Vrček, Petar Veličković, and Mile Şikić. A step towards neural genome assembly. arXiv preprint urXiv:2011.05013, 2020.
Aaron M Wenger, Paul Peluso, William Rowell, Pi-Chuan Chang, Richard J Hall, Gregory T Concepeion, Jana Ebler, Arkarachai Fungtammasan, Alexey Kolesnikov, Nathan D Olson, et al. Accurate circular consensus long-read sequencing improves variant detection and assembly of human genome. Nature biotechnology. 15510)1155-1162.2 2019.


Reviews:
[{"review_id": "vwMMpYsVCFg", "reviewer": "Reviewer_GFZQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- uses synthetic data to allow for quantifying accuracy of reconstructed genomes\n- benchmark against a recent previous method, Raven, was performed for both accuracy and execution time\n\nLimitations: \n- The synthetic sequencing reads do not contain any errors. This may  be a reasonable approximation only for HiFi reads. The authors should include simulations with varying levels of noise in order to test the efficacy of the proposed method versus Raven. If this is not done, then the scope of the paper should be about genome assembly for HiFi reads, instead of the more generic language used throughout the text. \n- How does the method do with shorter reads? Perhaps a sweep of this could be informative to set lower bounds. This is important for practitioners who may erroneously use this thinking it is a general assembler.  \n- The range of synthetic genomes are very small, up to 10 Mbp. As the authors stated, a human chromosome is 250 Mbp and there are of course 23 pairs of chromosomes.  Thus, it is unclear how well the GCN can assemble realistic data (not HiFi) for which there is plenty of data. A good use case could be metagenomics, where de novo assembly of contigs is critical. There needs to be some demonstration on real data. A proof of principle using real data would make this paper more compelling.\n- With Raven, there is no training. It assembles the genome with an algorithm. On the other hand, the GNN has parameters that require training. So, the reported execution time for GNN includes just the inference time and not the training, right? Is it fair to compare just the inference time of the GNN on a very powerful A100 vs the whole end-to-end task for the other methods? Perhaps an end-to-end execution time is more appropriate. Also, what is the memory requirement of the GCN? Do people need 48GB of GPU ram? How would the model's execution time be on a GPU that is more common, like a P100 on google colab?\n- Can this method deal with allelic differences across chromosomes? \n- The execution time was based on a single Intel Xeon E5-2698 v4 CPU, which has 20 cores. The Raven paper states that they were run on two AMD EPYCTM 7702 64-core processors. How much would this speed up the execution time, using more cores for Raven. ", "summary_of_the_paper": "This paper introduces a graph convolutional network to assemble a genome from long, perfectly accurate sequencing reads. They show that their model performs better when considering overlap lengths and graph topology versus just the overlap lengths. The proposed method is compared to other methods, such as Raven, and shown to reconstruct the genome much faster. The work was demonstrated on synthetic data without any read errors and thus serves as a prototype for real de novo genome assembly problems, which are much longer and contain noise.", "summary_of_the_review": "This paper provides a promising approach to use GCNs to assemble genomes. To the best of my knowledge, this is novel. The demonstration is focused on synthetic data with no noise. While this can be reasonable approximation with HiFi reads, it remains unclear how it extends to other kinds of data, eg. short- and long-read RNA seq for which there exists many data. To be impactful, a comparison on more realistic synthetic data is important, such as noise added and longer genomes. While there are many good things about this paper to be excited by, critically, a demonstration on real data is needed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "mouXoh3S7v", "reviewer": "Reviewer_c7uL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The benchmarks aren’t sufficient to demonstrate the potential for this approach. The authors do not use standard metrics for this field or compare to widely used genome assemblers like wtdbg2 and mdBG. These manuscripts are also great references for additional metrics to study.\n\nEkim, B., Berger, B. & Chikhi, R. Minimizer-space de Bruijn graphs: Whole-genome assembly of long reads in minutes on a personal computer. Cell Syst 12, 958-968.e6 (2021). \nRuan, J. & Li, H. Fast and accurate long-read assembly with wtdbg2. Nat Methods 17, 155–158 (2020). \n\nThe use of only simulated data is another problem. There is often a very large difference between solving this problem on simulated versus real data. For this reason, the field has needed to hold competitions to properly benchmark methods, such as the Assemblathon.\n\nThe authors’ simulated data also contains no sequencing errors. I completely disagree with the authors that this assumption is not “far-fetched”. The authors must benchmark their method on data containing sequencing errors, which are an inevitable presence in real data. If they believe error correction methods are a useful stage in a full pipeline, they are welcome to include such a method.\n\nOn p. 7, the authors write, “We start the traversal from the starting node of the ground-truth path and take w steps, where w is a hyperparameter and we refer to it as the walk length.\" How do you make use of data from the later portion of the genome if every SGD step begins from the start and goes for 10 graph steps?", "summary_of_the_paper": "The authors propose a graph neural network approach for genome assembly. In the framework of overlap-layout-consensus, a graph structure is formed in which reads are nodes and overlaps between them are edges. In theory, one desires a Hamiltonian path that visits every node and thus forms a reconstruction of the full genome.\n\nThe authors suggest that a gated graph convolutional neural network could compute on this graph to identify the true edges which should be followed in the Hamiltonian path. This is a creative and intriguing direction of research.\n\nThey specify a procedure to simulate data from a known genome and train the algorithm. They benchmark their method on simulated data versus another recently published genome assembler called Raven.", "summary_of_the_review": "Processing assembly graphs with graph neural networks is an intriguing direction, but this work hasn't sufficiently demonstrated its value.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "P-UMYtYSkWM", "reviewer": "Reviewer_xJLL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The paper presents an interesting idea of using Graph-based deep learning to learn the path for genome assembly thus extending the previous neural network-based assembly idea to graphs. \n+ The paper is clearly written. The problem is well defined and the choice of GNN architecture is well motivated.\n+ The result regarding the model handling the repetitive regions more effectively than Raven is particularly important for the use of the proposed method for de novo genome assembly.\n\nWeaknesses: \n- The results in the paper are not comprehensive enough to support and highlight the claims in the introduction. They are restricted to a very small subset of the simulated datasets generated from the human genome (focusing on just 3 chromosomes). \n- The choice of the baselines is not entirely clear. While Raven seems like a reasonable assembly method, the results in the paper (Vaser et al, 2021) do not suggest that it is the best assembly tool, thus requiring at least a mention/discussion of other genome assembly methods in the literature. \n- Furthermore, the baseline Raven paper explores different genomes (plants, prokaryotes, eukaryotes) as well as different sequencing technologies. This paper would benefit from a similarly comprehensive study of the performance of the GNN based method across different datasets\n- The GNN method requires the ground-truth position information that is obtained from an assembled genome and reads generated via simulation. Is the inference of a model trained from simulations then generalizable to another chromosome or another genome with actual reads? The results seem to suggest the former but it is unclear if the inferences were performed on actual reads of other chromosomes. How will such a framework work for de novo assembly? \n- Does the execution time include the training time of the GNN model? If not, then are the execution time comparisons fair? \n- The scalability of the method should be further explored in comparison to other baselines as graphs with the execution time as a function of the size of the mini references scaling to sizes>10 Mbp. \n- It would be useful to explore the potential cause of the differences in alignment performance of the GNN method (and others) across 2Mbp, 5Mbp, and 10Mbp mini-references. \n", "summary_of_the_paper": "This paper presents an interesting idea of using graph-based neural networks (GNNs) to find an optimal layout path during de novo genome assembly using the Overal-Layout-Consensus (OLS) method. Existing methods perform this step by using heuristics to simplify the graph (removing edges/nodes)  instead of finding a path to assemble the genome from the assembly graph. Therefore, they fail to resolve complex graphs with repetitive regions and instead remove or trim those altogether. The paper proposes to train a gated GNN to predict probabilities for the edges of an assembly graph. These probabilities can help in defining a path on the assembly graph that can lead to faster de novo assembly during the Layout phase. To obtain ground truth positional information, the paper uses simulated reads generated from the human genome. The GNN model is trained on mini-references (2 Mbp regions) taken from chromosome 11 and the alignment and execution time results are presented for 2Mbp, 5Mbp, and 10Mbp mini-references from chromosomes 11,10, and 12. The results show that the proposed GNN strategy improves over the greedy approach in alignment performance and an existing assembler (Raven) in execution time. \n", "summary_of_the_review": "The proposed idea in the paper is interesting, however, the limited set of results are insufficient to support its claims and highlight its usefulness for de novo genome assembly. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4FTbZnNTyV", "reviewer": "Reviewer_Av24", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Existing de novo assembly algorithms or software require extreme computational resources in both time and space. Neural network-based de novo assembly can reduce these extreme costs; therefore, this paper has nontrivial contributions on genome assembly area, and I think this work is promising.\n\nOn the other hand, it would be great if the authors address issues as follows:\n\n●\tRelated work\n\nI think this paper is one of the applications or the extensions of existing work [1], [2], [3], [4]. Could the authors briefly introduce those topics or research areas in the revised manuscript?\n\n●\tExperiment (dataset)\n\nIn this work, the authors used the human reference genome (CHM13) to demonstrate that the model has a capacity to reconstruct the reference sequence. However, as reference genomes such as CHM13 and GRCh38 already exist, biological researchers and practitioners do not need to assemble the human genome at usual times. Thus, conducting the experiment to explore the generalizability or transferability on unseen (i.e., non-human) sequences is essential to further demonstrate the utility of the proposed method. In other words, the proposed method should work well on assembly graphs of other species, which do not have reference genomes. \n\n●\tExperiment (evaluation)\n\nTo measure the accuracy of the assembly, the authors compared the lengths of the reconstructed genome. Obviously, this cannot exactly represent the accuracy of the assembly. Thus, I think the authors should supplement other accuracy metrics in the revised version.\n\n[1] Veličković et al., “Neural Execution of Graph Algorithms”, ICLR 2020.\n\n[2] Vrček et al., “A step towards neural genome assembly”, NeurIPS 2020 workshop.\n\n[3] Joshi et al., “Learning TSP Requires Rethinking Generalization”, CP 2021.\n\n[4] Cappart et al., “Combinatorial Optimization and Reasoning with Graph Neural Networks”, IJCAI 2021.\n", "summary_of_the_paper": "This paper addresses the problem of de novo assembly, which is one of the most complicated tasks in bioinformatics. De novo assembly is a task to reconstruct the whole genomic sequence given numerous broken pieces of the original sequence. Existing de novo assembly approaches, based on conventional graph algorithms (e.g., de bruijn graph and string graph) require extreme computational cost, restricting further applications.\n\nIn this paper, the authors proposed a novel method that reconstructs the original sequence from the assembly graph by using a graph neural network (GNN). When the assembly graph is fed to the GNN, the model outputs the paths to reconstruct the original sequence. The authors demonstrated the effectiveness of the proposed method by comparing reconstruction time and accuracy (i.e., length of the reconstructed genome) with one of the de novo assembly software (Raven) on human genome reference data.\n", "summary_of_the_review": "This paper proposed a novel neural network-based de novo assembly method. Since the proposed method can reduce extreme computational costs during the genome reconstruction process, it could be a promising direction for de novo assembly algorithms.\n\nHowever, the utility of the proposed method is not sufficiently demonstrated from the perspective of biology researchers and practitioners. Also, the technical novelty of the proposed method seems to be limited in terms of machine learning techniques. \n\nTherefore, I am leaning towards rejecting this paper at this moment.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper demonstrates that one phase of de novo assembly, specifically the layout phase, can be replaced with graph-neural-network based methods. The paper clarifies in the rebuttal that it focuses on building a method for assembling high-quality long reads. 

All four reviewers rated the paper as below the acceptance threshold. The reviewers largely agree that the idea of using GNNs to assemble a genome from reads is novel, interesting, and has the potential to be very useful. 
The reviewers raise the following concerns: The paper only considers synthetic data, and the synthetic reads used in the simulations are error-free. In practice, reads are not error-free, and thus simulations on real data or at the very least on reads with errors are needed. The authors acknowledge that, and state that they'll provide such experiments in future work. In summary, the reviewers found the experiments to be insufficient to support the claims, even though it is understood by the reviewers and me that the paper only presents a proof-of-concept idea. I agree with the reviewers that simulations on erroneous reads, ideally real data, would be needed for acceptance.

I recommend to reject the paper, since the paper provides insufficient experiments to understand the merits of the proposed approach.
Decision: Reject