Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction
Authors: Hansheng Xue
Vaibhav Rajan
Yu Lin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Computational Biology
Genomics
Haplotypes Assembly

Abstract: Understanding genetic variation, e.g., through mutations, in organisms is crucial to unravel their effects on the environment and human health. A fundamental characterization can be obtained by solving the haplotype assembly problem, which yields the variation across multiple copies of chromosomes. Variations among fast evolving viruses that lead to different strains (called quasispecies) are also deciphered with similar approaches. In both these cases, high-throughput sequencing technologies that provide oversampled mixtures of large noisy fragments (reads) of genomes, are used to infer constituent components (haplotypes or quasispecies). The problem is harder for polyploid species where there are more than two copies of chromosomes. State-of-the-art neural approaches to solve this NP-hard problem do not adequately model relations among the reads that are important for deconvolving the input signal. We address this problem by developing a new method, called NeurHap, that combines graph representation learning with combinatorial optimization. Our experiments demonstrate the substantially better performance of NeurHap in real and synthetic datasets compared to competing approaches.

Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction
Hansheng Xue, Vaibhav Rajan, and Yu Lin'
'School of Computing, Australian National University, Canberra, Australia
School of Computing, National University of Singapore, Singapore [hansheng.. yu lanu edu. au, vaibhav .rajan@nus....... edu. sg
Abstract
Understanding genetic variation, e.g.. through mutations, in organisms is crucial unravel their effects on the environment and human health. fundamental char- acterization be obtained by solving the haplotype assembly problem, which yields the variation across multiple copies chromosomes. Variations among fast evolving viruses that lead to different strains (called quasispecies) also deci- phered with similar approaches. In both these cases, high-throughput sequencing technologies that provide oversampled mixtures of large noisy fragments (reads) of genomes, are used to infer constituent components (haplotypes or quasispecies). The problem is harder for polyploid species where there are more than two copies of chromosomes. State-of-the art neural approaches to solve this NP-hard problem do not adequately model relations among the reads that are important for decon- volving the input signal. We address this problem by developing new method, called NeurHap, that combines graph representation learning with combinatorial optimization. Our experiments demonstrate substantially better performance of NeurHap in real and synthetic datasets compared to competing approaches.
1 Introduction
Our genetic material is organized as sequences of DNA RNA molecules (nucleotides) which form dineeniiinsional structures (chromosomes) within our cells. Most organisms have multiple highly similar copies of chromosomes in their cells (e.g., humans have 2). Variations in genetic sequences lead to the emergence of new species during evolution and are also known to be associated with many diseases (e.g., g., cancer). There many possible ways in which such variations among them is mutation or a change in the nucleotide at a specific location in the DNA or RNA sequence. A Single Nucleotide Polymorphism (SNP) refers which renders the copies nonidentical at that point. An ordered list of SNPs on a single chromosome called haplotype [Schwartz] 2010). Haplotypes provide signature of genetic variability and thus inform us about disease susceptibilities and evolutionary patterns (c.g., of viruses). These studies in turn pave the way for personalized medicine and effective drug development against viruses.
occur; the simplest
mutation in least one of the copies
The problem of inferring haplotypes from high-throughput sequencing data is called haplotype assembly phasing, and is done in multiple stages (see Figure T.. Sequencing data yields multiple copies of short fragments of the entire genomic sequence (called reads, Figure [pp.. These reads are noisy due sequencing errors and their short lengths may span across limited number of SNPs. This makes the problem of haplotype phasing challenging. The reads are first aligned to a reference genome. This step indicates positions that different across reads and thus infers the potential locations of SNPs. All other positions are discarded to obtain the SNP matrix (Figure Tb)). This
*Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Reference Genome
h1
sequencing
aligrment
calling
phosing
h2
Sequences
b) Reads
SNP Matrix
d) Clusters
Haplotypes
NeurHap
NeurHap
-search
-refine
Read-overlap Graph
Figure The pipeline of reference-based polyploid haplotypes reconstruction and NeuralHap. Haplotype phasing is formulated as graph coloring problem by constructing the Read-overlap graph. NeurHap consists of NeurHap-scarch, a graph neural network to learn vertex representations and color assignments, and NeurHap-refine, local refinement strategy further adjust colors.
matrix may viewed as an oversampled mixture noisy reads (restricted to SNPs). Each mixture component represents single haplotype and thus should have SNPs at the same locations.
In diploid species, containing two copies of chromosomes, there are two haplotypes to be inferred. This problem has been studied extensively (Browning and Browning 2011] In polyploid species, containing more than two copies of chromosomes (and thus more than two haplotypes). the problem is more challenging due to dramatic increase in search space (Van de Peer et al. / Saada al. 2022 Jablonski and Beerenwinkel 202T]. In reconstruction of virus strains, called viral quasispecies, from viral populations, similar challenges arise. Moreover, unknown population sizes and imbalanced abundances pose additional difficulties (Jablonski and Beerenwinkel 2021].
Existing approaches for haplotype phasing of polyploid species and viral quasispecies often group reads in the SNP matrix into clusters that correspond different haplotypes, respectively. In an ideal case, all reads from the same cluster should be consistent with respect to SNPs as they all belong to the same haplotype. reality inconsistencies occur due to sequencing errors in reads. Therefore, minimum error correction (MEC) score (Lippert et al.) 2002b) is used to measure the discrepancy between the consensus haplotypes and their associated reads within each cluster (see Figure le). is NP-hard to optimize the MEC score (Zhang et al.) [006]. and a number of combinatorial optimization heuristics have been proposed to approximate the optimal MEC score [Zhang et al. 2020].
More recently, the first neural network -based learning framework, named GAEseq (Ke and Vikalo 2020b), was proposed to phase haplotypes for polyploid species and viral quasispecies. CAECseq was later developed using a convolutional auto-encoder which captures spatial relationships between SNPs and enables clustering reads obtained from highly similar genomic regions [Ke and Vikalo 2020a]. Both GAEseq and CAECseq showed improved results compared to previous approaches. A major limitation of both CAECseq and GAEseq is that they cannot capture implicit relations among different reads. These methods have two independent steps (embedding and clustering) which makes the haplotype phasing results unstable. Besides, sparsity of the SNP matrix makes haplotype phasing for polyploids more challenging for these methods as well.
In this paper, we propose an approach based graph representation learning for haplotype phasing of polyploid species and viral quasispecies. We formulate the haplotype phasing problem as graph coloring problem, where the colors indicate haplotypes. The graph is constructed from the SNP matrix where vertices are reads and two edge types are defined based on pairwise consistency and conflicts with respect SNPs in the reads. Message passing-based neural networks are trained to minimize a loss designed to obtain color assignment that maximizes consistent edges and minimizes conflicting edges. The network learns vertex representations and through them, an initial color assignment. A local refinement strategy is then applied to adjust node colors in order to minimize MEC scores. Thus, in contrast to previous neural approaches that first learn representations and then cluster, our approach models the problem requirements in all steps. As a result, our model achieves better MEC scores, is more stable and also performs well on the challenging cases of polyploids and viral quasispecies. In summary, our contributions are:

