Encoding Unitig-level Assembly Graphs with Heterophilous Constraints for Metagenomic Contigs Binning
Authors: Hansheng Xue
Vijini Mallawaarachchi
Lexing Xie
Vaibhav Rajan
Venue: ICLR 2024 poster (2024)
Keywords: Metagenomics Binning
Computational Genomics
Graph Neural Networks
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)

Abstract: Metagenomics studies genomic material derived from mixed microbial communities in diverse environments, holding considerable significance for both human health and environmental sustainability. Metagenomic binning refers to the clustering of genomic subsequences obtained from high-throughput DNA sequencing into distinct bins, each representing a constituent organism within the community. Mainstream binning methods primarily rely on sequence features such as composition and abundance, making them unable to effectively handle sequences shorter than 1,000 bp and inherent noise within sequences. Several binning tools have emerged, aiming to enhance binning outcomes by using the assembly graph generated by assemblers, which encodes valuable overlapping information among genomic sequences. However, existing assembly graph-based binners mainly focus on simplified contig-level assembly graphs that are recreated from assembler’s original graphs, unitig-level assembly graphs. The simplification reduces the resolution of the connectivity information in original graphs. In this paper, we design a novel binning tool named UnitigBin, which leverages representation learning on unitig-level assembly graphs while adhering to heterophilious constraints imposed by single-copy marker genes, ensuring that constrained contigs cannot be grouped together. Extensive experiments conducted on synthetic and real datasets demonstrate that UnitigBin significantly surpasses state-of-the-art binning tools.

Published as a conference paper at ICLR 2024
ENCODING UNITIG-LEVEL ASSEMBLY GRAPHS WITH HETEROPHILOUS CONSTRAINTS FOR METAGENOMIC CONTIGS BINNING
Hansheng Xue Vijini Mallawaarachchi' Lexing Xie', Vaibhav Rajan
'ccooo of Computing, Australian National University, Canberra, Australia School of Computing, National University of Singapore, Singapore *College of Science and Engineering, Flinders University, Adelaide, Australia [hansheng. xue, lexing..n..... xie/@ane edu, au, vaibhav ra jan@nus edu. sq vi rijini..e mww.awaarachhhhaaaaaaaaaaaaaaaae wendeeerfiiiniiiieieeeemmeirrrre .n.....ed...................
ABSTRACT
Metagenomics studies genomic material derived from mixed microbial commu- nities in diverse environments, holding considerable significance for both human health and environmental sustainability. Metagenomic binning refers to the clus- tering of genomic subsequences obtained from high-throughput DNA sequencing into distinct bins, each representing a constituent organism within the commu- nity. Mainstream binning methods primarily rely on sequence features such as composition and abundance, making them unable to effectively handle sequences shorter than 1,000 bp and inherent noise within sequences. Several binning tools have emerged, aiming to enhance binning outcomes by using the assembly graph generated by assemblers, which encodes valuable overlapping information among genomic sequences. However, existing assembly graph-based binners mainly fo- cus on simplified contig-level assembly graphs that are recreated from assembler's original graphs, unitig-level assembly graphs. The simplification reduces the res- olution of the connectivity information original graphs. In this paper, we design novel binning tool named UNITIGBIN, which leverages representation learning on unitig-level assembly graphs while adhering to heterophilous constraints im- posed by single-copy marker genes, ensuring that constrained contigs cannot be grouped together. Extensive experiments conducted on synthetic and real datasets demonstrate that BNITIGBIN significantly surpasses Wate-of-the-art binning tools.
INTRODUCTION
Metagenomics involves the analysis of genetic materials originating from mixed microbial commu- nities present in various environments (Kaeberlein et al.) 2002). It offers a suite of tools rooted in genome sequencing to address crucial questions related human health and environmental sustain-
ability. As an illustration, the Human Microbiome Project (Tumbaugh et al. 2007) uses metage- nomic analysis techniques acquire valuable insights into the intricate microbial communities siding in human body. This effort also aids in identifying microbial species associated with various diseases present in the human gut (Nayfach et al. 2019). In standard metagenomic analysis work- flow, genetic materials are gathered from the microbial community and then processed through a sequencing platform generate DNA sequences commonly referred to as reads. Since these genetic materials are mixed together, it's uncertain which species each read belongs to. A core challenge in downstream analysis is to determine the species present within the input sample by examining these reads. However, these reads are too short for direct analysis. Many metagenomic techniques use as- sembly graphs to assemble these short reads into longer DNA sequences known as unitigs. Contigs are then formed by combining one multiple connected unitigs (Xiang et al.) 2023). In an assembly graph, each vertex corresponds to a unitig, and each edge represents the overlapping relationships between two unitigs (Nurk et al. 2017 Kolmogorov et al. 2020). Contigs are represented as either
"Corresponding author.

---

Published as a conference paper at ICLR 2024
single vertex or path comprising several vertices within the assembly graph. Contigs binning refers to the clustering of these contigs into distinct bins corresponding to constituent genomes.
Many existing metagenomic binning tools rely statistical information extracted from contigs themselves, including nucleotide composition and abundance features (Breitwieser et al. 2019] Yue et al., 2020). These tools do not take into account the homophily information within the sembly graph (Barnum et al. 2018). which suggests that sequences connected to each other in the assembly graph are more likely to belong the same species. In addition, inherent noise within sequences presents additional challenges for these sequence feature-based binning meth- ods. Several binning tools have been developed recently to leverage assembly graphs, including GraphBin (Mallawaarachhhi et al.) (020) and GraphMB (Lamurias et al. (022). However, instead of directly using unitig-level assembly graphs produced by the assembler, they simplify original graphs and re-construct contig-level assembly graphs, where vertices represent contigs and edges represent their overlaps. However, the simplification reduces the resolution of the connectivity in- formation in unitig-level assembly graphs and may introduce erroncous edges (Xiang et al. (023) Moreover, many existing binning tools face difficulties and exhibit low recall values when handling short sequences, often shorter than 1,000 bp, which are commonly excluded from analysis.
Additional biological information, such as single-copy marker genes, can also be exploited to im- prove binning results (Albertsen et al., 2013 Dupont et al. 2012). Single-copy marker genes are genes that occur only once in each species. two contigs share the same single-copy marker gene, it highly likely that they belong to different species. Some binning tools have utilized this additional information from single-copy marker genes to estimate the initial number of bins or enhance the quality of contig binning results (Mallawaarachchi & Lin 2022: Lamurias al. 2023). However, there are limited graph neural network models that can be directly employed to model the unitig-level assembly graph with heterophilous relationships. Moreover, dealing with the large-scale character- istics of unitig-level assembly graphs in real metagenomic data poses significant challenges for the learning process. this paper. we develop a graph neural network framework designed to model the unitig-level assembly graph while also adhering to heterophilous constraints imposed by single-copy marker genes, called UNITIGBIN. The contributions of this paper are listed as follows:
To the best of knowledge, this is the first use of graph neural networks to model the unitig-level assembly graph in the field of metagenomic contig binning.
We devise novel model for constraint- graph learning, UNITIGBIN-Learning which captures the unitig-level assembly graph with constraints by employing a diffusive convo- lution and optimizing triplet constraints. A p-batch strategy is designed for parallclization.
We devise novel UNITIGBIN-Binning framework that leverages a Matching algorithm to initialize markered contigs, uses Propagating labels to annotate unmarked contigs mean- while satisfying constraints, and employs a local refining strategy to fine-tune final binning.
Extensive experiments on synthetic and real datasets show that UNITIGBIN significantly outperforms sfate-of-the-art binners in terms of binning purity and completeness, regardless of whether graphs are from standard metagenomic assemblers, metaSPAdes and metaFlye.
2 RELATED WORK
Contigs binners. Despite contigs being assembled from short reads using assembly graphs, the majority of existing binners overlook the homophily information present in these assembly graphs. Instead, these binning tools rely on composition (normalized oligonucleotide, i.e. short strings of length k. frequencies) and coverage (average number of reads aligning to each position of the con- tig) information to perform contig binning. For example, MetaWatt (Strous et al.) 2012) leverages multivariate statistics and Markov models to bin contigs. CONCOCT (AIneberg & et al. 2014) combines the variational Bayesian model selection and Gaussian mixture model to cluster contigs into bins. MaxBin2 (Wu et al. (2016) designs an composition and coverage information to iteratively bin the contigs. BusyBeeWeb (Laczny et al.) 2017) is web application that uses a bootstrapped supervised binning approach for contig binning. MetaBAT2 (Kang et al. (019) is a graph partitioning approach that uses contigs' composition to con- struct the graph. SolidBin (Wang et al. 2019) uses a supervisd spectral clustering algorithm combined with additional biological knowledge. MetaBinner (Wang et al. 2023) is an ensemble binning tool that integrate various types of features. In addition, several binning tools have been
catittiiammaiiizziiiinn algorithm that uses both
2

---

Published as a conference paper at ICLR 2024
Unitig-level assembly graph
Learning
Matching
Propagoting ting
Refining
He Hatarophi constraints
Ceetiguk:
Contig-t:
Representations
Figure 1: The framework of UNITIGBIN consists of Learning, Matching, Propagating, and Refining-
developed to enhance performance using deep learning techniques. For instance, VAMB Nissen et al. 2021) uses deep variational autoencoders to learn both composition and coverage informa- tion. CLMB (Zhang et al. 2022) employs deep contrastive learning techniques to produce robust results even from noisy data. SemiBin (Pan et al. (022) designs semi-supervised Siamese neu- ral network incorporating must-link and cannot-link constraints obtained from reference genomes. These binning tools do not utilize assembly graphs and often omit short contigs because composition and coverage features are less reliable for short contigs, leading to lower recall values.
Assembly graph improves binning. To enhance the binning outcomes, recent bin-refinement meth- ods (Mallavaarachchi et al. 2020) have introduced the utilization of assembly graphs. However, these bin-refinement tools are not independent and require the initial binning results from existing binners as a starting point. MetaCoAG (Mallawaarachchi & Lin (022) is standalone binning tool capable of integrating composition, abundance, and assembly graph information to enhance bin- ning performance. In addition, several methods have been developed to use graph neural networks to model the assembly graph. For instance, GraphMB (Lamurias et al. 2022) uses a variational autoencoder model to encode both composition and abundance and then feeds these features into graph neural networks for contigs binning. This approach does not incorporate additional infor- mation like heterophilous constraints from single-copy marker genes. RepBin (Xue al. (022) designs a self-supervised graph learning framework for modeling assembly graphs while encoding prior constraints. Then, semi-supervised label propagation model is employed for contig binning- CCVAE (Lamurias et al. (203) develops a variational autoencoder to simultaneously learn the as- sembly graph and the information of single-copy marker genes and then uses a clustering algorithm for contig binning. A common limitation of these bashh binning tools is their applicability solely contig-level assembly graphs, which are generated from the unitig-level assembly graph using specific strategies. The transition from unitig-level to contig- reduces the resolution of connectivity information in the original graph and may introduce errors due to the chosen strategy.
3 METHODOLOGY
Preliminaries. Given a unitig-level assembly graph The output embedding for unitigs and contigs in the graph are d-dimensional vectors Z E R and 2 E RlPixd, and contigs binning results are denoted as B=(b, E RR, i }.), where K de- notes the number of bins. In the assembly graph G, V is the nodes unitigs set, E=( uy)| vy V} denotes edges indicating the overlap between unitigs, (=((pr..........u U...).... 2/ Up E V} cor- responds to the paths or contigs within the graph, and X= V} are features associated with nodes. Heterophilous constraints from the single-copy marker genes are C=((P;..... .... P;)...,).. lP:. Pj E P). The objective of binning metagenomic contigs is to assign a label b, E B to each contig ps P.
along with its constraints C.
Preprocessing. The heterophilous constraints C are created by employing the FragGeneScan (Rho) al., 2010) and HMMER (Eddy) 201T) tools to detect contigs containing single-copy marker genes, following similar approach as Max (Wu et al. 2016) and MetaCoAG (Mallawaarachchi & Lin 2022 When contigs belong to the same constraint set, it implies that these contigs should not be grouped together in pairs within the bins. The unitig-level assembly graphs constructed from two widely used assemblers: MetaSPAdes (Nurk et al. 2017) and metaFlye (Kolmogorov et al. (020).
Prior to modeling the assembly graph and clustering contigs, we initially perform preprocessing op- erations based on known knowledge (unitig-level assembly graph & and heterophilous constraints C). Two operators are introduced in UNITIGBIN, i) Graph disentangling and ii) Contigs sampling. Graph disentangling is designed to separate contigs within the unitig-leve assembly graph. For ex- ample, when constraints suggest that contig A and contig B should belong to distinct bins, yet these
3