---

We provide unique formulation of the haplotype phasing problem as graph coloring problem, and develop an algorithm based on graph representation learning and combinatorial optimization. Our approach consists of NeurHap-searee search, graph neural network to learn vertex representations and color assignments followed by NeurHap-refine, local refinement strategy to adjust colors and optimize MEC scores.
Extensive experiments on synthetic and real datasets demonstrate that our new method Neura aarralHap significantly outperforms state-of-the-art phasing methods for both polyploid species and viral quasispecies.
Related Work
Haplotype Phasing. The aim of haplotype phasing of polyploid species and viral quasispecies is to group reads into homogeneous clusters that corresponds to different haplotypes, respectively. The minimum error correction (MEC) score [Lippert et al., (0026) is introduced measure the total discrepancy of reads in all clusters but is NP-hard to be optimised (Zhang et al. (006). Haplotype phasing for diploid species (i.e., reconstructing two haplotypes) has been extensively studied in the last two decades and a number of combinatorial optimization heuristics have been proposed to approximate the optimal MEC score, such as BNB [Wang et al. 2005). HapCUT [Bansal and Baina 2008 HASH [Bansal et al. 2008). RefHap [Duitama et al. 2012) ProbHap 22144]
HapCUT2 Edge et al., 2017] and others, and refer Zhang et al. 2020 for a recent review on
phasing diploid species.
Haplotype phasing for polyploid species (i.e., reconstructing more than two haplotypes) becomes more computationally challenging as it requires a much larger search space compared to phasing two haplotypes for diploid species. A limited number of phasing methods work for polyploid
species, e.g., HapCompass [Aguiar and Istrail 2012). SDhaP [Das and Vikalo 2015). H-PoP (Xie)
al. 2016), AltHap (Hashemi et al.] 2018), refer to Abou Saada et al. [022 for recent review. Haplotype phasing for viral quasispecies is very similar to the problem of phasing polyploid species. While haplotypes in polyploid species typically have uniform abundances, the different haplotypes (strains) in viral quasispecies may have varying abundances. Quite a few tools have also been proposed for haplotype phasing of viral quasispecies. such as ViSpA [Astrovskaya et al. [01T]] ShoRAH ZZagordi et al. 2011]. QuRe [Prosperi and Salemi 2012). QuasiRecomb Töpfer et al. 2013). PredictHaplo Praabakarann et al. 2014), aBayesQR [Ahn and Vikalo 2018). TenSQR [Ahn et al. 2018). refer to [Jablonski and Beerenwinkel] [021] for a recent review.
More recently, deep learning models have been introduced into haplotype phasing for polyploid species and viral quasispecies. GAEseq [Ke and Vikalo, 20205) uses a graph auto-encoder model on the constructed reads-SNPs bipartite network to model the relations between reads and SNPs. CAECseq [Ke and Vikalo, [020a] uses a convolutional auto-encoder model to represent reads as low-dimensional features and then employs a clustering algorithm to group these reads. Note that GAEseq and CAECseq can be directly used to phase haplotypes for both polyploid species and viral quasispecies. Experimental results on both simulated and real datasets showed the superior results of GAEseq and CAECseq (in terms of MEC scores) compared to previous approaches for haplotype phasing for both polyploid species and viral quasispecies [Ke and Vikalo 2020bla However, implicit relations among different reads have not been fully captured by GAEseq and CAECseq. especially when embedding and clustering are modelled separately and the SNP matrix is sparse.
Neural Networks on Graphs. Most existing graph neural networks can be explained as message- passing based graph learning model which recursively combines learned features/messsges from their neighbors [Cui et al. 2019 Cai et al. [2018] Gilmer et al. 2017). Popular methods include GCN Kipp and Welling 2017 7 GraphSAGE [aamilton et al. 2207]]. GAT (Veličković et al. 2018 and GIN [uu
et al. 2019 I. All these methods make the homophily assumption that similar nodes in the graph should
be embedded close together. However, graph coloring aims assign pairwise nodes with distinct
colors for each edge of the graph, which is opposite to the homophily assumption. An intuitive way to integrate GNN models into the graph coloring challenge is to adjust the loss function, such as GNN- GCP [emos et al. 2019. RUN-CSP (Toenshoff et al., 2019). and PI-GNN [Schuetz et al. 2022). However, existing GNN-based graph coloring models cannot be implemented to the read-overlap graph directly because they cannot handle conflicting and consistent edges simultancously.
3

---

3 Methodology
Overview. In this paper, we propose the model of neural networks for graph coloring optimization to solve the haplotype reconstruction problem, called NeurHap. NeurHap mainly contains three steps, i) constructing the read-overlap graph; ii) global coloring searching via iterative neural networks model, NeurHap-search; iii) local refinement to fine tune final coloring, NeurHap-refine.
Notations. Let be the number of haplotypes in cell of polyploid species (aka. ploidy) or the number of strains in viral quasispecies. For example, human and other mam- mals contain two haplotypes (diploid, k=2); plants have more than 2 haplotypes (e.g.. California redwood has six copies of each chromosome, hexaploid, k= Viral qua- sispecies mixing? distinct HIV strains will have 5.
a) SNP Matrix A A
Read-overlop Graph
TTC
R5 T AAA
A
G
Single nucleotide polymorphisms (SNPs) refer to positions where not all haplotypes have the same alleles. Given the alignment of reads to a reference genome, the SNP columns can be identified by removing the columns with identical alleles. The remaining alignment is referred to as a m X n SNP matrix where m denotes the number of reads and n is the number of SNPs. The haplotype reconstruction aims to group m reads into k clusters {C1, C2,.... ) that correspond to & haplotypes, [H,, H2..... H respectively. Once reads are grouped into clusters, the haplotype H. can be reconstructed from reads in C, using a simple consensus voting. In the ideal case, all the reads from the cluster C₁ will be all consistent with H., In reality, this not the case and thus a minimum error correction (MEC) score [Lippert et al. 2002b is introduced to measure the discrepancy between the reads in the cluster C2 and the consensus haplotypes H4 in all clusters. Given the grouping of reads into clusters {C1, C2...., Ck). the corresponding MEC score can be computed as
Figure A toy example of constructing read-overlap graph with conflict edges (in grey) and consistent edge (in blue).
MEC(C1, C2....,CC,)
Cx)=
Σ Σ RJ) 1=1 RYEC;
(I)
where D(.) is the Hamming distance function. Note that HDHH,, R₂) for Rg E C. can only be computed when we know all the reads in the cluster Cs and use them to derive the consensus haplotype H. of C₁ The main challenge in haplotype phasing find the grouping of reads into (C1,C2,.... Cj} such that the MEC score is minimized.
Two reads are called overlapping if they span Given any two reads, the relationship between them belongs to one of three cases, consistent, conflict, ambiguous. While the relationship between two non-overlapping reads is always ambiguous, further introduce two parameters p and to define the relationship between two overlapping reads to account for sequencing errors and alignment ambiguity. Two overlapping reads are consistent if they overlap at least positions and have the same alleles over all overlapping positions; are in conflict if they differ on at least q overlapping positions; and are ambiguous otherwise. The term 'ambiguous' means that there is not enough evidence to support that these two reads should belong to the same haplotype (' ('consistent') or should belong to the different haplotypes ( ('conflict'), ). For example, in Figure 2 R4 and Ry are consistent, Ri and R2 are in conflict, and R₁ and R4 are ambiguous. In an ideal case, all the overlapping reads in the same cluster must be consistent. i.c., if two reads are in conflict, they must belong to different clusters. This observation naturally motivates us to build a read-over overlap graph to model all reads as vertices and the important pairwise relationships (i.e., consistent and conflict) between overlapping reads as edges. Moreover, if we use k colors to represent the l clusters of reads, the problem of haplotype phasing reduced to graph coloring problem on the read-overlap graph. For example, in Figure
common SNP positions otherwise non-overlapping.
2 the minimum MEC is achieved by grouping nine reads into three clusters, C1 = (R1, R4, R7), CO- = (R2, Rs, Rs) and C3- = (Ra, Ro, Rg). which correspond to three distinct colors corresponding vertices in the read-overlap graph, respectively.

---

3.1 Graph Coloring over the Read-overlap Graph.
The read-overlap graph = (V,&=,& Ex)
) is constructed in this step. Here, the vertex set denotes all reads, the edge set &= represents all pairwise consistent relationships between overlapping reads, and the edge set & refers to the pairwise conflict relationships between overlapping reads.
Now we are ready to reduce the problem of haplotype phasing to the graph coloring problem on the read-overlap graph. Recall that the haplotype phasing problem aims group reads into k clusters such that reads from the same cluster are as consistent as possible. If we employ c(v) to represent one out of k colors assigned and R2 are in the same cluster if and only if two corresponding vertices v; and új have the same color, i.e., c(v:)= = c(vz). Now the graph coloring problem needs assign a color c(v) for every vertex v E V to minimise the MEC score under the constraints that any two conflicting reads have two different colors and any two consistent reads have the same color.
read v (i.e., one of the k clusters that belongs to), two reads Rg
min d()) ..., d(v)))
minn Σ c(5)==
HD(H,,
Y(e uy) E Eg, cu:) + c(t)) V(e,, U2) E.m.. d(;) c(u))
s.l.,
Note that the above graph coloring problem is different from the classical graph coloring prob- lem [Pardalos et al.] [998] in combinatorial optimization. While all the edges are conflicting edges in the classical graph coloring problem, the above problem formulation in the equation 2 has constraints for both conflicting and consistent edges. In the following section, we will show how to model these constraints using neural networks.
3.2 Network-based Global Search and Combinatorial Optimization-basse Local Refinement
Satisfying Constraints. As the vertices of the read-overlap graph need to be colored to satisfy the constraints in the equation? 2 we further reduce the graph coloring problem to constraints satisfaction problem inspired by RUN-CSP [Toenshoff et al. 2019]. Graph neural networks (GNNs) are designed to follow homophily constraints such that similar vertices in the graph are embedded close to each other (i.e., same colors). While this true for consistent constraints in the read-overlap graph, the conflicting constraints impose heterozygous constraints, i.e., vertices connected by conflicting edge should have very different embeddings (i.e., different colors). Therefore, given k distinct colors, we introduce two 0/1 metrics in B for incorporating the above two different coloring constraints, M4 (for conflicting constraints) and M_ (for consistent constraints). The conffict-constrait matrix M& denotes the binary conflict relationships among k colors, i.e., (i, j) 1 if i * and 0 otherwise, for any i, E [1,....k k.. The consistent-constraie relationships between i colors, i.e., (i, = 1 if = and otherwise, for any i,j E {1....,k) k).
matrix M_ denotes the consistent
Assume that the coloring assignment matrix P E IR Vi is a matrix that represents the coloring assignment probability (over colors) for each vertex v in its corresponding row P(v). For any conflicting edge (0, M²} & in the read-overlap graph, we aim to assign different colors to and By and thus maximize the sum of probabirbbaiilities with different colors, i.e., P(u;) M(P;)))(())) Symmetrically, for any consistent edge (V;, v;)) E &- in the read-overlap graph, we aim to assign the same color to U; and v and thus maximize the sum of joint- point-probabilities with same colors, i.c., M(x:)__((rr;) T. In summary, the unsupervised objective function can be formulated follows:
1
L =
Σ log(P(o.)M,P(u))) X
Σ
((x))) (3)
E
(PLRy)EE.
Here, À controls the importance of consistent constraints compared to conflicting constraints. We will now show how to use representation learnings to derive a coloring-assignmeen assignment matrix that optimizes the above objective function.
Global Search: NeurHap-search. To derive a coloring-assggmmentt matrix P, we propose to use an iterative message passing-based representation learning model to capture the structural information of the read-overlap graph. The message-passing learning model mainly contains three operation functions, message-learning, aggregation, and combine operator. Given trainable d-dimensional
5

---

embeddings for every nodes {h(r1), h(v2). h(wa)) h(()) E Rd, Vs E V. which are initialized by randomly sampling from a uniform distribution, the message passing model can be formulated as:
h(u;)) = COMBINE(((".). h(m))), m(:) AGGREGATE (MESAAAAEE(MSSSSSSEEEEECC.)))
: e ((x)))).
Here, m(e;) is the learned messages from the neighbors of u; and ((;)) is the neighbors of U; with respect to conflict edges. COMBINE(.) is a combine function and AGGREGATE(.) de- notes aggregation function. To search for a simple model, adopt recent message updater and mean operator (m((;)) = [N( (e,EN(e:) () as combine and aggregate functions respec- tively. MESSAGE()) represents the learnable message function, e.g. MESSAGE(h((:) h(v,)) (a(o)))))(((;)) Two linear layers with activation function (e.g.. ReLU) are selected to construct the MLP layer. A simple linear decoder can be used map the learned node embeddings to the probability of colors: P(u;) = DEC(h(v;)) The message- passing model is iteratively trained for t times in each epoch generate reliable features for each node. The pseudocode for the global search process of NeurHap is as follows:
Algorithm 1: The Global Search Algorithm NeurHap-scarch
Data: SNP matrix R; number of iteration t; number of polyploids k; dimension of hidden features
Result: Assignments y.
Ex, &- +- Equation |
// Construct conflict and consistent edge set // Initialize coloring constraints Initialize by uniform distribution
M (k). (M(
Rd~ 1)
for epochs do
for & iterations do
m(u,) = msg((h(;))..... h(,)) = MLP(H(4)((b(s))
|/ Compute message
from h(w)) and h(p;))
m(v;) (m))) uy E N(:))) // Aggregate messages from
neighbors 0. h(v;)) comb(m(r;), h(v:)) // Combine messages from h(v:) and m(v;)
end
10
P dec(h(e;)
// Compute coloring assignment probs
11
[ t Equation
// Compute conflict loss Compute coloring assignment
12
y P
13
end
After optimizing the objective function with NeurHap, we can obtain an initial coloring assignment for vertices that satisfy the constraints in the equation in the read-overlap graph. However, the objective function in equation 2 (i.e., the MEC score) may not be optimized as there may exist multiple coloring assignments that satisfy all constraints. Therefore, we run an additional local refinement step to further optimise the objective function in equation
Local refinement: NeurHap-refine. This step mainly searches for possible color adjustments of individual vertices given their associated conflictigg and consistent constraints. More specifically, an individual vertex can be assigned color different from its current color without violating any of the associated conflicting constraints with the neighboring vertices, the color is changed if better MEC score is obtained by the change. The refinement algorithm, NeurHap-refine, iteratively explores these possible color adjustments of individual vertices. Refer to Appendix A. for the pseudocode.
4 Experiments
Dataset. To evaluate the proposed method NeurHap, we compare NeurHap with state-of-the-arr baselines for both polyploid species and viral quasispecies. i) Polyploid species: The Solanum Tuberosum Tetraploid (k=4) and the datasets of Solanum Tuberosum contains both simulated dataset Sim-Potato and real-world dataset Real-Potato, both downloaded from [Ke and Vikalo b)] Sim-Potato contains 40 sub-datasets, which contains ten different samples sequenced four distinct coverages (5X, 10X, 20X, and 30X). Real-Potato is the Chromosome 5 capture-seq