---

Published as a conference paper at ICLR 2024
two contigs share overlapping unitig in the assembly graph (as shown in Figure DT. create new unitig by duplicating the original unitig 5 to disentangle the assembly graph. Contigs sampling is devised to create positive relationships among contigs by leveraging the inherent structure of the assembly graph. Different from conversion strategies used in GraphBin and GraphMB to construct contig-level assembly graphs. Here, focus on determining whether two paths are directly con- nected or linked by only single hop (Miller et al. 2010); in this case, we establish a positive edge between these contigs. The sampled positive contigs set is represented O {(pi. Pj PP)) P).
Overview. UNITIGBIN consists of two main components: Learning, which uses a graph neural network model the unitig-level assembly graph while adhering to constraints, and Binning, a contig-leve framework. In the Binning stage, a Matching algorithm is employed to initialize mark- ered contigs, Propagating labels are used to annotate unmarked contigs while satisfying constraints, and local Refining strategy is incorporated to fine-tune binning assignments (refer to Figure I.
3.1 Learning: REPRESENTING UNITIG-LEVEL ASSEMBLY GRAPH WITH CONSTRAINTS
The UNITIGBIN- model aims obtain latent representations for both unitigs/nodes Z and contigs/paths 2 considering both unitig-level assembly graph 9 and heterophilous constraints C. In this section, we will introduce the Learning framework in three components, a) Diffusion encoder- decoder framework. b) Triplet Gaussian constraints optimization, and c) p-Batch parallclization.
3.1.1 DIFFUSION
DECODER FRAMEWORK
An encoder-decoder architecture is adopted as the foundational learn- ing framework in Learning, which comprises two primary components: a graph diffusive convolution en- coder (Klicpera et al., 2019) and an inner-product decoder. The dif- fusive encoder captures the graph's s topology and initial node features, while the inner-product decoder re- constructs the graph's 's structure using learned features from the diffusive encoder. Minimizing the reconstruction loss, which measures the dissimilarity between the original and reconstructed graph, allows to obtain the node embeddings.
Contigs Roprosentotions
Loss for Batches
Graph
batch
batch
O positive
Constroints
Loss for Constraints
Unitigs Representations
fragment
negative
Loss for Reconstruction
Figure 2: The framework of the UNITIGBIN-Learnnng
Encoder-Decoder. In Learning, a variational autoencoder (Kingma & Welling 2013) is estab- lished. A denotes the adjacency matrix of a unitig-level assembly graph with self self-loops (A=A+IN, IN is the unit matrix), D stands for its diagonal degree matrix, i.e., Di= Aij. We use DIF- FCONV symbolize the diffusive convolution. Then, the diffusive encoder can be formulated as: [ -)=[[= 1=1
((2,]X, A). with q(2; X, ()=xA,))=4 (=: jus, diag(af)), where y=DIFFCONV, (H, A), log DDD=D CONV, H, A), and H=DIFFCONV(X A). The inner-product decoder is calculated as p(A 2 -I N II p( (1g zi, Zy), with p( (A, ) =Sigmoid 2z). The object follows:
Lg B (y log p( Á|z) - K (T Z A)][p(Z)),
where pl 2 +(=+==+++..))) W22, 0. I) is a Gaussian prior. A weighted cross entropy loss (Kipf & Welling 2016 is used in Equation to measure the reconstruction error between A and Å. K KL(-) is the divergence function to measure the similarity between the distribution X( and p(Z).
Diffusive convolution. Following RepBin (Xue al., 2022), we also the PageRank- -bssd diffusion (Page et al. 1999) to model the unitig-level assembly graph. To provide a brief explana- tion, when considering node i with vectorial feature x;, the iterative calculation of its diffusive feature follows the equation (PR(z))=(1-o)AAP))) transitioning different state. The transitions state for node can be computed as PPR (<rq ( A)-a)A)-2 --g.. Tg. The diffusive convolution and layer-wise propagation rule can be formulated as:
+aI,, where a E (0, 1] is the probability of
H --1 o (DiFFCONV H'e'), DIFFCONV = a[Ix - (1 a)D -)D- 1/ AD -1/2-1
(2)
where (.) denotes a non-lineat activation function, and el E IR V| is a l-layer trainable transfor- mation matrix, d, is the embeddings dimension in the 1-layer, and ===X. By optimizing the object
4

---

Published as a conference paper at ICLR 2024
in Equation| 1
latent embeddings for unitigs be obtained, Z E R Rilxd A readout function can be used generate features for contigs, Z=R(Z), with 2,= Dvep, Zv, and 2 E R P
3.1.2 TRIPLET GAUSSIAN CONSTRAINTS OPTIMIZATION
In constraints C, each set signifies that certain contigs contain the identical marker gene and these contigs must not be grouped pairwise into the same bin. In Learning, we convert contig- constraints C into the pairwise contig-constraints set C' and pairwise unitig-constraits set M'.. In each pairwise constraint (i.j) .M', it indicates that unitig i and j must not be assigned to the same bin. We treat these pairwise constraints as negative samples, whereas we sample existing edges in the graph positive samples. In detail, for every pairwise constraint (i,j) MM,, sample node i's neighbors, N₁. as positive edges. Sampled triplet constraints can be defined as M. i, V E N.). To integrate Gaussian distributions and triplet constraints, draw inspiration from (Bojchevski & Günnemann, 2018) and incorporate measuring and ranking strategies. Within the decoder framework, the Gaussian embeddings in hidden layers can be acquired as follows: z==N (uu,)) E,) with >. =diag(elu(log) o; ++)),, μ4 E I E, E Rdxd, where D=DIFFCONV, ( A) and log G=DIIFCONV,
A). The KL divergence-based dissimilar- ity measurement (He et al. 2015) between two Gaussian embeddings and 2j can be represented as 2 ([) [ E, EE)+ m1 Σ m4)) d do [ where Ir(-) and denote the trace and determinant a matrix respectively. Each triplet constraint (i.j.k) k) M signifies that unitig i and must not be in the same bins, and there is a high probability that nodes and & should belong to the same bin. In other words, node more closely related h com- pared to node j. We formulate the triplet constraints ranking strategy as A(z,, =x) < A(zi, Zz). The square-exponential loss (LeCun et al. 2006) used to measure the triplet constraints ranking as:
C.
Σ
(DRINN)))) + exp DKa--DK
(LJ.EJMM
Algorithm 1: The Unitig-level Assembly Graph Learning Algorithm UNITIGBIN-Learnin
Data: Unitig-level assembly graph G; constraints C; dimension of embedding d; number of graph batches nı;
Result: Embedding for unitigs Z and contigs 2.
G,O + Preprocess(G, C) // Graph untangling and Contigs sampling M < Sample(G. C) Sample triplet unitig constraints
Batches + p-Batch((O,n) // Split batches
for e E epochs do
for b E Batches do
H₂ < -AIFFCONY(AA,X)) Base diffusive convolution
14b. log g DIFFCONV, (H,, DIF, As) //Gaussian embeddi ng
Lyp < Equation
// Compute loss for graph reconstruction
end
Lg Lyb //Accmuulate the batch losses
Le t Equation 3, Lb +- DRL. // compute the cmstraints batch loss 11
12
L E + Cu + A1 Le Compute loss in Equation
13 end
Z +
// Unitigs Embedding
15 7 R(Z) // Contigs Embedding
3.1.3 P-BATCH: TRAINING DATA BATCHING
Training GNNs on unitig-level assembly graphs from real metagenomic data, which can reach mil- lions in size, presents significant computational challenges. Creating training batches presents challenge as must satisfy two criteria: i) processing each contig in parallel while preserving its completeness, and ii) grouping diverse contigs with positive relationships into the same batch to tain this valuable information. To address these hurdles, we introduce a graph splitting and training module named p-Batch, which systematically selects independent sets of nodes from the Positive- contig Graph which derived from the positive contigs set in an iterative manner. The p- p-Batch module takes each path the minimum splitting unit and functions iteratively through two steps:
5

---