---

data of a small solanum tuberosum population available at NCBI (accession SRR6173308 Tem samples are generated by randomly selecting ten genomic regions as the reference genome. ii) Viral Quasispecies: Three viral quasispecies datasets are downloaded from SAVAGI [Baaijens et al. 2017]. including the human immunodeficiency virus (5-strain HIV, k=5), the hepatitis C virus (10-strain HCV, /0), and the zika virus (15-strain ZIKV, k=/5). Ten samples are generated by
randomly sampling from each of these three datasets. In this paper, we use BWA-MEM [Li 2013) to
align reads to the reference genome and use the same tool described in CAECseq and GAEseq Ke
and Vikalo 2020a to derive the SNP matrix from the above alignment to ensure a fair comparison.
Baseline algorithms. GAEseq Ke and Vikalo 2020b] and CAECseq [Ke and Vikalo 2020a] are two ofate-of-the-art approaches that work on both haplotype assembly and viral quasispecies reconstruction. We included two additional methods, H-PoP [Xie et al., 2016), AltHap [Hashemi eet al., 2018), that specifically work on haplotype assembly for polyploid species. We also included one additional method, TenSQR (Ahn et al.) 2018), that specifically works on viral quasispecies reconstruction. Many other specitic methods are not included in this study because GAEseq [Ke] and Vikalo 2020b] and CAECseq [Ke and Vikalo 2020a] have recently demonstrated their superior performance against other baselines in both haplotype assembly and viral quasispecies reconstruction.
Experimental setup. The minimum error correction (MEC) score, given in equation | is adopted as the evaluation metrie [Lippert et al. 2002a for both haplotype assembly and viral quasispecies reconstruction. Following the experimental setup in [e and Vikalo 2020a (), all the algorithms run ten times on each input dataset and the lowest MEC score is reported. The initial number of polyploids A is known: k = 4 for both Sim-Potate and Real-Potato, & = 5 for 5-strain HIV, k = 10 for 10-strain HCV, and 15 for 15-strain ZIKV V. The default settings of NeurHap hyperparameter are as follows. The representation dimensions are all empirically set to be 32. The number of iteration t in NeurHap-search is set to be 10 as default. The parameter À chooses 0.01 as the default value. The default values for parameters p and are 3 and 5, respectively. The NeurHap model is freely available at testpa///gitie
com/ http///uuaannnnnneeieeeee Neu
4.1 Performance on Polyploid Species data
T and 2 shoow that NeurHap sig-
Table 1: Performance comparison on Sim-Potato data.
nificantly outperforms state-of-the-att baselines, which achieving the lowest MEC scores on both the Sim-Potato and Real-Potate datasets. For Cov- 5X of Sim-Potato, the MEC score obtained by NeurHap is 29.9 which about 3x lower than the lowest scores achieved by baselines (96.2 for CAECseq). For Real-Potato, NeurHap also achieves the lowest MEC scores on all samples. The average MEC score achieved by NeurHap is 371.6 which is significantly lower than the second lowest MEC score obtained by CAECseq, 400. The gap between NeurHap and baselines demonstrates the superiority of our model in polyploid haplotype phasing.
Model
#Cov 5X
#Cov 10X
#Cov 20X
#Cov 30X
H-PoP
429.0.164.1
133.91103.
2826.9 1782.2.161.88
1880777
AltHap
610,9+259.3
122.3+179.1
649.3+3694
1148. 2:+-099.9
GAEseq
153.7=20.3
261.6=58.7
372.8+745
496.9+128.7
CAECseq
96.2++26.9
141.4=407
254.2+992
372.9+118899
Neurflap
29.94:5.7
51.9:182
92.6=10.6
142.0::23.6
Table 2: Performance comparison on
data.
Sample
#1
#2
#3
#4
#5
#6
#7
#8
#9
#10
Avg.
Reads
240
389
274
115
141
398
295
284
489
449
SNPs
294
238
83
23
176
198
456
424
236
410
H-PPP
705
525
132
4
240
982
981
766
793
1413
654. 1:435666
AltHap
746
572
192
299
1295
1021
982
811
1311
1
GAEseq
231
406
180
873
558
441
592
712
409.2
CAECseq
229
393
103
172
859
522
430
593
698
400.0+260.9
NeurHap
178
343
93
163
857
499
384
561
632
371.6.1268.9
7

---

4.2 Performance on Viral Quasispecies data
Table shows the results obtained by NeurHap and baselines for reconstructing viral quasispecies on three datasets respectively, 5-strain HIV. 10-strain HCV, and 15-strain ZIKV. In Table NeurHap significantly outperforms baselines on all 10 samples in these datasets. NeurHap achieves the lowest MEC score in 5-strain HIV (1371.4), .4), which is about 160 lower than the MEC score obtained by CAECseq (1638.5). For 10-strain HCV data, NeurHap also achieves the lowest MEC score 1008.1 and the second lowest MEC score is 1144.3 obtained by TenSQR. With increase in the number of haplotypes (strains), performance of CABCseq and GAEseq deteriorates and while that of NeurHap improves. NeurHap significantly outperforms CAECseq and GAEseq polyploid haplotypes.
Table 3: Performance comparison on three viral quasispecies datasets.
Dataset
#1
#2
43
#4
#5
#6
#7
#8
#9
#10
Avg.
Reads
967
961
951
961
966
969
962
965
955
971
SNPs
1617
1685
1595
1605
1615
1660
1619
1622
1580
1653
S-strain HIV
TenSQR
1920
2324
1867
1896
2055
1793
2125
1754
1679
1757
1917.0.198.
198.6
GAEseq
1981
1953
1678
1806
1905
2007
1819
1746
1702
1747
1834,4=119.
CAECseq
1729
1750
1787
1552
1730
1622
1611
1529
1519
1556
1638
NeurHap
1307
1525
1385
1265
1410
1382
1393
1323
1274
1450
1371.4:81.2
Reads
500
498
500
499
498
500
499
500
500
500
SNPs
1770
1712
1794
1749
1741
1759
1786
1765
1743
1808
10-strain HCV
TenSQR
1081
1037
1106
960
1115
1015
1365
1293
1396
1075
15
GAEseq
1270
1121
1301
1171
1245
1152
1371
1105
1152
1200
1208.81888
CAECseq
1490
1616
1347
1675
1475
1405
1563
1413
1436
1554
1033.
NeurHap
1029
990
1097
956
1012
899
1014
1008
1079
997
1:56.1
Reads
500
500
500
500
500
499
498
497
499
500
SNPs
2384
2358
2385
2360
2386
2383
2375
2373
2353
2353
15-strain ZIKV
TenSQR
941
794
859
869
9.50
8.56
848
789
849
758
851.316615
GAEseq
1470
15855
1.115
1,590
1713
1363
1523
1348
1618
1393
1511.811194
CAECseq
2344
2248
2427
2338
2454
2406
2378
2496
2292
2309
2369.2+77.4
NeurHap
718
655
752
721
862
658
694
622
666
675
702.3167.8
4.3
Visualization
To better understand the phasing results, we use python-iGraph package to visualize the read-overlap graph of 55m-Potao-5X dataset with clustering results from NeurHap. CAECseq. and GAEseq (see Figure B Different colors denote distinct haplotypes (the number of haplotypes for Sim-Potato is 4). Grey edges are conflicting edges and blue edges are consistent edges in the read-overlap graph. The color of nodes in Figure 3 are derived from the clusters constructed by different models, i.e., Figure b) and c), 89 and 133 conflicting edges are violated (i.e., connecting two vertices with the same color) for CABCseq and GAEseq, respectively, while none of the conflicting edges are violated for NeurHap. NeurHap derives a coloring assignment that is most consistent with the conflicting and consistent edges the read-overlap graph.
each color indicates a cluster of reads that are inferred to come from the same haplotype.
Figure 4 the search process of NeurHap on the Sim-Potato-S5 SXX Sample 1 as an example. The sub-figure a) shows the grid layout of the initial coloring of the read-overlap graph violates significant number of conflicting edges (in grey) and consistent edges (in blue). With the increasing number of epochs, the number of violating constraints (confficting and consistent edges) decrease significantly.
4.4 Experimental Analysis
Ablation study. To study the effectiveness of our proposed model, we conduct ablation study to examine the two algorithmic components in NeurHap, graph neural network-based algorithm NeurHap-scarch and local combinatorial sptimisation-basee refinement algorithm NeurHap-refine.
8

---

a) NeurHap (MEC-27)
b) CAECseq [MEC-100]
c) GAEseq [MEC-196]
Figure 3: The visualization of NeurHap, CAECseq. and GAEseq Sim-Potato- 5X-Samplel data.
a) epoch=0
b) epoch=10
c) epoch=30
d) epoch=70
Figure 4: The grid layout of read-overlap graph with the violating edges in the training of NeurHap.
Figure shows that NeurHap-refine is able further optimize the MEC score, e.g., the MEC scores for 5-strain HIV by NeurHap-searde and NeurHap are 1453.5 and 1371.4 respectively, demonstrat- ing the complementary effectiveness of global search and local refinement algorithms phasing haplotypes.
Parameter analysis & Running time. We investigate the importance of core parameters in model, including p and q for read-overlap graph, À for consistent constraints, for iterations, and for feature dimension. The detailed parameters analysis is listed in the Appendix A.3. We benchmark the running time of NeurHap against two deep learning baselines CAECseq and GAEseq on the Sim- Potato-Cov30 data. NeurHap achieves the lowest MEC score (142.0) compared with CAECseq (372.9) and GAE- seq (496.9). The running time of NeurHap 258 seconds which is faster than CAECseq (341 seconds). GAEseq is the slowest among the three and takes 492 seconds.
seurrh
NeurHap
MEC
500
Sim Rexi-Potato 3-strain 10-struin MC
HIV
S-straln-IKVV
Figure Results NeurHap-search and NeurHap (NeurHap-searde + NeurHap-refine) on all five datasets.
Conclusion
In this paper, we propose NeurHap. a graph representation learning approach to reconstruct haplotypes of polyploid species and viral quasispecies. We give novel formulation of the haplotype phasing problem graph coloring problem. We design a message-passian search framework over carefully constructed graph to assign colors (indicating haplotypes) to the reads, and local refinement step adjust colors optimize MEC scores. Extensive experiments on both simulated and real-world datasets demonstrate the effectiveness of our proposed NeurHap model on phasing haplotypes from polyploid species and viral quasispecies. A limitation our method in its ability to handle long reads. Massive long reads in polyploids leads to an even larger search space that may addressed by extensions to our approach future work. Besides, NeurHap cannot automatically discover the number of haplotypes. This limitation will be addressed going forward.
based graph neural network