Published as a conference paper at ICLR 2024
selecting the largest contigs sets from the candidates, and ii) feeding them into the smallest batch. The p-Batch will continue until all candidate contigs are fed into one batch. In practice, there are still some unitigs that are fed into different batches. We design a loss function to minimize the prob- ability distribution of these jointly nodes. The objective function for the p-Batch loss function can be calculated as La Eojje DRI(N)l/M)) where Q is the set of joint-unitigs pairs.
Objective function. The object of Learning is determined by combination of Cy. Le. and Ls, with A regulating the significance of constraints loss. Refer Algorithm 1 for pseudocode of Learning.
C = Lg + Lo + A1 Le
(4)
3.2 Binning: COMPRISING MATCHING CONSTRAINTS, PROPAGATING AND REFINING BINS
Matching. After obtaining the embeddings of contigs in the Learning step. you can directly apply existing clustering algorithms (such as K-Means) for contigs binning. However, dealing with imbal- anced bin sizes adds complexity to the contigs binning process. RepBin (Xue et al. 2022) proposes a semi-supervised label propagation model using constrained contigs as initial labels. However, RepBin runs K-Means on embeddings of large number of constrained contigs to initialize labels, which can be computationally expensive. The lack of known number of bins is another challenge.
In UNITIGBIN, we devised simple yet efficient matching algorithm for attaining optimal binning initialization. Matching mainly consists of two key steps: i) Binning Initialization and ii) Iterative Matching. Initially, we arrange constraints in C in descending order based on their length, selecting the largest set as the initial bin. We then perform iterative calculations to determine the similarity between matched bins and candidate contigs. A greedy method is used to select the maximum value for matching operations. In the matching process, we incorporate threshold value denoted as T. If the similarity between a bin and a contig is above T, we add this contig to the bin. Instead, we opt to create new bin that includes this contig. Refer to Algorithm 2 in Appendix A.1 for the pseudocode.
Propagating, From the preceding Learning and Matching phases, we obtain embeddings of unitigs denoted as Z E RIVIxd and initial labels assigned to constrained contigs represented by Ye E K We follow RepBin and design contig-level label propagation model instead of running K-Means algorithm directly. Besides, we also introduce a penalty function to maximize constraint satisfaction.
Propagating consists of three parts: graph convolution, readout function, and fully connected layer. Graph convolution learns both the unitig-level assembly graph and unitigs features from Learning, which can be described as 74+1=a (CONV. Z'O"), where CoNv=n-1/2 AAN= 1122 The embeddings of contigs can be obtained through the readout function, (ZR(Z), 2 E R!P Then, the binning probability can be represented as Y Y=Softmax(2W + +). Y E glM* where K is the number of bins. A cross-entropy function used to optimize the binning results. However, the binning assignment may violate prior constraints. To maximize constraint satisfaction, we introduce an optimization function. Given K bins, we use a 0/1 matrix R for incorporating constraints. The constraint matrix Iy denotes the binary conflict relationships among K bins, i.e., Iy (i,j)=1 if i * and 0 otherwise, for any i {1,... K}. The bin-assignment matrix Y E IR |P X is matrix that represents the bin assignment probability (over K bins) for each contig i in its corresponding row Y,. For any constraint (i, E C', aim to assign different bins to i and and thus maximize the sum of joint-pron probbbbibbiisss with different bins, i.e., Y, The objective function is as follows:
K
L f=
Yu In Zia A2
Σ (L.))C
log( (e(YTI+Y))
(5)
C"
L=Y
Refining. In Refining, our primary goal is to explore potential binning assignments for contigs, taking into account heterophilous constraints. This step primarily consists of two components: i) Splitting and ii) Merging. Splitting aims to divide existing bins into multiple sub-bins when identical marker genes are present within the bin. Merging is intended to combine sub-bins into a larger bin when these sub-bins do not share the same marker genes. Refer to Appendix A. for the pseudocode.
EXPERIMENTS
Datasets and Baselines. We evaluate UNITIGBIN model on 12 datasets, consisting of assembled by metaSPAdes v3.15.2 (Nurk et al., 2017) and 6 assembled by metaFlye v2.9 (Kolmogorov al.,

---

Published as a conference paper at ICLR 2024
Table 1: CheckM results for the number of HQ bins by UNITIGBIN and baselines.
Methods
Sim20G
Sim50G
Sim100G
Sharon
DeepHPM
COPD
MetaBAT2
16
2
0
0
MaxBin2
35
6
8
9
Semi Bin
18
38
68
5
VAMB
18
31
51
5
2
6
GraphMB
13
18
2
CCVAF
12
15
28
2
RepBin
18
15
1
0
MetaCOAG
17
34
69
7
8
17
UNITIGBIN
43
7
12
21
A% MaxBin2
0%
18.6%
28.9%
14.3%
33.3%
57.1%
A % SemiBin/VAMB
10%
11.6%
10.5%
28.6%
83.3%
71.4%
4% MetaCoAG
15%
20.9%
9.2%
0%
33.3%
19.0%
2020). In metaSPAdes-assemblle datasets, Sim20G, Sim50G, and Sim1000 are three datasets col- lected from GraphBin2 (Mallawaarachchi al. 202T) and MetaCoAG (Mallawaarachchi & Ling 2022). In metaaFyyeasssmmile datasets, 6 real-world Wastewater Treatment Plant (WWTP) datasets are collected (Singleton al. 2021). Table A1 provides a comprehensive overview of the dataset statistics. UNITIGBIN is evaluated against three categories of binning tools: 2 traditional ap- proaches, MaxBin 2.0 (Wu et al. 2016) and MetaBAT2 (Kang et al.] 2019): ; b) deep learning-
based binning tools, SemiBin (Pan al. (022) and VAMB (Nissen et al. 202T): : c) assembly
graph-based binning models, GraphMB (Lamurias et al. 2022), RepBin (Xue et al. 2022). Meta-
CoAG Malllaaaaachhhii & Lin 2022), and CCVAE [Lamurias et al. (023).
Metrics and Experimental Settings. We use the popular CheckM v.. (Parks et al. 2015) tool evaluate the binning results of UNITIGBIN and baselines. CheckM assesses bin quality through sets of single-copy marker genes and without using ground truth. We use CheckM to assess the completeness and contamination of the bins generated by each tool. For metaSPAdes datasets, we adhere to the experimental setup outlined in MetaCoAG (Mallawaarachhhi & Lin 2022). We define precision as 1/(1 + contamination) and recall as completeness. High-quality (HQ) bins are char- acterized by precision > 90 and recall > 80. Medium-quality (MQ) bins have precision > 80 and recall 50, while the remaining bins are classified as Low-quality (LQ) bins. For metaFlye datasets, follow the experimental setup used in GraphMB (Lamurias et al., 2022 and CCVAE (Lamurias) jet al. 2023), which employs two specific criteria: completeness > 90 & contamination < 5, and completeness > 50 & contamination
10, to assess the quality of bins. We also AMBER v2.0.2 (Meyer et al., 2018)) tool and calculate the Precision, Recall, F1, Adjusted Rand Index (ARI) metrics Xue et 2022) evaluate simulated datasets using ground truth.
4.1 EVALUATION ON METASPADES-BAN DATASETS
Table shows that UNITIGBIN significantly outperforms state-of-the-art baselines, achieving the highest number of high-quality bins as evaluated by CheckM. Sim100G, UNITIGBIN yields 76 high-quality bins, approximately 9.2% more than the highest number obtained by baselines (69 for MetaCoAG), In COPD, UNITIGBIN also attains the highest number of high-quality (HQ) bins, with 21 HQ bins, which is considerably greater than the second-highest number of HQ bins obtained by MetaCoAG (17). This substantial gap between UNITIGBIN and baselines underscores the su- perior performance our model in contig binning. The CheckM results for medium-quality (MQ) bins generated by UNITIGBIN and baselines can be found in Table A3 UNITIGBIN consistently outperforms other methods by achieving the highest number of HQ+MQ bins across most datasets.
In three simulated datasets, we also employ the AMBER tool and calculate the Precision, Recall, Fl, and ARI scores to assess the performance of both UNITIGBIN and baselines. Here we take Sim20G an example, Figure denotes the Average Completeness (AC) and Average Purity (AP) at the nucleotide level, while Table 2 presents the and ARI score (with 'bp' representing the nucleotide-level and 'seq' representing the sequence-level), and the number of HQ bins. Com- parison with baselines demonstrates that UNITIGBIN achieves the highest level of performance. In particular, UNITIGBIN is capable of binning not only long contigs but also those shorter than

---