---

References
Omar Abou Saada, Anne Friedrich, and Joseph Schacherer. Towards accurate, contiguous and complete alignment-based polyploid phasing algorithms. Genomics, 114(3)110066) 2022.
D. Aguiar and Sorin Istrail. Hapcompass: fast cycle basis algorithm for accurate haplotype assembly of sequence data. Journal of computational biology, 19 6:577-90, 2012.
Soyeon Ahn and Haris Vikalo. abayesqr: A bayesian method for reconstruction of viral populations characterized by low diversity. Journal of computational biology, 25:637-648, 2018.
Soyeon Ahn, Ziqi Ke, and Haris Vikalo. Viral quasispecies reconstruction via tensor factorization with successive read removal. Bioinformatics, 34:i23 i31, 2018.
Irina Astrovskaya, Bassam Tork, Serghei Mangul, Kelly Westbrooks, Ion I. Mändoiu, Peter Balfe, and Alex Zelikovsky. Inferring viral quasispecies spectra from 454 pyrosequencing reads. BMC Bioinformatics, 12:S1 S1, 2011.
Jasmijn A. Baaijens, Amal Zine El Aabidine, Eric Rivals, and Alexander Schönhuth. De novo assembly of viral quasispecies using overlap graphs. Genome research, 27 5:835-848, 2017.
Vikas Kumar Bansal and Vineet Bafna. Hapcut: efficient and accurate algorithm for the haplotype assembly problem. Bioinformatics, 24 16:i153-9, 2008.
Vikas Kumar Bansal, Aaron L. Halpern, Nelson Axelrod, and Vineet Bafna. An meme algorithm for haplotype assembly from whole-genome sequence data. Genome research, 18 8:1336-46, 2008
Sharon Browning and Brian L Browning. Haplotype phasing: existing methods and new develop- ments. Nature Reviews Genetics, 12(10):733-714, 2011.
Hong Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. comprehensive survey of graph embedding: Problems, techniques, and applications. TKDE, 30:1616-1637, 2018.
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu, survey on network embedding. TKDE, 31: 833-852, 2019.
Shreepriya Das and Haris Vikalo. Sdhap: haplotype assembly for diploids and polyploids via semi-definite programming. BMC Genomics, 16, 2015.
Jorge Duitama, Gayle K McEwen, Thomas Huebsch, Stefanie Palczewski, Sabrina Schulz, Kevin J. Verstrepen, Eun- KuunK Suk, and Margret R. Hoehe. Fosmid-basse based whole genome haplotyping of hapmap trio child: evaluation of single individual haplotyping techniques. Nucleic Acids Research, 40:2041 2053, 2012.
Peter Edge, Vineet Bafna, and Vikas Kumar Bansal. Hapcut2: robust and accurate haplotype assembly for diverse sequencing technologies. Genome research, 27 5:801-812, 2017.
Justin Gilmer, Samuel Schoenholz, Patrick F, Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Abolfazl Hashemi, Banghua Zhu, and Haris Vikalo. Sparse tensor decomposition for haplotype assembly of diploids and polyploids. BMC Genomics, 19(191), 2018
Kim Philipp Jablonski and Niko Beerenwinkel. Computational methods for viral quasispecies assembly. In Virus Bioinformatics, pages 51-64. Chapman and Hall/CRC, 2021.
Ziqi Ke and Haris Vikalo. convolutional auto-encoder for haplotype assembly and viral quasispecies reconstruction. In NeurlPS, 2020a.
Ziqi Ke and Haris Vikalo. graph auto-encoder for haplotype assembly and viral quasispecies reconstruction. In AAAI, 2020b.
10

---

Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Volodymyr Kuleshov. Probabilistic single-individual haplotyping. Bioinformatics, 30:i379 - 1385, 2014.
Henrique Lemos, Marcelo O. R. Prates, Pedro H. C. Avelar, and Lamb. Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. 2019 IEEE 31st International Conference Tools with Artificial Intelligence (ICTAI), pages 879-885, 2019.
Heng Li. Aligning sequence reads, clone sequences and assembly contigs with bwa-mem. arXiv: Genomics, 2013.
Ross Lippert, Russell Schwartz, Giuseppe Lancia, and Sorin Istrail. Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Briefings in bioinformatics, 3(1): 23 31, 2002a.
Ross Lippert, Russell Schwartz, Giuseppe Lancia, and Sorin Istrail. Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Briefings in bioinformatics, 3(1): 23-31, 2002b.
Panos M Pardalos, Thelma Mavridou, and Jue Xue. The graph coloring problem: A bibliographic survey. In Handbook of combinatorial optimization, pages 1077-1141. Springer, 1998.
Sandhya Prabhakaran, Mélanie Rey, Osvaldo Zagordi, Niko Beerenwinkel, and Volker Roth. Hiv haplotype inference using propagating dirichlet process mixture model. JEEE/ACM Transactions on Computational Biology and Bioinformatics, 11:182-191, 2014.
Mattia C. F. Prosperi and Marco Salemi. Qure: software for viral quasispecies reconstruction from next-generation sequencing data. Bioinformutics, 28 1:132-3, 2012.
Martin J. A. Schuetz, J. Kyle Brubaker, and Helmut G. Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. ArXiv, abs/2107.01 2022.
Russell Schwartz. Theory and algorithms for the haplotype assembly problem. Communications in Information and Systems, 10(1):23-38) 38, 2010.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Run-csp: Unsupervised learning of message passing networks for binary constraint satisfaction problems. ArXiv, htw///9990088888 2019.
Armin Töpfer, Osvaldo Zagordi, Sandhya Prabhakaran, Volker Roth, Eran Halperin, and Niko
Beerenwinkel. Probabilistic inference of viral quasispecies subject to recombination. Journal of computational biology : j.oourall of computational molecular cell biology, 20 2:113-23, 2013.
Yves Van de Peer, Eshchar Mizrachi, and Kathleen Marchal. The evolutionary significance of polyploidy. Nature Reviews Genetics, 18(7):411-42 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018.
Rui-Sheng Wang, Ling- Yun Wu, Zhen-Ping Li, and Xiang-Sun Zhang. Haplotype reconstruction from snp fragments by minimum error correction. Bioinformatics, 21 10:2456 62, 2005.
Minzhu Xie, Qiong Wu, Jianxin Wang, and Tao Jiang. H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids. Bioinformatics, 32324))3735-3744 2016.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Osvaldo Zagordi, Arnab Bhattacharya, Nicholas Eriksson, and Niko Beerenwinkel. Shorah: es- timating the genetic diversity of a mixed sample from next-generation sequencing data. BMC Bioinformatics, 12:119- 119, 2011.
11

---