Published as a conference paper at ICLR 2024
1,000 bp, which are typically discarded by other binning tools. For instance, UNITIGBIN achieves a sequence-level Fl score of 0.952, which significantly higher than the second- highest FI score obtained by MaxBin2, 0.632. The calculated Precision, Recall, FI, and ARI scores shown in Table A2
Table 2: FI(%), ARI(%), and HQ metrics on the Sim20G.
Average Completenese (9)
Semiiing
HoxB Unfigüin
Reptin
Methods
(l
(l
ARl(pp)
ARl(seg)
HQt
WAMD
UntiiBii
GraphMD
MetaBAT2
61.0
30.1
39.2
21.6
MetaCorG
60-
MaxBin2
99.0
63.2
99.0
77.5
20
RcoBin
SeriBinn
MataBATZ
SemiBin
98.4
53.7
98.1
41.7
19
MetaCoAG
Grap
VAMB
VAMB
97.5
59.1
97.9
96.7
GraphMB
94.2
58.3
55.9
34.4
10
20-
MetaBATZ
CCVAE
97.8
61.3
79.1
46.8
13
RepBin
96.6
44.8
96.3
14.2
16
60
Average Purity (96)
80
90
100
MctaCoAG
95.3
58.9
99.1
78.7
UNITIGBIN
98.7
95.2
99.3
97.4
20
Figure 3; AC and AP for Sim20G.
4.2
EVALUATION ON METAFLYE-BASHE DATASETS
We also benchmark UNITIGBIN and baselines six real datasets assembled using metaFlye. We use the CheckM tool and count the number of bins that meet two criteria (following CCVAE): A)
completeness>>00 & Contamination<55, and B) completeness>50 & Contamination 10. Figure clearly shows that UNITIGBIN outperforms baselines across all six datasets. UNITIGBIN produces total of 1,775 bins that meet the criteria In contrast, the highest count achieved by baselines is 962 bins, which is 45.8% less than the number of bins obtained by UNITIGBIN. Notably, CCVAE uses CheckM to detect single-copy marker genes within contigs and extract heterophilous constraints. Moreover, CCVAE also employs CheckM to evaluate binning results. To eliminate potential am- biguity, we follow the pipeline of MaxBin2 and MetaCoAG, using FragGeneScan and HMMER to identify contigs containing marker genes. We also present results for UNITIGBIN using constraints extracted from CheckM, which are detailed in Figure AT In summary, UNITIGBIN consistently demonstrates superior performance across datasets assembled by both metaSPAdes and metaFlye.
Domh
Undigttin
OOVAS
205
190
100
GreonMi
232
43
191
181
MesazAta
VAUS
28
152
131
151
Semiin
23
14
Marbi
MasCaAG
Repfin
36
420
430
Man
Viby
Mjor
Untiigtin
5:5
230
222
178
Grapndi
209
75
MetaRA72
19
144
130
96
VAMS
BenBin
Marbbo
20
61
MAGDOAG
RepBin
Compntores Contume
200
130
230
300
200
150
200
100
200
Figure 4: CheckM results of UNITIGBIN and baselines on 6 real datasets assembled using metaFlye.
4.3 VISUALIZATION AND EXPERIMENTAL ANALYSIS
Visualization. To gain deeper insights into the binning results, we employ the python-igraph pack- age to visualize the unitig-level assembly graph of Sim alongside the ground truth and binning results obtained from various binning tools (selected ten representative bins, see Figure 5p. Nodes represent unitigs, while edges indicate overlapping relationships between distinct unitigs. Distinct colors represent different species or bins. UNITIGBIN produces binning results that align well with the ground truth, whereas other baselines struggle with missing inaccurate labels.
8

---

Published as a conference paper at ICLR 2024
Nessaria mannaatkdo Smeptocooss themophiluu
Ensipelctvtt mhusoopthhite
Ricketrsa prosroei
Campyloaader jokuni
Odeerbatt splencrrios
Photoenauum profundum
GruundTruth
UnitigBin
MetaCoAG
SemiBin
MaxBin2
VAMB
Figure 5: Visualization of selected ten bins in Sim100C with ground truth and different binners.
Ablation study & Parameters analysis. To assess the effectiveness of our proposed model, we perform ablation study to investigate the individual algorithmic components within UNITIGBIN. Figure [6 illustrates that each component within UNITIGBIN contigs binning perfor-
contributes the improvement mance (more details in Appendix A.7). We also analyze the impact of parameters such dimension d. the transition prob- ability in diffusive convolution, the threshold T in Match- ing, the importance of constraints A loss function Eqn and the importance of constraints X2 in loss function Eqn Figures A3 show that UNITIGBIN displays relatively low sensitivity variations in the aforementioned parameters, As A₁ is raised, involving more importance constraints, the performance of UNITIGBIN increases and tends to stabilize.
80
11
21
71
76
43
60
61
10
32
20
MQ Bins
Learning w/o Refining
UnitigBin
Learning w/o
Learning w/o
Binning w/o
Figure 6: Results of UNITIGBIN and its variants on Sim100%
Training process & Running time. Figure A2 (a) and (b) show the training process of Learning and Propagating in UNITIGBIN respectively. As the number of training iterations increases, the proportion of vio- lated constraints decreases and more constraints of UNITIGBIN against selected baselines on Sim100G (refer to Figure (A] second-fastest deep learning-basse bbsed binning tool, with runtime of approximately 30 mins, beaten only by VAMB, which faster. It is significantly faster than other deep learning-basse baaedd methods.
satisfied. We also benchmark the running time
(c)). UNITIGBIN the
5 CONCLUSION
To model the unitig-level assembly graph directly output from metagenomic assemblers while in- corporating heterophilous constraints derived from single-copy marker genes, present novel binning tool called UNITIGBIN, a graph neural network model with constraint satisfaction designed for binning metagenomic contigs. UNITIGBIN comprises Learning, which uses a graph neural net- work model to learn the unitig-level assembly graph while adhering to constraints. It is followed by a contig Binning framework that employs an adapted Matching algorithm to initialize markered con- tigs, uses Propagating to annotate unmarked contigs while satisfying constraints, and incorporates local Refining strategy to fine-tune binning assignments. Extensive experiments conducted on both synthetic and real datasets show that UNITIGBIN outperforms existing binning tools significantly. The primary limitations of the model include its inability to label overlapping bins, where contigs belong to multiple species, and the difficulty of binning unmarked and short contigs. As future work, we plan to explore graph neural networks for binning short, unmarked contigs with multiple labels, and efficiently encoding large-scale unitig-level assembly graphs.

---

Published as a conference paper at ICLR 2024
REFERENCES
Mads Albertsen, Philip Hugenholtz, Adam Skarshewski, Kåre L Nielsen, Gene W Tyson, and Per H Nielsen. Genome sequences of rare, uncultured bacteria obtained by differential coverage binning of multiple metagenomes. Nature biotechnology, 31(6):533-538 2013.
Johannes Alneberg and al. Binning metagenomic contigs by coverage and composition. Nature methods, pp. 1 1144-1146, 2014.
Tyler P Barnum, Isracl A Figueroa, Charlotte I Carlström, Lauren N Lucas, Anna L Engelbrektson, and John D Coates. Genome-resolver metagenomics identifies genetic mobility, metabolic inter- actions, and unexpected diversity in perchlorate-reducing communities. The ISME journal, 12(6): 1568-1581, 2018.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In ICLR, 2018.
Florian P Breitwieser, Jennifer Lu, and Steven I. Salzberg. A review of methods and databases for metagenomic classification and assembly. Briefings bioinformatics, (114):1122-1111 2019.
Simon JS Cameron, Keir E Lewis, Sharon A Huws, Wanchang Lin, Matthew J Hegarty, Paul D Lewis, Luis AJ Mur, and Justin A Pachebat. Metagenomic sequencing of the chronic obstructive pulmonary disease upper bronchial tract microbiome reveals functional changes associated with disease severity. PLoS One, (2)):e0149005, 2016.
Alex Chklovski, Donovan Parks, Ben J Woodcroft, and Gene W Tyson. Checkm2: a rapid, scalable and accurate tool for assessing microbial genome quality using machine learning. Nature Methoods 20(8):1203-1212, 2023.
Chris L Dupont, Douglas B Rusch, Shibu Yooseph, Mary-Jane Lombardo, Alexander Richter, Ruben Valas, Mark Novotny, Joyclyn Yee-Greenbaum, Jeremy D Selengut, Dan H Haft, et al. Genomic insights to sar86, an abundant and uncultivated marine bacterial lineage. The ISME journal, (66):11661119) 2012.
Sean R Eddy. Accelerated profile HMM searches. PLoS computational biology, 7(10):e1002195, 2011.
Hadrien Gourlé, Oskar Karlsson-Lindsjj, Juliette Hayer, and Erik Bongcam-Rudloff. Simulating Illumina metagenomic data with InSilicoSeq. Bioinformatics, 35(3):521-522, 2019.
Shizhu He, Kang Liu, Guoliang Ji, and Jun Zhao. Learning to represent knowledge graphs with gaussian embedding. In CIKM, 2015.
Tammi Kaeberlein, Kim Lewis, and Slava S Epstein. Isolating" uncultivable" microorganisms in pure culture in simulated natural environment. Science, 296(5570): 127-11191 2002.
Dongwan D Kang, Feng Li, Edward Kirton, Ashleigh Thomas, Rob Egan, Hong An, and Zhong Wang. MetaBAT 2: an adaptive bimning algorithm for robust and efficient genome reconstruction from metagenome assemblies. Peer., 7:27359, 2019.
Diederik P Kingma and Max Welling. 1rX.v:1312.611,, 2013.
Auto-encoding variational bayes.
arXiv preprint
Thomas N Kipf and Max Welling. Variational Graph Auto-Encoders. In NeurIPS Workshop on Bayesian Deep Learning. 2016.
Johannes Klicpera, Stefan WeiBenberger, and Stephan Günnnemann. Diffusion Improves Graph Learning. In NeurIPS, 2019.
Mikhail Kolmogorov, Derek Bickhart, Bahar Behsaz, Alexey Gurevich, Mikhail Rayko, Sung Bong Shin, Kristen Kuhn, Jeffrey Yuan. Evgeny Polevikov, Timothy PL Smith, et al. metaFlye: scalable long-read metagenome assembly using repeat graphs. Nature Methods, 17 (11):1103-1110 2020.
10

---

Published as a conference paper at ICLR 2024
Cedric C. Laczny, Christina Kiefer, Valentina Galata, Tobias Fehlmann, Christina Backes, and An- dreas Keller. BusyBer Bee Web: metagenomic data amalysis by bootstrapped supervised binning and annotation. Nucleic Acids Research, pp. W171-W179, 2017.
Andre Lamurias, Mantas Sereika, Mads Albertsen, Katja Hose, and Thomas Dyhre Nielsen. Metage- nomic binning with assembly graph embeddings. Bioinformatics, (8(19):481-4488 2022.
Andre Lamurias, Alessandro Tibo, Katja Hose, Mads Albertsen, and Thomas Dyhre Nielsen. Metagenomic Binning using Connectivity-constaiie
Variational Autoencoders. In ICMI,, 2023.
Yann LeCun, Sumit Chopra, Raia Hadsell. M Ranzato, and Fujie Huang. A tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
Heng Li. Minimap2: pairwise alignment for nuclcotide sequences. Bioinformatics, 34(18)33094- 3100, 2018.
Cong-Cong Liu, Shan-Shan Dong, Jia-Bin Chen, Chen Wang, Pan Ning, Yan Guo, and Tie-Lin Yang. Metadecoder: novel method for clustering metagenomic contigs. Microbiome, 10(1): 1-16, 2022.
Jason Lloyd-Price Anup Mahurkar, Gholamali Rahnavard, Jonathan Crabtree, Joshua Orvis, A Brantley Hall, Arthur Brady, Heather H Creasy, Carrie McCracken, Michelle G Giglio, et al. Strains, functions and dynamics in the expanded Human Microbiome Project. Nature, 550(7674)): 61-66, 2017.
Vijini Mallawaarachchi and Yu Lin. Accurate binning of metagenomic contigs using composition, coverage, and assembly graphs. Journal of Computational Biology, 29(12):1337-1337 2022.
Vijini Mallawaarachchi, Anuradha Wickramarachchi, and Yu Lin. GraphBin: refined binning of metagenomic contigs using assembly graphs. Bioinformatics, 36(11):333))))) 36(11)333073313 2020.
Vijini G. Mallawaarachchi, Anuradha S. Wickramarachchi, and Yu Lin. Improving metagenomic binning results with overlapped bins using assembly graphs. Algorithms for Molecular Biology, 16(1):3, 2021.
Fernando Meyer, Peter Hofmann, Peter Belmann, Ruben Garrido-Oter, Adrian Fritz, Alexander Sczyrba, and Alice C McHardy, AMBER: assessment of metagenome BinnERs. Gigascience, (6):giy069, 2018
Fernando Meyer, Adrian Fritz, Zhi-Luo Deng, David Koslicki, Till Robin Lesker, Alexey Gurevich, Gary Robertson, Mohammed Alser, Dmitry Antipov, Francesco Beghini, al. Critical assessment of metagenome interpretation: the second round of challenges. Nature methods, 19(4):429-440, 2022.
Jason R Miller, Sergey Koren, and Granger Sutton. Assembly algorithms for next-generation se- quencing data. Genomics, 95(6):315-33 337-27, 2010.
Stephen Nayfach, Zhou Jason Shi, Rekha Seshadri, Katherine S Pollard, and Nikos C Kyrpides. New insights from uncultivated genomes of the global human gut microbiome. Nature, 568 (7753):505-510 2019.
Jakob Nybo Nissen, Joachim Johansen, Rosa Lundbye Allesée, Casper Kaae Sønderby, Jose Juan Almagro Armenteros, Christopher Heje Grønbech, Lars Juhl Jensen, Henrik Bjøm Nielsen, Thomas Nordahl Petersen, Ole Winther, et al. Improved metagenome binning and assembly using deep variational autoencoders. Nature biotechnology, 39(5)5555-560, 2021.
Sergey Nurk, Dmitry Meleshko, Anton Korobeynikov, and Pavel Pevzner. metaSPAdes: new versatile metagenomic assembler. Genome research, 2745):824-834, 2017.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Shaojun Pan. Chengkai Zhu, Xing-Ming Zhao, and Luis Pedro Coelho. A deep siamese neural network improves metagenome- genomes microbiome datasets across different en- vironments. Nature communications, 13(1):2326, 2022.

---

Published as a conference paper at ICLR 2024
Shaojun Pan, Xing-Ming Zhao, and Luis Pedro Coelho. SemiBin2: self-supervised contrastive learning leads to better MAGs for short- and long-read sequencing. Bioinformatics, 19:i21-i29, 06 2023.
Donovan H Parks, Michael Imelfort, Connor T Skennerton, Philip Hugenholtz, and Gene W Tyson. CheckM: assessing the quality of microbial genomes recovered from isolates, single cells, and metagenomes. Genome research, 25(7):1043-1055 2015.
Mina Rho, Haixu Tang, and Yuzhen Ye. FragGeneScan: predicting genes in short and error-prone reads. Nucleic acids research, 38(20)=111=2191, 2010.
Alexander Sczyrba, Peter Hofmann, Peter Belmann, David Koslicki, Stefan Janssen, Johannes Dröge, Ivan Gregor, Stephan Majda, Jessika Fiedler, Eik Dahms, et al. Critical assessment of metagenome interpretation-4 benchmark of metagenomics software. Nature methods, 14(1 1): 1063-1071,2017
Itai Sharon, Michael J Morowitz, Brian C Thomas, Elizabeth K Costello, David A Relman, and Jillian Banfield. Time series community genomies analysis reveals rapid shifts in bacterial species, strains, and phage during infant gut colonization. Genome research, 23(1):111-120, 2013.
Caitlin M Singleton, Francesca Petriglieri, Jannie M Kristensen, Rasmus H Kirkegaard, Thomas Y Michaelsen, Martin H Andersen, Zivile Kondrotaite, Søren M Karst, Morten S Dueholm, Per H Nielsen, et al. Connecting structure to function with the recovery over 1000 high-quality metagenome-assemblee genomes from activated sludge using long-read sequencing. Nature com- municalions, 12(1):2009, 2021.
Mare Strous, Beate Kraft, Regina Bisdorf, and Halina Tegetmeyer. The Binning of Metagenomic Contigs for Microbial Physiology of Mixed Cultures. Frontiers in Microbiology, 3:410, 2012.
Peter Turnbaugh, Ruth Ley, Micah Hamady, Claire M Fraser-Liggett, Rob Knight, and Jeffrey I Gordon. The human microbiome project. Nature, 449(7164):804-8100 2007.
Ziye Wang, Zhengyang Wang, Yang Young Lu, Fengzhu Sun, and Shanfeng Zhu. SolidBin: im- proving metagenome binning with semi-supervised normalized cut, Bioinformatics, 35(21):4229- 4238, 2019.
Ziye Wang, Pingqin Huang, Ronghui You, Fengzhu Sun, and Shanfeng Zhu. Metabinner: a high- performance and stand-alone ensemble binning method to recover individual genomes from com- plex microbial communities. Genome Biology, 24(1):1, 2023.
Yu- Wei Wu, Yung-Hsu Tang, Susannah G Tringe, Blake A Simmons, and Steven W Singer. MaxBin: automated binning method recover individual genomes from metagenomes ing an expectation-maxiiizatiio algorithm. Microbiome, 2:1-18, 2014.
Yu-Wei Wu, Blake A Simmons, and Steven W Singer. MaxBin 2.0: an automated binning algorithm to recover genomes from multiple metagenomic datasets. Bioinformatiis, 52(4):605-607 2016.
Baoyu Xiang, Liping Zhao, and Menghui Zhang. Unitig level assembly graph based metagenome- assembled genome refiner (ugmagrefiner): A tool to increase completeness and resolution of metagenomme-asembble genomes. Computational and Structural Biotechnology Journal, 21: 2394-2404, 2023.
Hansheng Xue, Vijini Mallawaarachchi, Yujia Zhang, Vaibhav Rajan, and Yu Lin. RepBin: constraint-baaee graph representation learning for metagenomic binning. In AAAI, 2022.
Yi Yue, Hao Huang, Zhao Qi. Hui-Min Dou, Xin-Yi Yi Liu, Tian-Fei Han, Yue Chen, Xiang-Jun Song, You-Hua Zhang, and Jian Tu. Evaluating metagenomies tools for genome binning with real metagenomic datasets and cami datasets. BMC bioinformatics, 21(1):1-15, 2020.
Pengfei Zhang, Zhengyuan Jiang, Yixuan Wang, and Yu Li. Clmb: deep contrastive learning for bust metagenomic binning. In International Conference on Research in Computational Molecular Biology, pp. 326-348. Springer, 2022.
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 THE PSEUDOCODE FOR UNITIGBIN
In this paper, we propose the model of neural networks for constraint-based graph representation to solve the metagenomic contigs binning problem, called UNITIGBIN. UNITIGBIN consists of two main components: Learning, which uses graph neural network model to directly learn the unitig- level assembly graph while adhering to constraints, and Binning, a contig-level binning framework. In the Binning stage, Matching algorithm employed to initialize markered contigs, Propagating labels are used to annotate unmarked contigs while satisfying constraints, and a local Refining strat- egy is incorporated fine-tuna binning assignments. In the subsequent subsection, we will elucidate the Matching and Refining modules and provide the pseudocode.
Matching. In Matching, we design an adapted matching algorithm to obtain optimal binning ini- tialization. The Matching process primarily has two steps: i) Binning Initialization and ii) Iterative Matching. Initially, we arrange the constraints ing the largest constraint set as the initial bin. Then, we perform iterative calculations to determine the similarity between matched bins and candidate contigs. We employ a greedy approach to select the maximum value for matching operations. During the matching process, incorporate thresh- old value denoted as T. If the similarity between a bin and a candidate is below this threshold, we consider it unfavorable add the candidate contig to the bin. Instead, opt create bin that includes this contig. The pseudocode for the UNITIGBiN-Mucchin is as follows.
in descending order based on their length, select-
Algorithm 2: The Markers Matching Algorithm UNIrIGBIN-Matching
Data: Embedding for contigs Z: Heterophilous constraints C; Threshold for adjustment T; Result: Matched binning initializations Ye.
C+ Sort(C) // Sort C in descending order by their length
2 Ye e C[O] I/Intiaaize bin with maximum set of constraints
for k [1,
(i((i,] (imi)))e.SSSmmm.CCC. C(&D // Compute sim between bins and cands s (=( + Son(S) // Sort S in descending order by sim value
Tag =0 MIIntialize the iteration tag as None
for [(.,j) :} do
7
if L not in Tag then
if T then
Yel Ycl] +j
// Add new bin with contig j Add bin |Yel and contig to iteration
11
Tag + [Ycl,]
tag list
12
else
13
Yeli] +-
// Assign contig to bin i Add bin and contig j to iteration tag
14
Tag < i,j
list
15
end
end 16
17 end
end
Refining. In Refining, our primary goal is to explore potential binning assignments for contigs, taking into account heterophilous constraints. This step primarily consists of two components: Splitting and ii) Merging. Splitting aims to divide existing bins into multiple sub-bins when identical marker genes are present within the bin. Merging intended to combine sub-bins into larger bin when these sub-bins do not share the same marker genes. The pseudocode for the UNITIGBIN- Refining is as follows.
A.2 DATASETS AND BASELINES
Datasets. We evaluate UNITIGBIN model on 12 datasets, consisting of 6 assembled by metaSPAdes v3.15.2 (Nurk et al.) 2017) and 6 assembled by metaFlye v2.9 (Kolmogorov et al.] (2020). Within the metaSPAdes-aseemble datasets, Sim20G, Sim50G, and Sim100G are three datasets collected
13

---

Published as a conference paper at ICLR 2024
from GraphBin2 (Mallawaarachchi et al. 2021 and MetaCoAG Mallawaarachhhi & Lin 2022
which are simulated based on the species found in the simMC+ dataset (Wu et al. 2014). Paired- end reads for these datasets are simulated using InSilicoSeq (Gourlé al. 2019). Sharon, COPD, and DeepHPM are 3 real-world datasets. Sharon is preborn infant gut metagenome (Sharon et al, 2013) identified with the National Center for Biotechnology Information (NCBI) accession num- ber SRA052203. COPD refers to the metagenomics of the Chronic Obstructive Pulmonary Disease Lung Microbiome (Cameron et al. 2016) and is associated with the NCBI BioProject number PR- JEB9034. DeepHMP' represents human metagenome sample from the tongue dorsum of partic- ipant in the Deep WGS HMP clinical samples (Lloyd-Price et al., 2017). with the NCBI accession number SRX378791. In the metaally-assembled datasets, 6 real- world datasets are collected from datasess
GraphMB (Lamurias et 2022) and CCVAE (Lamurias al. 2023 The six datasets consist of real-world Wastewater Treatment Plant (WWTP) datasets obtained from (Singleton et al.) 2021 under the BioProject number PRJNA629478. FragGeneScan (Rho et al. al. (2010) and HMMER (Eddy) 2011) are applied detect contigs containing marker genes and generate heterophilic constraints, following the methodology outlined in MetaCoAG (Mallawaarachchi
Lin 2022) and MaxBin 2.0 (Wu et al. 2016). Ground truths for three simulated datasets (Sim20/50/1006 are derived us- ing Minimap2 (018) to map the contigs to the reference genomes, still following the steps of MetaCoAG. Table Al provides comprehensive statistics of datasets.
Algorithm 3: The Binning Refinement Algorithm UNITIG
Data: Binning for contigs B; Heterophilous constraints C; Result: Refined binning B. Splitting
C2M C
Construct mapping function: :oloonooottl Cont:ggnnttgaaaao B -- IIIntiializ the splitting binset
for bin E B do
bs.ms + 0000
I/ Initialize the subbin and submarker
for c E bin do
4 (2)(c)
Map the contig to corresponding marker
if m & ms then
mst ms+m, bst bsth
No identical marker
10
else
B - B+bs
IIdentical marker, add new subbin 1| Initialize the subbin and submarker
bst b. ms+m
end
14
end
15
B < B+bs
add a bin
16 end
11 Merging
B2M t B.C // Construct mapping Bun
19 Tag +- True // Initialize the iteration tag as True
while Tag = True do
21
Tag < False Set the iteration tag as False
22
S=((i,)) s) -Comt(B2M(B)) // Count common markers between
pairwise bins
23
for : in S do
if then
B +- Merging(B.i.j) |/ Meree bin i and bin into one bin
26
Tag - True Set the iteration tag to be true break
end
29
end
30 end
B B Output the final binning assi gnment
14

---

Published as a conference paper at ICLR 2024
Table A1: Summary and statistics of the 12 datasets.
No. of Samples
Fragments length (bp)
No. of Fragments
Contigs length (bp)
No. of Contigs
No. of Links
No.
Dataset
Assembler
Markers
Sim-20G
10,891.04
6,131
46,234.75
1,452
8,213
75
Sim-50G
1
5,888 21
24,401
28,680.50
5,058
32,654
85
Sim-100m 100G
1
4,501.00 .66
67,516
19,977.80
15,729
90,124
85
metaSPAdes
Sharon
18
1,039. 83
37,164
1,212.44
29,899
29.175 194
109
DeepHPM
8
594.81
227.635
694.53
130,363
126,4997
108
COPD
18
716.74
452,600
759.00
125,524
109,134
108
Hjor
39.443.96
22,005
42,677.75
21.111
5,335
108
Viby
4
48,103 183103.74
27,719
52,183.60
26,427
7,342
109
Damh
4
48,748.20
40,048
54,275.15
37,285
12,977
110
metaFlye
Mari
4
40,005.90
42,539
44,377.07
40,450
12,178
108
AalE
41,192.55 4
46,938
44,788.51
44.777
11,749
109
Hade
36,665.14 4
82,063
41,467.02
76,924
26,737
104
Baselines. UNITIGBIN evaluated against three categories of binning tools: a) 2 traditional ap-
proaches, MaxBin 2.0 (Wu et al. 2016) and MetaBAT2 (Kang et al. 2019) b) deep learning- based binning tools, SemiBin (Pan et al. 2022) and VAMB (Nissen et al. 202I): c) assembly graph-based binning models, GraphMB (Lamurias al. 2022), RepBin (ue al. 2022), Meta- CoAG aMallawaarachchi & Lin, 2022), and CCVAE (Lamurias et al., 2023). For all baselines, we
fine-tune their models with various parameters and present metric scores of their best configurations.
i) Traditional approaches:
MaxBin2: is probabilistic model that incorporates Expectation-Maximiiza lizing both composition and coverage features for contigs binning (Wu et al. 2016). Available at https: / sourceforge, net / pttr//oooscsssseeee /maaaminn////
algorithm, uti-
MetaBAT2: constructs a graph using the composition information of contigs and employs graph partitioning algorithm to address the metagenomic binning problem (Kang al. 2019). Available at https:://// /bi tbucket..... org/ worg/berrkee mereeeeeey ey aab/ http//eabtt////mmmmm tetaat/sr... mtc/maste///..
iii Deep learning-based binning tools:
SemiBin: is a reference-based binning approach that aligns contigs to reference genomes, creat- ing must-link and cannot-link constraints. It then utilizes a semi-supervised siamese neural net- work to integrate prior constraints into the contig binning process (Pan et al., 2022). Available at https: / / gå gi thub. com/ i
/Semi Bin.
VAMB: uses deep variational autoencoder models encode both the composition and coverage in- formation of contigs and then employs an iterative clustering algorithm to bin contigs (Nissen al.) 2021 Available at https: / / teitthe thub. com RasmussenLab vamb.
iii) Assembly graph-based binning models:
GraphMB: encodes contig composition and abundance information using variational toencoder model, combining these learned features with the assembly graph to train a graph neural network model. The resulting contig embeddings are then fed into the same clustering algorithm as VAMB for contig binning (Lamurias et al., 2022). Available at https:: /ttp://gitttt con/ MwtMMMicrooiii caaiccooaaaaaa wwrbiallarrMatteeee Br/GraphMB.
RepBin: employs constraint- based self-supervised graph learning framework to model the as- sembly graph, followed by the utilization of GCN-based label propagation model for contig bin- ning (Xue et al.) 2022). Available at ht
thub. com/ xuehansheng/ /aep/i/e...... MetaCoAG: designs an algorithm that integrates composition, abundance, and assembly graph to www/metagentteeeeooccooooooooooo s a
enhance contigs binning, Available at ht /tt//githuu
CCVAE: incorporates the prior constraints of single-copy marker genes, identified using CheckM, into variational autoencoder model to leam the assembly graph. It subsequently employs clus- tering algorithm on learned embeddings for contig binning (Lamurias et al. 2023). Available at https: / //gi thub. com/b.ccom/M.. wwt.cioo//Mi./..cc crobi www.kaaaterr/eeeeeeeeeeeaa
15

---

Published as a conference paper at ICLR 2024
A.3 IMPLEMENTATION DETAILS
In this section, we will provide instructions on how to run our proposed UNITIGBIN model re- produce the experimental results presented in paper. In the preprocessing phase, two crucial operations are carried out to create the unitig-level assembly graphs and derive heterophilous con- straints. These constraints are generated by identifying single-copy marker genes within contigs.
a) Create Unitig-level Assembly Graphs. Two different types of assembly graphs are employed in this paper. We utilize two widely used assemblers, namely metaSPAdes (Nurk al. (2017) and metaFlye (Kolmogorov et al. 2020), to generate the unitig-level assembly graphs. The example command is as follows:
i) The metaSPAdes assembler:
spades - -1 Reads_l.
fastq faatt
Reads_2 fastq -o /output.dir
ii) The metaFlye assembler:
flye --meta --aabbio-rw Reads. fastq -0 /output.dir
b) Extract Heterophilous Constraints. In UNITIGBIN, we use FragGeneScan (Rho et al., 2010)
and HMMER (Eddy 201T) to extract the constraints by identifying single-copy marker genes in contigs. The example command is as follows:
run_Fraggeenescan.pl
-ggeromer//pathhc///cotisss fasta
wttt://ottput..iirrootii.....a.a fasta...aaaaaaa.a cacteraagccoopoiii -complete-0
-trainncomplete taciceee-hhee -thread-8 1>/ htt.:///w././ouuuouoo.ooooooooo/ fasta. frag..
2>
hmmsearch -
httpo//otcciitt/totttttttttttttt fas.ss.fsaaa.ao hmmout --cut.tc
--ep 8 httpp/tttt/aaaaee..oott /otpss/ttttmoootouuuutououuo
/tttt/ottttttttoooooo cooticitticooo.. fasta..aaaaaaa.... frag.
2> / /ttp//ptt.ii//oooniieee.otteteee fasta.aaa........
Next, we employ the code from SolidBin (Wang et al. 2019) to extract constraints and store them in several sets. Each set represents the contigs containing specific single-copy marker gene.
c) Run UNITIGBIN. To reproduce the experimental results in this paper, we can simply run the following command (we take the Sim20G an example):
python uniti tiliiiiiin... py --data Sim20C --epoch 2000 --dim 32 --lr
0.01 --nbatch --a 0.05 --λ, 0.7 --A2 0.1 --th 0.01
where parameter --data a represents the selected dataset; -eepoch denotes the number of epoch;
--dim the dimension of the embedding: lr r the learning rate; --nbatch represents
the number of batches; --a denotes the probability of transition in diffusive convolution; - th represents the threshold in the Matching; -- and --À2 are two parameters control the importance of constraints in the process of Learming and Propagating respectively.
d) CheckM Evaluation. After obtaining the binning results, we can use CheckM v1.1.3 (Parks et al. 2015) to evaluate the performance of binning. The example command is follows: checkn lineage wf -x fasta /input.dir/# fasta
/output.dir//CeekM..Re
checkn analyze -x fasta /atth//c//ceekmttttt222333.11110 phylo. hmm /output_dir /ottput.ddir//heec....
checkn qa --out format 1 -f htthm//phhllll/// hmm /twtppt..dir//htbeeooee
http:////cchekk..atttttta
Running environment. UNITIGBIN is implemented in Python 3.6 and Pytorch 1.8 using the Linux server with Intel Xeon Platinum 8268 2.9 GHz CPU, 96GB RAM and Nvidia Tesla Volta V100- SXM2 with 32GB memory.
Experimental setups. For UNITIGBIN, we use composition features from the sequences and adja- cency matrix of the unitig-level assembly graph the initial features for nodes. The default settings of UNITIGBIN hyperparameters are as follows. The representation dimensions are all empirically set and vary from 32 to 256. The parameter in the diffusive convolution is simply set within the range of [0.005, 0.05]. The batch size of the p-batch varies from to 5 in all datasets. Following the experimental setup in Mallawaarachhhi & Lin 2022 and (Lamurias al. 2023), all the algorithms run five times on each input dataset and the best binning assignment is reported. The UNITIGBIN model is freely available at at petttps://ithuue htt.a///ccooooeeeeeeeeeeeeee
16

---

Published as a conference paper at ICLR 2024
Table A2: Evaluation results UNITIGBIN and baselines.
Dataset
Methods
Contigs / Ratiof
Bins
Precision
Recallt
FIf
ARI
MetaBAT2
402 28.0%
88
97.01
7.96
14.70
21.55
MaxBin2
666 / 46.3%
89.48
42.97
58.06
77.46
VAMB
530 / 36.9%
21
99.62
38.29
55.32
96.52
SemiBin
790 / 54.9%
20
68.21
38.29
49.05
41.69
Sim20G (K=20)
GraphMB
732 50.9%
34
74.35
39.33
51.45
34.43
CCVAE
737 51.3%
51
85.25
38.59
53.13
46.82
RepBin
1,437 99.9%
97.99
95.84
96,90
94.51
MetaCoAG
595 275/41.44 41.4%
20
89.52
38.74 74
54.07
78.66
UNITIGBIN
1,438 / 100 %
21
98.22
98.07
98.14
97.38
MctaBAT2
1,139 / 22.5%
222
81.13
6.09
11 11.33
14.98
MaxBin2
1,900 / 37.6%
49
84.23
33.59
48.03
76.32
VAMB
1,310 25.9%
46
88.74
31.35
46.33
85.74
SemiBin
2,231 44.1%
90.67
36.63
52.18
74.18
Sim50G
GraphMB
2,332 / 46.1%
87
58.24
38.35
46.25
18.11
(K=50)
CCVAE
2,137 / 42.2%
65
54.83
36.94
44.14
16.78
RepBin
5,058/ / 100
47
78.69
90,80
84.31
77.55
MetaCoAG
2,030 / 40.1%
79.72
35.32
48,95
69.30
UNITIGBIN
5,058 / 100% %
48
89.41
91.06
90.23
90.61
MetaBAT2
0.44%
100.00
0.46
0.92
83.95
VAMB
3,814 24.9%
87
87,01
29.82
44.42
81.13
MaxBin2
5,723 37.4%
95
71.10
25,84
37.90
52.43
GraphMB
8,045 / 52.5%
226
46.11
39.62
42.62
7.65
100G
CCVAE
7,206 47.0%
243
56.94
36.58
44.54
13.35
(K=100)
SemiBin
6,706 / 43.8%
957
91.40
34.46
50.05
71.77
RepBin
15,310 99.9%
72
63.51
92.55
75.33
48.58
MetaCoAG
6,033 / 39.4%
90
74.84
30.31
43.15
59.89
UNITIGBIN
15,319 100%
101
76.77
78.45
77.60
79.85
A.4 EVALUATION METRICS
In addition to the CheckM (Parks al. 2015) and AMBER (Meyer et al. 2018) tools, also calculate the Precision, Recall, FI, and ARI as evaluation metrics for the contigs binning task. A R KxS is used to denote the confusion matrix, where K is the number of bins predicted by binners and S represents the number of true species in the ground truth. The element in A, like Ak.s, indicates that the number of contigs species s. N is the total number of contigs binned by this tool and N, denotes the number of contigs that are not clustered or discarded by this binning tool. The detailed evaluation metries described as follows:
clustered into the bin & but actually belong to the
Σx max, Akss
Σ, max; AK,S
Precision
Recall =
(6)
Σx E. Ak.
Σx E, Ak, + N
Σn. (At.e) ( Σx Ak. Σ, (
Precision x Recall
F1 = 2 Precision Recall.
ARI
E. (A
E. (A
1 AE..) + E. (A..))
In the results, we present the number of contigs identified by different binning tools and also calcu- late the proportion of contigs that have been labeled. The higher the proportion of labeled contigs, the better the binning tool performs. Besides, we also show the number of bins identified by differ- ent binners. Both predicted bins higher or lower than ground truth are not good. From the evaluation metrics collected in Table A2 can find that UNITIGBIN achieves the highest score among the most evaluation metrics. In particular, UNITIGBIN can label both long and short contigs. leading significantly higher Recall compared to other binning tools, with the exception of RepBin. For
17

---

Published as a conference paper at ICLR 2024
example, in the SimI00G dataset, MetaBAT2 can only label 0.4% of the contigs, while UNITIGBIN capable of labeling all 15,319 contigs.
A.5 CHECKM RESULTS ON METASPADES DATASETS.
We use CheckM tool to evaluate the performance UNITIGBIN on metaSPAdes assembled datasets. We adhere to the experimental setup outlined in MetaCoAG (Mallawaarachchi & Lin 2022). We define precision as 1/(1 contamination) and recall as completeness. High-quality (HQ) bins are characterized by precision > 90 and recall 80. Medium-quality (MQ) bins have precision > 80 and recall > 50, while the remaining bins are classified as Low-quality (LQ) bins. The detailed evaluation metrics are collected Table A3 Several deep learning- -based binning tools, such as SemiBin, GraphMB, CCVAE, and RepBin, could not be executed on the DeepHPM and COPD datasets due to resource limitations. Table A3 demonstrates that UNITIGBIN outper- forms the other baseline methods significantly. UNITIGBIN achieves the highest number of HQ bins and HQ+MQ bins. For instance, the real COPD dataset, UNITIGBIN obtains HQ and 28 MQ bins, which is more than the sccond-highed number of HQ bins achieved by MetaCoAG (17 for HQ and MQ bins). In DeepHPM, UNITIGBIN achieves 12 HQ bins, surpassing the highest number of HQ bins obtained by baselines (8 for MetaCoAG and MaxBin2).
Table A3: Evaluation results by UNITIGBIN and baselines (CheckM).
Sim20G
Sim50G
SimI00G MQT
Methods
HQT
MQT
LQ+
HQf
MQT
LQ+
HQT
LQT
MetaBAT2
5
16
194
24
MaxBin2
20
0
35
7
54
15
26
SemiBin
18
1
3
38
4
8
68
9
31
VAMB
18
31
12
51
10
26
GraphMB
1
73
206
CCVAE
12
1
38
15
71
28
213
RepBin
18
15
15
19
8
33
MetaCoAG
17
34
3
69
8
13
UNITIGBIN
20
14
Sharon
DeepHPM
COPD
HQT
MQF
LQL
HQT
MQT
LQI
HQf
MQT
LQL
MetaBAT2
2
2
20
60
2
74
MaxBin2
6
47
24
123
SemiBin
5
VAMB
5
2
13
7
48
GraphMB
2
0
53
CCVAE
2
74
RepBin
46
MetaCoAG
7
3
8
10
9
17
25
26
UNITIGBIN
7
5
2
12
17
10
21
28
20
A.6 CONSTRAINTS FROM CHECKM
In the UNITIGBIN model, we use the FragGeneScan (Rho et al. 2010) and HMMER (ddy 201 tools to generate heterophilous constraints, following the MaxBin2 Ww al. 2016) and Meta- CoAG Mallawaarachchi & Lin 2022). However, it's worth noting that CCVAE (Lamurias et al.) 2023) relies on the CheckM tool to generate prior information for constraints. To further assess the performance of our proposed UNITIGBIN model, we also integrate the heterophilous con- straints obtained from CheckM instead of the original constraints into UNITIGBIN. Figure A] shows the number of HQ (completeness>>90 & Contamination and MQ (completeness>-50 & Contamination-<10) bins achieved by UNITIGBIN under the constraints of CheckM. UNITIG- BIN(CheckMI achieves more HQ and MQ bins than UNITIGBIN and significantly more than CC- VAE. For example, the Hade dataset, (NrrIGBINCheccMM achieves the highest number HQ bins (75), surpassing the HQ bins obtained CCVAE (52 HQ bins) and UNITIGBIN (64 HQ bins).
18

---

Published as a conference paper at ICLR 2024
[Hjor]
[Viby]
[Mari]
[Damh]
[AalE]
[Hade]
500
450
463
434
400
350
336
332
300
319
290
250
255
200
222
205
178
191
190
189
150
160
100
103
115
50
46
15
74
86
60
63
66
52
64
75
28
0
COVAE
AntiigiinChaacke
UnitigBin
CCVAE
UnitigEinCheckai
UntiiBlin
COVAE
Unitigiin(hhachi
UnitigBin
COVAE
UnitiBiin
CnttgBinnChackki
COVAE
UnitigBin(Checke
UnitiBiin
COVAE
UnitigGin
UniugBin
Figure A1: Results of CCVAE, UNITIGBIN and UNITIGBIN(CheckM) on 6 datasets.
A.7 PARAMETERS ANALYSIS AND SCALABILITY
More details in ablation study. In Figure 6 the 'Learning' denotes the Learning model and uses K-Means to bin contigs; 'w/o Refining' represents the UNITIGBIN model without the final Refining step: LLarning w/o C' indicates that not incorporate constraints into the Learning process; 'Learn- ing w/o B' means the Learning model without batch loss; and 'Binming w/o C" is the Binning model does not optimize constraints satisfaction. Figure iillustrasss that each component within UNITIG- BIN contributes to the improvement in contig binning performance.
Training and running time. Figure A2 (a) and (b) show the training process of Learning and Prop- agating modules in UNITIGBIN respectively. The loss value stabilizes when the number of epochs reaches 600. Besides, as the number of training iterations increases, the proportion of violated con- straints decreases. We also benchmark the rumning time of UNITIGBIN against selected baselines on 100G (refer to Figure A2 (c)). MaxBin2 and MetaCoAG are two non-deep learning models and were executed CPU, while other deep learning- based binning tools were trained GPU. Here, we provide the rumning time and the count of HQ bins. UNITIGBIN is the recond-fasted deep learning-based binning tool, with runtime of approximately 30 mins, beaten only by VAMB, which faster. is significantly faster than other deep learning baaed binning tools, including GraphMB (49 mins), SemiBin (55 minutes), RepBin (55 minutes), and CCVAE (72 minutes).
(a)
(b)
(c)
loss of leerning loss of reconstruction
80
UnitigBin
0.8
loss of p batch
constraints
0.8
MotaCoAG
SemiBin
HD Bims
MaxBin2
0.6
propepating violatigg
0.4
0.4
CCVAE
0.2
0.2
20
GraphMB
RepBin
0.0
200
400
600
800
1000
200
400
600
800
1000
10
30
50
70
Training Iterations
Training iterations
Running time (mins)
Figure A2: The training loss and running time of UNITIGBIN on Sim100G.
Parameters analysis. In this part, we investigate the importance of core parameters in the UNITIG- BIN without Refining model, including the dimension of embedding d, the probability of transition in diffusive convolution a, the threshold in the matching algorithm T, and two parameters control the importance of constraints x and X2. Figure A3 (a) shows that UNITIGBIN is relatively robust to the dimension of embedding d ranging from 32 512. In Figure A3 (b), we observe grad-
19

---

Published as a conference paper at ICLR 2024
ual increase in the number of HQ bins the parameter in DIFFCONV is varied from 5e to 5e 5e-2. 2. Figure A3 (c) shows that UNITIGBIN is also relatively robust to the parameter of threshold in the matching algorithm. The parameter A in the Learning model governs the significance of heterophilous constraints. As A increases, the number of HQ bins also increases, reaching its max- imum when set to 0.7. The UNITIGBIN model demonstrates robustness changes in the parameter
22 in the Binning model (as shown in Figure A3 (c)).
(a)
(b)
100
80
0.0005
0.005
Dimension
Alpha DiffConv
Threshold Matching
(d)
(e)
HQ Bins
0.1
0.3
0.5
0.7
0.9
0.01
0.05
0.1
0.3
0.5
Lambda in Learning
Lambda in Binning
Figure A3: Parameters analysis of UNITIGBIN on Sim100G (d, a, T, A1. and 22).
A.8 ADDITIONAL EXPERIMENTAL RESULTS
Evaluating constraints satisfaction. One goal of our proposed UNITIGBIN model is to enhance the satisfaction of heterophilous constraints derived from single-copy marker genes. In order assess the achievement of our objectives, we calculate the ratio of final binning results that deviate from heterophilous constraints. The illustration in Figure A3(b) depicts the procedure for minimizing the number of violating constraints. Furthermore, the table below (on Sim100G) provides the ratio of violating constraints accomplished by the UNITIGBIN and selected baseline methods. UNITIGBIN satisfies almost all constraints, exhibiting only a 0.9% violation of heterophilous constraints, a rate lower than that observed in other baseline methods.
Table A4: The specific proportion of violated heterophilous constraints.
MaxBin2
SemiBin
VAMB
GraphMB
CCVAE
RepBin
MetaCoAG
UNITIGBIN
1,712/
2,226/
2.623/
37/
42,244/
22,627
8,854/
2,069/
1,686/ /
Num.
127.449
180,044
152,948
1,313
170,476
167.211
177,910
153,026
182,366
Ratio
1.34%
1.24%
1.92%
2.82%
24.80%
13.53%
4.98%
1.35%
0.90%
Additional comparisons with the Metadecoder tool. Metadecoder (Liu et al. 2022) is a binning tool based on Gaussian mixture model, utilizing k-mer frequencies and coverages. Here, we also introduce Metadecoder as a baseline and conduct initial comparisons on three simulated datasets and one Sharon dataset. We followed the experimental settings specified in MetaCoAG and selected CheckM as the evaluation tool. As observed in Table A5 Metadecoder's performance is noticeably inferior to that of UNITIGBIN. In Sim20G, Metadecoder generates 19 high-quality bins, surpassing the count achieved by MetaCoAG (17) but falling short of UNITIGBIN (20). In the Sim50G and Sim 100G datasets, Metadecoder produces 25 high-quality bins for Sim50G and 35 for Sim respectively. These counts are notably lower than those achieved by UNITIGBIN (43 for Sim50G
20

---

Published as a conference paper at ICLR 2024
and 76 for Sim100G) In the Sharon dataset, Metadecoder generates only 4 high--uality bins, count significantly lower than the number achieved by both MetaCoAG and UNITIGBIN (7).
Table A5: Evaluation results by UNITIGBIN and baselines.
Sim20G
Sim50G
Sim100G
Sharon
Methods
HQT
MQT
HQT
MQT
I.Q.
HQT
MQT
LQ4
HQT
MQT
LQ.
Metadecoder
19
2
25
10
35
27
45
MetaCoAG
17
0
0
34
6
3
69
8
13
7
3
UNITIGBIN
20
0
43
4
76
11
14
7
5
Additional comparisons with the SimBin2 tool. we conduct comparison between UNITIGBIN and SemiBin2 (Pan et al., 2023), an enhanced version of SemiBin, to further assess performance. SemiBin2 is applied to three simulated datasets and one real world dataset, and its performance is compared with SemiBin, MetaCoAG (the best assembly graph-based baseline), and UNITIGBIN. We adhere to the experimental setup outlined in MetaCoAG (refer to A.5), and the resulting ex- perimental data is presented in Table A6 SemiBin2 demonstrates superior performance compared to SemiBin and MetaCoAG across all three simulated datasets, although it falls slightly short of UNITIGBIN. In the Sharon dataset, SemiBin2, MetaCoAG, and UNITIGBIN all attain the maximum count of high-quality bins (7), which is higher than the number obtained by SemiBin (5).
Table A6: Evaluation results by UNITIGBIN and baselines.
Sim20G
Sim50G MQ1
Sim100G MQt
Sharon MQT
Methods
HQt
MQt
LQL
HQt
LQL
HQt
LQU
HQt
LQL
SemiBin
18
3
38
4
8
68
9
31
0
10
SemiBin2
1
15
MetaCoAG
17
0
0
34
6
3
69
8
13
3
0
UNITIGBIN
20
0
1
43
4
4
76
11
14
7
5
2
Assessing performance using CheckM2. We utilize CheckM2 (Chklovski et al. 2023) to further assess the performance of UNITigBIN and the baseline methods. As an illustration, we focus on three simulated datasets assembled by metaSPAdes. Our experimental setup aligns with the guide- lines provided in MetaCoAG (Mallawaarachchi & Lin, 2022), where High-quality (HQ) bins are defined by precision > 90 and recall > 80. Medium-quality (MQ) bins exhibit precision > 80 and recall > 50, while the remaining bins are categorized as now-quality (LQ) bins. The CheckM2 repository can be accessed at https: hopp:///iia //ttthbbbbbb///////// com/ chklovske /hsski/Chhck2.. and the ex- ecution command $ checkm2 predict threadds 64 input / /input_de cipputddir// / /output_dir// The detailed experimental results compiled in Table A7 UNITIGBIN demonstrates superior performance compared to other baselines, securing a top-tier position. As an instance, UNITIGBIN identifies 20 high-quality bins in the Sim20G dataset, a number equivalent to that achieved by MaxBin2 and VAMB. In the Sim50G dataset, UNITIG- BIN secures 41 high-quality bins, slightly surpassing the count achieved by MaxBin2 (40). In the Sim 100G dataset, UNITIGBIN acquires 69 high-quality bins, slightly fewer than the count achieved by SemiBin (70). UNITIGBIN continues show good performance in evaluations using CheckM2.
--outout-directt
Additonal comparison on CAMI dataset. While our paper extensively employs various simulated and real-world datasets to assess the performance of UNITIGBIN comparison to state-of-the-art baselines. we also undertake benchmarking on specific dataset (Urogenital tract, referred toe as CAMI UG) from the toy Human Microbiome project of the second CAMI challenge (Sczyrba al.) 2017 Meyer et 2022). Additionally, we adhere to the experimental setup outlined in MetaCoAG and employ CheckM as the evaluation tool for conducting preliminary comparisons. In this part, our primary choice for comparative method is VAMB (Nissen et al. 202 deep learning-based bin- ning tool. A summary of the experimental results is presented in Table A8 UNITIGBIN slightly sur- passes the performance of the VAMB model, yielding 35 high-quality bins and 26 peddium-qualig bins. UNITIGBIN can bin a greater number of contigs than VAMB, with a runtime of approximately 40 minutes (For detailed information about the running environment, please refer to Section A.3.).
21

---

Published as a conference paper at ICLR 2024
Table A7: Evaluation results by UNITIGBIN and baselines (CheckM2).
Sim20G
Sim50G
SimI00G
Methods
HQt
MQT
LQ4
HQt
MQt
LQL
HQt
MQ1
LQU
MetaBAT2
208
22
MaxBin2
20
40
3
65
12
18
SemiBin
19
1
2
39
9
70
8
20
VAMB
20
0
35
10
68
6
13
GraphMB
10
23
14
73
3
170
CCVAE
13
71
119
RepBin
18
17
21
25
14
39
MetaCoAG
18
39
4
4
67
12
4
UNITIGBIN
20
9
12
14
To apply UNITIGBIN to the CAMLUG dataset, we configure the 'nbatch' parameter indicating the division of the original unitig-level assembly graph into 5 subgraphs. While we have an opti- mization function for joint-unitigs pairs (p-Batch), increasing the number of batches may potentially introduce more errors. Thus, there is still a need for efforts to design more efficient binning models on the unitig-level assembly graphs, especially when dealing with large-scale metagenomic data.
Table A8: Evaluation results by UNITIGBIN and VAMB on the CAMI UG dataset.
Binned Contigs
Detected Bins
CAMI UG
Methods
HQT
MQT
LQL
VAMB
21,398 49,879
34
10
UNITIGBIN
121
35
26
53
22


Reviews:
[{"review_id": "OExa22rE8F", "reviewer": "Reviewer_22Pk", "summary": "The paper presented a graph neural net based approach for the application of binning metagnomic contigs, ie. clustering genomic subsequences into bins representing a constituent organism. The paper showed numerical results where the presented approach outperformed the other tested approaches on 12 public datasets.", "questions": "1) Suggest to motivate the readers more by explicitly describing the problem formulation including what objective is desired; ideally this can be formulated as an mathematical objective function and tied to the choice of loss function in the later learning component.\n\n2) Suggest to describe the experiment setup including what training/testing/validation data is included and clarify the statistical significance of the result comparison; if this is not feasible, provide justification and identify future steps.\n\n3) It’s not clear from the experiment results why particularly GNN is needed – suggest to provide perhaps case studies to show how GNN is able to capture the information that the other approaches cannot, since introducing GNN is considered as the main contribution of the work.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The application seems to be novel by introducing the popular-studied approach of graph neural nets. The experiment includes 12 datasets and compares against 3 categories of tools.", "weaknesses": "I like how the authors keep the section of Problem Statement, but I don’t follow the exact problem to be solved however. The paragraph on Page 3 in Problem Statement only talked about the notation but does not specify what the task is, or what the desired output should be. Further, it wasn’t clear what objective is aimed at – which also motivates my question for how we make sure the objective function in each component maps to the objective of binning?\n\nSeparately, in the experiment setup, it’s unclear how the training/testing/validation is conducted; also while the results reported in Table 2 are promising, it’s unclear how significant they are.\n\nSince one motivation described in the Intro is that the presented approaches will respect the constraints – it’d be good to explicitly evaluate how it was done as compared to other methods, either in an explicit metric (or perhaps I mis-interpret the existing one?) or through an example.", "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": "", "extra_scores": {}}, {"review_id": "vysv4UJpMY", "reviewer": "Reviewer_WrPh", "summary": "In this paper, the authors introduce a novel binning tool, UNITIGBIN, which encodes unitig-level assembly graphs while considering constraints generated by single-copy marker gene information. After obtaining the embeddings of the sequences, UNITIGBIN bins the contigs (formed by combining one or multiple connected unitigs) using a binning framework consisting of 1) binning initialization, 2) iterative matching, 3) propagating and 4) refining. The results from datasets with assembly graphs generated by two different assemblers demonstrate that UNITIGBIN outperforms the compared methods in overall.", "questions": "Please provide more details about the datasets, for example, the number of the sequencing samples, the way to obtain the ground truth.\nThe definition of single-copy marker genes and the introduction of semibin appear to lack precision", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper offers a practical approach for transitioning from contig-level representation learning to unitig-level.", "weaknesses": "The novelty appears somewhat limited, as the approach primarily combines existing representation learning techniques and the constraint-based graph representation learning-based binning method RepBin, albeit with the conversion of assembly graphs from contig-level to unitig-level. Additionally, the binning steps appear to be a combination of Metacoag (binning initialization) and RepBin (propagating and refining) with limited improments. The authors should provide a more detailed and distinct description of the similarities and differences.\n\nThe experiments are inadequate in terms of comparing the results obtained from unitig-level assembly graphs with those from contig-level assembly graphs. These experiments are significant for demonstrating the transition from unitig-level assembly graphs to contig-level assembly graphs.\n\nThe experiments are insufficient. Most of the datasets are small-scale single-sample datasets. For a more robust comparison of binning performance, it is recommended to utilize the CAMI I and CAMI II benchmark datasets.  In addition, the recently introduced Metadecoder has shown its effectiveness as a method. SemiBin2, an improvement over Semibin1, presents a novel approach specifically designed for long read data. It is highly recommended that the authors include these methods in the benchmark analysis.\n\nWe recommend that the authors employ Checkm2 to assess MAG quality, as it outperforms the original version of CheckM in predicting MAG quality, even for those with sparse genomic representation or reduced genome size.\n\nThis method is tailored to address a particular problem and may pose challenges when attempting to adapt it for use in different domains.", "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": "", "extra_scores": {}}, {"review_id": "FmfC9EPHWj", "reviewer": "Reviewer_UkJP", "summary": "* A tool for metagenomic binning (clustering) has been developed, consisting of two main components: a learning stage where representations of unitigs (nodes) and contigs (paths) from the unitig assembly graph are considered, along with the constraints that prevent two contigs from belonging to the same bin; and a binning stage where the labels are initialized, propagated, and refined.\n* The primary novelty of the proposed method arises from the direct learning approach applied to the unitig assembly graph, rather than reconstructing a contig assembly and learning from it. Additionally, a clustering method has been introduced as a replacement for Kmeans, leveraging the learned representations to address the issue of imbalanced bin size.\n* UnitigBin has been evaluated on 12 datasets against baseline methods. The binning results have been assessed by evaluating both the completeness and contamination of the bins using checkM and by evaluating the accuracy of clustering via Precision, Recall, F1, and ARF scores.", "questions": "* Is there any evidence or an intuitive explanation of what additional information is captured by learning directly from the unitig assembly graph instead of the reconstructed contig assembly graph, and how this contributes to the improvement in binning performance? Conducting an ablation study by running a similar framework directly on the unitig assembly graph and demonstrating performance differences could be helpful for illustration.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The evaluation is comprehensive. It compares different categories of baseline binning methods, including traditional approaches, deep-learning-based binning tools, and assembly graph-based binning tools. Ablation studies and runtime analyses were also conducted, demonstrating the usefulness and efficiency of each component of the proposed framework.\n* The binning results from the proposed method show a significant improvement over the baselines on both measures, the completeness and contamination of the bins using checkM and the accuracy of clustering via Precision, Recall, F1, and ARF scores.\n* A p-batch training technique is proposed to address the computational challenge without compromising efficiency.", "weaknesses": "* It shows that the overall performance is heavily reliant on the choice of downstream clustering methods. Using Kmeans on the learned representation yields surprisingly poor results, which raises the question of whether the representation learning is beneficial in this application.\n* Considering the additional computational complexity introduced when learning directly from Unitig assembly graphs, it is not entirely clear why the proposed method can capture additional information that may have been overlooked in prior work that learned from reconstructed contig assembly graphs.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)