Xiang- Sun Zhang, Rui-Sheng Wang, Ling- Yun Wu, and Wei Zhang. Minimum conflict indi- vidual haplotyping from smp fragments and related genotype. Evolutionary Bioinformaties, 1176934400000000032, 2006.
Xingtan Zhang, Ruoxi Wu, Yibin Wang. Jiaxin Yu, and Haibao Tang. Unzipping haplotypes in diploid and polyploid genomes. Computational and structural biotechnology journal, 18:66-72, 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes]. [No] or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questionn/annswes below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [N/A]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Code will be made publicly available upon the publication of the paper.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and Appendix A.2.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] We select the lowest MEC score as the final results after running experiment 10 times which is same as previous SOTA basclines.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix A.2.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "n4O8wK1Cwsb", "reviewer": "Reviewer_BGfU", "summary": "Haplotype assembly is crucial for resolving the fine structure of structural variation, detecting copy number variation, SNP panel imputation (these tasks in diploids), and reconstruction of viral \"quasispecies\". Assembly is more difficult with shallower sequencing, increasing ploidy, increasing sequencing error, and increasing numbers of related strains.\n\nThe authors define the assembly problem for ploidy > 2, given a priori a number N of chromosomes or species, and a set of reads aligned to a reference, as assigning reads to N haplotypes (\"colouring\") are aligned to minimize the summed hamming distances between each of the reads and their respective consensus haplotype (the so-called MEC). This problem is unfortunately NP-hard.\n\nThe authors first relax the problem by allowing themselves to merely assign each read a probability of belonging to each haplotype, solving the original problem by simply assigning each read the most likely colour (this is taken from previous work). Next they write a heuristic loss for this relaxed problem. The loss penalizes overlapping and consistent (> p bases overlapping, all the same) reads being assigned to different haplotypes and overlapping and inconsistent (> p bases overlapping, > q different - p, q are hyperparameters) being assigned to the same haplotype.\n\nPrecomputing which reads overlap and are consistent or inconsistent, the authors propose minimizing the objective the following way:\nassign each read an embedding that is put through a neural network\nAfter obtaining a colouring by minimizing this heuristic objective, the authors \"tune\" the colouring to minimize the MEC as well. However, in figure 5 (compared to table 3), the authors demonstrate that most of the performance improvement of the model compared to previous methods comes from simply minimizing the heuristic loss.\n\nThe authors demonstrate their ability to minimize the MEC on a number of benchmarks", "questions": "1) My primary question: The loss in equation (3) must be minimized over a space of dimension #reads X (#haplotypes-1). The largest this dimension ends up being in the benchmarks is 500 x 14 = 7000. Is it not thus possible to perform gradient descent on the haplotype membership probabilities directly? It also seems that since the GNN method involves optimizing the initial embeddings of all reads, optimizing the GNN is a higher dimensional problem than optimizing the membership probabilities directly. (Other NN methods cited -CAECseq and GAEseq- avoid the problem of the dimensionality of the optimization problem scaling with number of reads by using the one-hot encoded sequence or the column of the SNP matrix to construct the initial embedding, in principle reducing the dimension of the optimization problem.)\n\n2) Why do the benchmarks contain so few reads and only aim to reconstruct small parts of a chromosome? Methods exist for diploid haplotype assembly that are accurate for 100s of kb containing substantially more than 1000 reads. H-PoP looked to assemble over 60 thousand reads with 12 thousand SNPs in their publication. Is scaling to the size of an entire chromosome a difficulty for your method? Is this scaling not necessary for use of these algorithms?\n\n3) Why only focus on MEC as a performance metric? It is known that the presence of reads with errors means that the correct phasing may not be the one with the lowest MEC. Many alternatives, including switch error rate are presented in the author's citation Saada OA et al, 2022. This seems to be an important consideration especially when introducing a new metric to minimize.", "limitations": "It seems that the primary limitation of this method is its inability to scale beyond small datasets assembling short reads from only a fraction of a chromosome at once. At least evidence was not shown of scaling to larger datasets.\nThe authors have not suggested a method to tune hyperparameters p and q for arbitrary datasets, which may be required for sequencing with different read length and quality.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) Data and code was easily accessible, making it easy to tell what the authors did. Although the particular parameters used to run the code are not available.\n2) The authors seemingly pose what seems to be a new objective for the relaxed assembly problem whose minimization seems to also minimize the MEC.\n3) The authors propose a method that, in attempting to minimize this new objective, succeeds in minimizing the MEC more than previous methods.\nWeaknesses:\n1) I am concerned the benchmarks do not justify the use of the GNN.\n2) I am concerned benchmarking using only MEC on very small datasets may not display any possible pathology of the assembly and doesn't demonstrate the ability of the model to scale to relevant data sizes.\n(See questions)\nBecause of these concerns, the validation provides enough guidance to practitioners on the strengths and efficacy of the model.\n3) The main text leaves certain concepts ambiguous: i) the authors did not make it clear in the main text what parameters were being optimized in the methods, in particular the initial embeddings. ii) it was not stated unequivocally that the authors themselves had come up with the objective (3), or what they were inspired by.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jZveUcabLuC", "reviewer": "Reviewer_X2sa", "summary": "This paper explores the haplotype assembly/phasing problem through the lens of graph coloring and proposes a solution based on graph representation learning with a local search refinement. The problem admits a unique graph coloring formulation that differs from conventional graph coloring in that there can be consistent and conflict edges, whereas, traditionally, graph coloring would only handle conflict edges. Similarly, graph neural networks typically assume that similar nodes should have similar embeddings, but this assumption is challenged in the current setting. The authors formulate a loss function to account for both types of edges and their experiments demonstrate a significant improvement over competing approaches.", "questions": "1. Can you provide more details on how the COMBINE, AGGREGATE, and MESSAGE functions are defined?\n2. How do you see the notions of similar and dissimilar embeddings via consistent and conflict relationships being generalized to graph neural networks more broadly?", "limitations": "The authors claim that Section 5 covers limitations, though details are scarce.\n\nSome minor comments:\n\"haploytypes\" -> haplotypes\n\"Neural Networks on Graph.\" -> Neural Networks on Graphs.\n\"functionm\" -> function\n\"} respectively\" -> }, respectively\n\"Two overlapping read are called\" -> reads\n\"naturally motives\" -> naturally motivates\n\"constraints satisfying problem\" -> constraint satisfaction problem\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* A nice reduction from the haplotype assembly/phasing problem to a modified graph coloring problem is proposed, thereby introducing opportunities to leverage work done in that field.\n* A novel loss function is derived that accounts for similarity and dissimilarity of vertex relationships via consistent and conflict edges, respectively. This may even be generalized to graph neural networks more broadly.\n* Experiments are performed on synthetic a real-world datasets, demonstrating an improvement over competing approaches.\n\nWeaknesses\n* Some details are missing on how the COMBINE, AGGREGRATE, and MESSAGE functions are defined", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SL6mVrWfs36", "reviewer": "Reviewer_uUcF", "summary": "The paper proposes a GNN-based approach for clustering reads (short biological sequences) that come from a stochastic process of sampling, with errors, subsequences from a few similar, but different, long sequences (e.g. genomes of several viral quasispecies); the ultimate goal of the method is to infer these long sequences from a set of short reads.", "questions": "Please comment on the assumptions/design choices (see above), and on the novelty of the method.", "limitations": "Limitations are described adequately.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The presentation of the problem and the method is mostly clear, although some design choices are presented without much motivation, and seem somewhat problematic. Specifically:\n- why use only SNP positions in determining that reads are overlapping (line 156 and 174)? Why not use positions in which nucleotides are the same (non-SNP positions?). E.g. if two 200bp reads overlap on 100 bases, but are from a region (e.g. a highly conserved, essential gene) that contains very few SNPs (below $p$ SNPs), why are they not considered overlapping?\n- In lines 155, one reads “any two reads (…) must be (…) non-overlapping, consistent, conflict. But Consistent is defined as 0 differences in SNPs, Conflict as $\\geq q$ differences in SNPs, then two overlapping reads with e.g. $q-1$ differing SNPs are neither Consistent nor Conflicting.\n- the requirement that “any two conflicting reads have two different colors and any two consistent reads have the same color” (line 185) seems too strong. What about e.g. three quasispecies GGGGAA, AACCTT, AACCGG and a set of 3 reads AACC CCTT CCGG, p=2, q=2? All three reads are overlapping, and 1 is consistent with 2 & 3, but 2 & 3 are in conflict.\n\nThe paper involves a GNN message passing approach for solving the problem of assigning reads to quasispecies (colors), modeled as minimizing the loss (eq. 3) composed of two terms involving inner products of color assignments $p_i$ for vertices $i$: the “consistent” term that is the sum of $-\\log( <p_i, p_j> )$ over all pairs $(i,j)$ linked by consistent edge, and the “conflict” term that is the sum of $-log ( 1 - <p_i, p_j> )$ over all pairs $(i,j)$ linked by conflict edge. This is a straightforward extension of cited prior work that only used one edge type and had a single term. Thus, the novelty of the approach on the GNN side is limited.\n\nFinally, the toy example in Figure 2 seems too simple: judging from it, the problem can be solved by finding connected components in the graph with only blue (Consistent) edges taken into account.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FVPpNKlzRe", "reviewer": "Reviewer_Exv5", "summary": "The authors propose a new method for haplotype reconstruction in polyploid species and viral quasispecies. Their approach relies on graph message passing neural network.", "questions": "I see how Eqn. 3 is a relaxation of the constraints in Eqn. 2, but how exactly does the objective (the Hamming distance) come in? Could you provide a proof/derivation of Eqn. 3 from Eqn. 2?\n\nLine 94 typo: ployploid -> polyploid\nLine 287 typo: quasiqpecies -> quasispecies\nTable 3: title says 3 viral quasispecies datasets, but 10 datasets are listed\nWhere are the colors from in Figure 3? (i.e. what’s the reference haplotype assignment?)", "limitations": "Although these are not problems unique to this method, I think the method’s inability to take into account statistical uncertainty, and inability to automatically discover the number of haplotypes (as may be necessary in studying viral quasispecies) are important limitations that should be discussed and addressed going forward.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper offers a clear and careful explanation of the problem, and an original solution. The performance gains over previous methods are substantial, suggesting the method could likely have significant impact on biological practice.\n\nA weakness of the method is that the problem is not set up using an explicit generative model, with a clear description of the estimand and noise. This makes it difficult to understand the statistical properties of the estimation problem the authors are trying to solve. Instead, an objective is simply assumed (though I understand it is a standard objective in the field). Perhaps even more importantly, this also prevents connections to the broader ML/statistics literature, and in particular prevents application/comparison to well-studied methods for clustering vectors of discrete data, with entries missing at random (an alternative view of the haplotype reconstruction problem). ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept