Tile-X: A vertex reordering approach for scalable long read assembly

Tile-X: A vertex reordering approach for scalable long read assembly [Proceedings] | bioRxiv /* */ /* */ <!-- <!-- /*! * yepnope1.5.4 * (c) WTFPL, GPLv2 */ (function(a,b,c){function d(a){return"[object Function]"==o.call(a)}function e(a){return"string"==typeof a}function f(){}function g(a){return!a||"loaded"==a||"complete"==a||"uninitialized"==a}function h(){var a=p.shift();q=1,a?a.t?m(function(){("c"==a.t?B.injectCss:B.injectJs)(a.s,0,a.a,a.x,a.e,1)},0):(a(),h()):q=0}function i(a,c,d,e,f,i,j){function k(b){if(!o&&g(l.readyState)&&(u.r=o=1,!q&&h(),l.onload=l.onreadystatechange=null,b)){"img"!=a&&m(function(){t.removeChild(l)},50);for(var d in y[c])y[c].hasOwnProperty(d)&&y[c][d].onload()}}var j=j||B.errorTimeout,l=b.createElement(a),o=0,r=0,u={t:d,s:c,e:f,a:i,x:j};1===y[c]&&(r=1,y[c]=[]),"object"==a?l.data=c:(l.src=c,l.type=a),l.width=l.height="0",l.onerror=l.onload=l.onreadystatechange=function(){k.call(this,r)},p.splice(e,0,u),"img"!=a&&(r||2===y[c]?(t.insertBefore(l,s?null:n),m(k,j)):y[c].push(l))}function j(a,b,c,d,f){return q=0,b=b||"j",e(a)?i("c"==b?v:u,a,b,this.i++,c,d,f):(p.splice(this.i++,0,a),1==p.length&&h()),this}function k(){var a=B;return a.loader={load:j,i:0},a}var l=b.documentElement,m=a.setTimeout,n=b.getElementsByTagName("script")[0],o={}.toString,p=[],q=0,r="MozAppearance"in l.style,s=r&&!!b.createRange().compareNode,t=s?l:n.parentNode,l=a.opera&&"[object Opera]"==o.call(a.opera),l=!!b.attachEvent&&!l,u=r?"object":l?"script":"img",v=l?"script":u,w=Array.isArray||function(a){return"[object Array]"==o.call(a)},x=[],y={},z={timeout:function(a,b){return b.length&&(a.timeout=b[0]),a}},A,B;B=function(a){function b(a){var a=a.split("!"),b=x.length,c=a.pop(),d=a.length,c={url:c,origUrl:c,prefixes:a},e,f,g;for(f=0;f<d;f++)g=a[f].split("="),(e=z[g.shift()])&&(c=e(c,g));for(f=0;f<b;f++)c=x[f](c);return c}function g(a,e,f,g,h){var i=b(a),j=i.autoCallback;i.url.split(".").pop().split("?").shift(),i.bypass||(e&&(e=d(e)?e:e[a]||e[g]||e[a.split("/").pop().split("?")[0]]),i.instead?i.instead(a,e,f,g,h):(y[i.url]?i.noexec=!0:y[i.url]=1,f.load(i.url,i.forceCSS||!i.forceJS&&"css"==i.url.split(".").pop().split("?").shift()?"c":c,i.noexec,i.attrs,i.timeout),(d(e)||d(j))&&f.load(function(){k(),e&&e(i.origUrl,h,g),j&&j(i.origUrl,h,g),y[i.url]=2})))}function h(a,b){function c(a,c){if(a){if(e(a))c||(j=function(){var a=[].slice.call(arguments);k.apply(this,a),l()}),g(a,j,b,0,h);else if(Object(a)===a)for(n in m=function(){var b=0,c;for(c in a)a.hasOwnProperty(c)&&b++;return b}(),a)a.hasOwnProperty(n)&&(!c&&!--m&&(d(j)?j=function(){var a=[].slice.call(arguments);k.apply(this,a),l()}:j[n]=function(a){return function(){var b=[].slice.call(arguments);a&&a.apply(this,b),l()}}(k[n])),g(a[n],j,b,n,h))}else!c&&l()}var h=!!a.test,i=a.load||a.both,j=a.callback||f,k=j,l=a.complete||f,m,n;c(h?a.yep:a.nope,!!i),i&&c(i)}var i,j,l=this.yepnope.loader;if(e(a))g(a,0,l,0);else if(w(a))for(i=0;i (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0];var j=d.createElement(s);var dl=l!='dataLayer'?'&l='+l:'';j.src='//www.googletagmanager.com/gtm.js?id='+i+dl;j.type='text/javascript';j.async=true;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-M677548'); Skip to main content Home About Submit ALERTS / RSS Search for this keyword Advanced Search Confirmatory Results Tile-X: A vertex reordering approach for scalable long read assembly [Proceedings] View ORCID Profile Oieswarya Bhowmik , View ORCID Profile Ananth Kalyanaraman doi: https://doi.org/10.1101/2025.04.21.649853 Oieswarya Bhowmik 1 School of Electrical Engineering and Computer Science, Washington State University , Pullman, WA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Oieswarya Bhowmik For correspondence: oieswarya.bhowmik{at}wsu.edu Ananth Kalyanaraman 1 School of Electrical Engineering and Computer Science, Washington State University , Pullman, WA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Ananth Kalyanaraman Abstract Full Text Info/History Metrics Supplementary material Preview PDF Abstract Traditional approaches for long read assembly compute overlapping reads and subsequently use that overlap information to assemble the contigs. Inherent to this approach is the subproblem of ordering the reads as per their (unknown) genomic positions of origin. However, existing approaches are not designed to explicitly target computation of this true ordering during the assembly process; instead the ordering information becomes available only after the assembly is complete. In this paper, we posit that prior computing of a reliable read ordering, even if imperfect, can significantly reduce the computational burden of the assembly process, preserve assembly quality, and enhance parallel scalability. Specifically, we present Tile-X , a novel graph-theoretic vertex reordering-centric approach to compute long read assemblies. The main idea of the approach is to efficiently compute an overlap graph first, use the overlap graph to (re)order the reads (vertices of the graph), and use that ordering to generate a partitioned parallel assembly. We test this idea with two classes of vertex reordering schemes: a) one that uses standard graph vertex reordering schemes that maximize graph locality or bandwidth measures; and b) another class where we custom define a sparsified reordering scheme that exploits sequence characteristics of the underlying graph to reduce the memory and time-footprint for the final assembly step. Using experiments on a combination of real-world and simulated PacBio High Fidelity (HiFi) long reads generated from real genomes, we demonstrate that the Tile-X approach is able to achieve substantial improvements over state-of-the-art long read assemblers, in memory efficiency and runtime, while preserving assembly quality metrics such as NGA50 and largest alignment. On average, across all the inputs, Tile-X achieved an NGA50 between 1.06 × and 2.1 × larger than state-of-the-art assemblers we compared with, while reducing runtime by up to 3.5 × and memory consumption up to 3.3 × . 1 Introduction The recent emergence and rapid evolution of long read sequencing technologies has spawned off a new era in the genome discovery, variant discovery, disease identification, and phylogenetic analysis [ 1 , 2 , 3 , 4 , 5 ]. Single molecule sequencing (SMS) technologies including Oxford Nanopore Technologies (ONT) [ 2 ] and Pacific Biosciences (PacBio) [ 6 ] are starting to provide long reads covering different length ranges and quality. PacBio provides reads of varying length intervals (30–60 Kbp for CLR, 10–25 Kbp for HiFi) and low error rates (5%–13% for CLR, 100 Kbp) but with higher error rates (8%-15%) [ 4 , 7 , 8 ]. Owing to the rapid evolution of the long read technology, long read assembly remains an actively pursued problem for algorithmic development and optimization. There are broadly two classes of long read assemblers: those that construct a de Bruijn graph [ 9 , 10 ] and those that use the overlap layout consensus (OLC) approach [ 11 , 12 , 13 , 14 , 15 ]—with a majority following the OLC approach. In the OLC approach, overlapping reads are detected (either through alignment-based or alignment-free) methods, and the overlap information is used to build a read graph (or string graph) where nodes are reads and edges are between pairs of overlapping reads. Subsequently, this graph is processed to generate contigs that constitute the output assembly. The individual assemblers typically vary in the way they compute the overlaps and the way they process the graphs to generate contigs. For instance, MECAT [ 11 ] leverages a pseudolinear alignment scoring algorithm to accelerate overlap detection, reducing computational overhead substantially. Falcon [ 12 ] utilizes a hierarchical genome assembly process to produce phased diploid assemblies that are both accurate and contiguous. Peregrine [ 13 ] employs sparse hierarchical minimizers to streamline the overlap detection process, enabling rapid assembly of high-coverage datasets with reduced computational resources. Tools such as HiCanu [ 14 ] and Hifiasm [ 15 ] enhance the quality of their alignments through strategies like haplotype phasing and homopolymer compression. However, across all these assemblers the two major phases are the computation of overlap and the use of that overlap information to produce the assemblies. Inherent to the OLC approach of assembly is the subproblem of ordering the reads as per their (unknown) genomic positions of origin. In fact, if the true ordering of reads along the target genome becomes known, then the problem of de novo assembly is significantly simplified because all that remains is to compute the alignment between successive pairs of overlapping reads defined by that order. However, the ordering of reads is not known a priori . Furthermore, existing assemblers are not designed to explicitly target computation of this true ordering during the assembly process. Instead, the ordering information becomes available after the final assembly is produced. There have been some recent works which have exploited clustering or partitioning ideas to generate an assembly [ 16 ]. Clustering tasks can be viewed as an alternative to generate an ordering, binning the reads into buckets, which can be independently processed for assembly. However, generating an ordering (partial or total) has further information that can be exploited. Contributions In this paper, we evaluate the merits of computing an explicit ordering of reads during the early stages of the assembly process. In particular, we posit that computing an explicit read ordering, even if imperfect, has the potential to significantly reduce the computational burden of the assembly process, without compromising on the assemby quality, while enhancing parallel scalability. Specifically, we present Tile-X , a novel graph-theoretic vertex reordering-centric approach to compute long read assemblies. The main idea of the approach is to efficiently compute an overlap graph first, use the overlap graph to (re)order the reads (vertices of the graph), and use that ordering to generate a parallel partitioned assembly. Here, we note that it may not be practical to compute the true ordering. In fact, under various sequence-agnostic graph-theoretic optimization measures (evaluated in [ 17 ]), the problem of computing such an optimal ordering is also intractable. However, it is also not necessary to compute a perfect ordering. Instead, a cheaper approximate ordering could suffice to generate a coarse partitioning of reads, providing a two-fold benefit: a) separation of reads from unrelated parts of the genome into different partitions (important for reducing potential misassemblies); and b) introducing a way to process the different partitions in parallel, thereby improving scalability. We test this main idea of using ordering to aid long read assembly, under two classes of vertex reordering schemes: a) one that uses standard graph vertex reordering schemes [ 18 , 19 , 20 ] that maximize various graph locality/bandwidth measures [ 17 ]; and b) another class where we custom-define a new type of sparsified reordering scheme that exploits sequence characteristics of the underlying graph to reduce the computational footprint for the final assembly step. Our experiments on a combination of real-world and simulated PacBio High Fidelity (HiFi) long reads generated from real genomes demonstrate that the Tile-X approach is able to achieve substantial improvements over state-of-the-art long read assemblies, in memory efficiency and runtime, while preserving assembly quality metrics such as NGA50 and largest alignment. For instance, for the full human genome, the sparsified reordering version of Tile-X (called Tile-Far ) achieves an NGA50 that is 2.1× larger compared to Hifiasm , at a run-time that is 1.9× faster, while consuming only 30% of the memory. Our results also elucidate the inherent performance-quality trade-offs among the ordering schemes. We note that our Tile-X approach can be also viewed as a framework because it is generic enough to allow the use of any long read assembler in the last step of contig assembly. 2 Methods In this section, we first outline the major steps of our Tile-X workflow for long read assembly using read ordering ( Section 2.1 ). We then provide two problem formulations for the read ordering, and describe our method for each of those formulations ( Section 2.2 ). In Section 2.2.3 , we present the design of our overall Tile-X parallel implementation. Notation For rest of the paper, we use the following notation. Let L = { r 1 , r 2 , …, r n } denote the set of n input long reads. Given a read r , the length of the read is denoted by | r |. We denote an overlap-based read graph as G ( V, E ), where V = L (i.e., one vertex per read) and an edge ( i, j ) connecting the vertices corresponding to r i and r j . The graph is undirected. We also associate a numerical weight associated with each edge, denoted by ω i,j , to reflect the strength of overlap between the two reads. 2.1 Overview of the Tile-X workflow As introduced and motivated in Section 1 , the main idea of our approach is to compute a read ordering from the read graph ( G ( V, E )) and use that ordering information to generate a genome assembly. Below, we present a high-level summary of the major steps ( Figure 1 ), with details presented in subsequent sections: S1) Graph construction: Given L , construct a read graph G ( V, E ) as per the overlap detection method of choice. Different assemblers choose different methods (alignment-based or alignment-free or a combination). For testing purposes, we use JEM-mapper [ 21 , 22 ]—an alignment-free, distributed, and parallel mapping tool that is both efficient and accurate. JEM-mapper employs a sketch-based approach, generating minimizer-based Jaccard sketches to identify overlaps. To further optimize the mapping process, we focus on mapping only the end segments of the long reads—i.e., for each read, we extract a segment of ℓ base pairs (ℓ = 2 Kbp used in our experiments) from both ends to generate sketches. The output of this step is a read graph G ( V, E ) for all the long reads. Download figure Open in new tab Figure 1. A schematic illustration of the major phases of the proposed Tile-X approach. S2) Vertex ordering From G ( V, E ) with n vertices (or reads), we generate a vertex ordering π : V → {1, 2, …, n }, which is a bijective mapping such that the rank of r i is represented by π ( i ). This ordering represents a linear permutation (or a linear ordering) of the input reads. In Section 2.2 , we describe various schemes for generating an ordering. S3) Partitioning Next, using the linear ordering generated in π , we partition the read set into p subsets. Partitioning can be done in multiple ways: one approach is to identify weak links in the ordering and use them as partition boundaries, while another approach ensures uniform partition sizes to maintain balanced workloads in a parallel setting. In our implementation, we adopt the latter strategy to optimize load balancing. Specifically, we divide the ordered reads into evenly sized partitions, ensuring that each subset contains approximately the same number of reads. After partitioning, we update the subsets to ensure the ending read of one partition say P r , is replicated in its successive partition P r +1 if it exists (shown as the “ghost” vertices straddling the partition boundaries of Figure 1 ). This is done so as to maintain contiguity across partitions. S4) Partitioned assembly Next, treating each partition as an individual assembly task, we apply a long read assembler of choice to assemble and produce contigs from each partition. In our implementation and testing, we used Hifiasm [ 15 ]. Note that this strategy to do a partitioned assembly on each partition generated by step S3, has two advantages: a) Even if the linear ordering detected by the vertex ordering has imperfections, the assembly task will ignore that and treat each partition as just a collection of reads to assemble. This makes the assembly process robust to ordering errors. b) Each partition represents an independent task that can allow all partitions to be assembled in parallel. S5) Merge assemblies In a final merge step, we combine the individual assemblies produced by the set of successive partitions. This is achieved by running the assembler once again but only on the output contigs that share long reads between two successive partitions. 2.2 Read ordering There are broadly two categories of read ordering schemes ( Figure 2 ) we explore in this paper. In the first approach, we treat the read ordering problem as a graph-theoretic vertex ordering problem. This allows us to explore various standard vertex-ordering schemes ( Section 2.2.1 ). All these schemes produce an ordering for the entire collection of input reads. Next, with a goal to reduce the inbound computational workload for the downstream partitioned assembly step, we present a sparsification-based approach to the ordering problem that can reduce the number of reads selected as part of the final ordering ( Section 2.2.2 ). Assembly workloads that have read sets generated with a high sequencing coverage are better suited to benefit from this approach. Download figure Open in new tab Figure 2. Different vertex ordering schemes of Tile-X . 2.2.1 Vertex reordering schemes Vertex ordering (or reordering) is a classical problem in graph theory and sparse linear algebra used widely to improve locality in computation [ 17 , 23 , 24 , 25 ]. Intuitively, given an input sparse matrix, the goal is to reorder the rows such that rows sharing nonzeroes in common appear contiguously, effectively concentrating the nonzeros along the main diagonal of the reordered matrix (as shown in the Figure 2 (left)). This reordering formulation also naturally extends to graphs since any graph can be represented as an adjacency matrix (with vertices as rows, and edges as nonzeros). Therefore, reordering is equivalent to renumbering vertices of the graph such that those with shared neighbors in common are contiguously numbered. More formally, this is the minimum linear arrangement (MINLA) problem [ 23 ]: Given a graph G ( V, E ), let π : V → {1, 2, …, | V |} be a bijective mapping of verticeLs to a linear permutuation π (i.e., ordering). Then the linear arrangement score is given by [ 26 ]: L ( G, π ) = ∑ ( i,j )∈ E | π ( i ) − π ( j )|. An optimal ordering π * is one which minimizes the linear arrangement score for the graph. This optimization problem is NP-Hard [ 23 ], and numerous efficient heuristis are used in practice [ 17 ]. In the context of genome assembly, it should be easy to see why reordering can be helpful for ordering the vertices of a read graph. Intuitively, because of sequencing coverage, reads that originate from the same region of the genome are likely to share edges to one another in the corresponding read graph. Therefore generating a linear ordering of the vertices of the graph would approximate the ordering of reads along the target genome. As part of the Tile-X framework, we incorporated three vertex ordering schemes that represent three different classes of methods. Tile-RCM : The Reverse Cuthill-McKee (RCM) [ 18 ] ordering scheme is an efficient greedy heuristic that tries to minimize a measure of the graph’s adjacency matrix bandwidth. Tile-Metis : The Metis ordering is based on a graph partitioner [ 20 ], which uses a min-cut multi-level approach to generate a balanced partitioning of vertices (into a pre-specified number of partitions) and subsequently a traversal by each partition to generate its ordering. Tile-Grappolo : The Grappolo ordering is one that uses the corresponding fast and efficient parallel community detection algorithm [ 19 ] to generate an ordering. Intuitively, the first step clusters the vertices into tightly-knit communities using the modularity metric [ 27 ], and then traverses the set of vertices by each community to generate an ordering. Under community detection, the number of target communities is determined by the algorithm based on the input (i.e., not user-specified). While any vertex ordering scheme can be used here, our choices to incorporate and evaluate these three schemes is based on empirical evidence that these schemes outperform other schemes for general graphs [ 17 ]. However, their application to read graphs is new in this paper. 2.2.2 Sparsified reordering ( Tile-Far ) Problem In this section, we describe a new vertex ordering heuristic called Tile-Far . This new scheme is motivated by a goal to reduce the number of reads included in the final ordering. The underlying problem is a variant of the classical ordering problem. Given a graph G ( V, E ), the goal is to generate a linear ordering π s that covers only a “minimal” subset of reads. If V ′ ⊆ V denotes that subset, then π s is a bijective mapping π s : →{ V ′ 1, 2, …, | V |} ′ . In order to compute V ′ and a corresponding π s , recall that in the Tile-X approach introduced at the start of Section 2.1 , the ordering computed in step S2 is subsequently used to generate a partitioned assembly (steps S3 through S5). Therefore, the choice of the subset V ′ should be such that it is as small as possible (in the interest of performance), while importantly preserving critical overlap information required to generate an accurate assembly. In other words, the goal is to detect a minimum subset V ′ from which it is possible to generate an assembly that can match the quality of any of the non-sparsified schemes. In order to compute such a minimal subset V ′ for sparse ordering, we first observe that a read subset V ′ that corresponds to a small fixed coverage (e.g., 2× or 3 ×) of the target genome should contain sufficient overlap information for assembly. However, the read graph is built using all reads which typically would represent a higher coverage used during sequencing (typically ≥10×). This problem goal is similar to the classical Minimum Tiling Path [ 28 ] which was used in the early 2000s to generate a minimal physical map for sequencing experiments. Approach A potential strategy to generate a sparsified ordering π s is to follow a two-step process of first sparsifying the input graph (from G ( V, E ) to G ′ ( V ′ , E ′ )) and then generating a linear ordering for the V ′ in G ′ . However, this would mean added computational overhead for graph sparsification, which is related to other known NP-Hard problems such as minimum vertex cover [ 29 ] and edge cover [ 30 ]. Instead of such a two-step process, we present here an efficient algorithm, Tile-Far , that directly generates π s from G ( V, E ). Given read graph G ( V, E ) and starting from an empty ordering, the Tile-Far algorithm incrementally grows its ordering by visiting a subset of vertices in V in a certain order and appending them to the current ordering. Initially this traversal starts at a vertex of degree one. In rare instances of a connected component of a graph with no single degree vertices, then the list of all smallest degree vertices in that component are marked as potential “starts” for a traversal. For convenience, we refer to the set of all such start vertices in the entire graph where traversals could start as V S (i.e., V 𝒮 ⊆ V ). Let r i be an arbitrary vertex being visited by the algorithm at any given time. Let N ( r i ) denote the neighbors of r i —i.e., N ( r i ) = { r j | ( i, j ) E }. From r i , Tile-Far tries to greedily find the “farthest” neighbor of r i from N ( r i ) and append it to π s . More formally, let r i and r j be two reads which share a good end-to-end overlap (i.e., semi-global alignment), with the length of their alignment denoted as Span ( r i , r j ). Definition 2.1. The farthest neighbor of a read r i is another read r far ∈ N ( r i ) to which r i has the maximum span—i . e ., r far = arg max j Span ( r i , r j ). In other words, selecting such a farthest neighbor maximizes the ordering’s span over the target genome in the region corresponding to the two reads. Notably, it has the advantage of skipping over other reads that may lie along the way which also overlap with r i due to the depth of sequencing coverage ( C )—thereby generating a sparsification ordering. This idea is illustrated in Figure 3 . Download figure Open in new tab Figure 3. Tile-Far : (a) Long reads r i , r i +1 , r i +2 , r i +3 , r j , and r e spanning overlapping genomic regions; (b) Read graph showing the selection of r j as the farthest neighbor of r i (skipping all other reads along the way). In order to find a farthest neighbor of a given read, without computing alignments and directly from the graph G ( V, E ), we start by focusing on maximal cliques within the graph. Let M ( r i , r j ) denote a subgraph of G ( V, E ) that is also a maximal clique that contains both r i and r j . By definition, each read within M ( r i , r j ) shares overlaps with every other read in that clique. The Tile-Far heuristic identifies a successor r j for read r i by maximizing the following structural gain function: Note that N ( r j ) ⊇ M ( r i , r j ) for any vertex r j . Intuitively, the above structural gain function is a measure of the number of new reads that r i can access through a candidate neighbor r j , that are not already in within its reach in M ( r i , r j ). The more such new reads, the higher the utility of candidate r j to r i in extending the contig assembly on the target genome. While we have posed this approach based on maximal cliques, our algorithm does not explicitly compute these cliques as clique computation is hard and expensive in practice [ 31 ]. In fact, we can observe from Eqn. 1 we only need to estimate the cardinality of the maximal clique size for each ( r i , r j ) pair in Eqn. 1 . Assuming all edges in the input read graph G ( V, E ) are “correct”—i.e., true to overlapping reads on the genome—our estimation function is given by | M ( r i , r j ) |= | N ( r i ) ∩ N ( r j ) |. This correctness assumption is not restrictive in practice as argued below. To save runtime further, when our algorithm reaches a vertex r i , our algorithm lazily calculates this intersection cardinality for each of r i ’s neighbors at that time, and applies the arg max operation to obtain ψ ( r i ). Algorithm 1 summarizes the main steps of our Tile-Far algorithm. As noted above, the structural gain function objective assumes that the edges in the read graph are “true”, i.e., the reads connected via an edge are truly overlapping on the target genome. However, this depends on the precision accuracy of the mapping procedure (step S1), and there is always a risk of placing a chimeric edge between two reads (belonging to two different parts of the genome). To mitigate the risk of creating a chimeric merge as part of the sparsified ordering, we introduce an additional condition to check before identifying the farthest neighbor ψ ( r i ). If the maximum choice neighbor has a | M ( r i , r j ) | below a certain threshold τ , then we instead select the next best choice of neighbor (if one exists) that satisfies this threshold τ . This reduces the chance of exposing an unreliable farthest neighbor and alleviates the risk of creating false merges in the subsequent assembly step. If the read sequencing coverage is C , then we set in our experiments. Algorithm 1 Tile-Far Heuristic Download figure Open in new tab Algorithmic properties Even though the Tile-Far algorithm is a heuristic, there are several provable properties of the algorithm. Collectively these properties serve to highlight the algorithm’s advantages and limitations. Lemma 2.1. The farthest neighbor relationship ψ (.) (as defined in Eqn. 1 ) is not symmetric . Proof . Consider two reads r i and r j which share an edge in G ( V, E ). The choice for the farthest neighbor in Eqn. 1 depends on the degree of the destination vertex, which may be different for the two vertices. Therefore, there is no guarantee that if r j = ψ ( r i ) then r i = ψ ( r j ). Lemma 2.2. Each read will feature in exactly one of the orderings reported by Tile-Far . Proof . The lemma holds because of the visit flag maintained at each vertex by the algorithm. The implications of the above two lemmas is that the Tile-Far heuristic is non-deterministic and can potentially generate different output orderings from the same input. Next we show an important property, about the degree of sparsity that can be expected of Tile-Far . Definition 2.2. An ordering of m reads π t = [ r 1 , r 2 , … r m ] is referred to as a true ordering if the reads cover a contiguous stretch of the target genome, with every successive pair of reads in the ordering truly overlapping . Lemma 2.3. Consider a true ordering of reads π t : [ r i , r i +1 , r i +2 , …, r i + k , r j , r e ] such that r i overlaps with r j but there exists no overlap between reads ( r i , r e ). Then, if the Tile-Far algorithm visits r i then it is likely to identify r j as its farthest neighbor . Proof . Given that π t is a true ordering and given that r i and r j share an overlap, we can expect that all the intermediate reads r i +1 through r i + k also share overlaps with one another and with r i and r j —thereby forming a clique in the read graph G ( V, E ) (as illustrated in Fig. 3 ). Furthermore, since read r i does not overlap with r e , the collection { r i , r i +1 , r i +2 , …, r i + k , r j } form a maximal clique for the vertex pair ( r i , r j ), with size M ( r i , r j ) = k + 2. This also implies that M ( r i , r j ) = M ( r i , r f ) for i + 1≤ f ≤ i + k . Therefore, when the Tile-Far algorithm considers which of its neighbors from r i +1 through r j can be considered farthest, the choice is determined by which of those candidate reads r c maximizes | N ( c ) \ M ( r i , r c ) | (by Eqn. 1 )—which is same as the read that maximizes | N ( r c ) | (since all | M ( r i , r c ) | are the same relative to r i ). We observe here that | N ( r j ) | ≥| N ( r c ) |, over all candidates c . By contradiction, if there were to be an intermediate read r f , where i + 1≤ f ≤ i + k , that has a larger vertex degree that would imply that there has to be at least one additional read (such as r e ) to the right of r f that it overlaps with. But if that is the case, then r j , which is further right of r f in the true ordering would also have to overlap with r e thereby ensuring that | N ( r j )| ≥ | N ( r c )|. Therefore, the Tile-Far algorithm would select r j as ψ ( r i ). The implication of Lemma 2.3 is that the algorithm is likely to skip all the intermediate reads [ r i +1 , r i +2 , …, r i + k ], which corresponds to a significant saving in ordering retention as k increases. 2.2.3 Parallel implementation We have implemented the Tile-X framework including Tile-RCM , Tile-Grappolo , Tile-Metis , and Tile-Far in C/C++ and using the MPI message passing library for communication under the distributed memory model, and OpenMP for shared memory multithreaded parallelism. Owing to space limitations, we skip the inner details of the parallel implementation. Our code is available as open source at https://github.com/Oieswarya/Tile-X . 3 Results and Discussion 3.1 Experimental setup Test inputs For our experiments, we used genome inputs downloaded from the NCBI Gen-Bank [ 32 ], as summarized in Table 1 . We used the Sim-it PacBio HiFi simulator [ 33 ], with a default 10× coverage and read length median of 10Kbp. In addition to simulated reads, we also used two real-world HiFi sequencing datasets, both generated using the PacBio Sequel II system: a caddisfly genome ( H. magnus ) [ 34 ], and a drumfish genome ( N. coibor ) [ 35 ]. Test platform: All experiments were conducted on a distributed memory cluster with 9 compute nodes, each with 64 AMD Opteron™ (2.3GHz) cores and 128 GB DRAM. The nodes are interconnected using 10Gbps Ethernet and share 190TB of ZFS storage. The distributed executions of Tile-X were performed using MPI with up to p = 64 processes (4 compute nodes, each running 16 processes, with 1 thread per process), while the multithreaded executions used 64 threads on a single node of the cluster. For all other the state-of-the-art assemblers, we ran them in their multithreaded mode on 64 threads (mapped to 64 cores) on a single node of the cluster. For all runs, we ran Tile-X with a batch size of 16,384 in the batch assembly step. View this table: View inline View popup Download powerpoint Table 1: Input datasets used in our experiments. All genome inputs were downloaded from NCBI GenBank [ 32 ]. 3.2 Qualitative evaluation We compare the Tile-X methods against other state-of-the-art assemblers including Hifiasm [ 15 ], HiCanu [ 14 ], HiFlye [ 36 ], and GoldRush [ 10 ]. All the quality results for are shown in Table 2 . Our results show that for all inputs Tile-X methods produce comparable or better assembly contiguity (NGA50, NG50, largest alignment) compared to standard tools. This is achieved while maintaining near perfect genome coverage and duplication ratio, and reduced misassemblies (effect of ordering and partitioning in Tile-X ). View this table: View inline View popup Download powerpoint Table 2: Qualitative comparison of the output contigs generated by the different tools on the different inputs. Symbol * indicates that the corresponding runs did not complete within 6 hours; symbol indicates − that the corresponding runs required more than 256 GB of memory which was the system maximum memory. Bold face values show the best results for each input. As the genome size increases, Tile-Grappolo generally outperformed the other methods across most of the metrics. For instance, for H. sapiens , Tile-Grappolo achieved an NGA50 of 34.5Mbp which is 2.1 × longer than Hifiasm . The better results observed for Tile-Grappolo (relative to other vertex ordering schemes) is consistent with the relative performance reported on generic graphs in [ 17 ]. Largely this is owing to the rigorous optimization function of modularity that it internally uses, without bounding the sizes or number of communities prior to generation of the ordering. However, it is notable that Tile-Far , despite sparsifying on the read space, still produced quality comparable to the other Tile-X methods. In general, despite the minor deviations in quality, all Tile-X schemes performed comparably, and in many cases also outperformed the state-of-the-art assemblers. Among the existing assemblers, Hifiasm in general produced the best outputs. However, in almost all cases (except D. busckii ), the Tile-X implementations produce better quality compared to Hifiasm , demonstrating the positive effect of ordering prior to using a standalone assembler. The Tile-X methods also produced less misassemblies in multiple cases, demonstrating the value of partitioning after ordering, which would reduce ambiguity in the subsequent partitioned assembly step. 3.3 Performance evaluation Table 3 shows the parallel performance for three of the largest inputs comparing all the tools (results for all inputs is provided in the supplementary materials in Table S1). We see that Tile-X consistently demonstrates significant speedups over the state-of-the-art assemblers, and among the Tile-X tools, Tile-Far is the fastest, demonstrating the value of sparsification even for a small coverage inputs (10×). For instance for H. sapiens , Tile-Far is 1.9× faster than Hifiasm . View this table: View inline View popup Download powerpoint Table 3: Performance comparison of the output contigs generated by the different tools on the three larger inputs (simulated). Symbol *indicates that the corresponding runs did not complete within 6 hours; symbol − indicates that the corresponding runs required more than 252GB of memory which was the system maximum memory. Bold face values show the best results for each input. On average Tile-Far was 1.9× to 3.5× faster than fastest state-of-the-art tool for any input. The factor improvements with Tile-Far correlate to the sparsification factors achieved by Tile-Far (data not shown due to space). Table 3 also shows the memory consumption of all the tools. Here again, Tile-X outperforms the other tools, demonstrating the value of breaking down the input through ordering into partitions. Furthermore, among the Tile-X schemes, Tile-Far consumes the least memory, i.e., between 2.6× and 3.3× less than Hifiasm —demonstrating the value of sparsification. We note that both the runtime and memory performance of the Tile-X implementations can further improve as we increase the number of processors (due to their distributed memory implementation). Impact of sparsification on high coverage inputs We note here that the true space saving impact of the sparsification idea in Tile-Far can be realized when we start increasing the sequencing coverage. To demonstrate this point, we ran Tile-Far over inputs obtained using increasing coverage, ranging from 4 to 30× on the H. aestivaria input. Results are shown in Table 4 . The results show that the qualitative gains plateau out after 10× coverage. However, neither the runtime nor the memory increases with Tile-Far beyond the 9× coverage setting. In fact, with increasing coverage, the sparsification rate only improves (i.e., fraction of vertices retained decreases). These results show the effectiveness of sparsification to reduce redundancy as shown in the property of Lemma 2.3. View this table: View inline View popup Download powerpoint Table 4: Quality and performance evaluation of running Tile-Far with different coverages of long reads on input H. aestivaria . Vertex sparsification rate is measured as the percentage of reads retained in the sparsified ordering relative to the total input. Bold face values show the best results for each metric. 3.4 Real-world dataset evaluation We evaluated the performance of Tile-X on two real-world HiFi sequencing datasets as shown in Table 5 . In terms of assembly quality, Tile-X showed significant improvements over state-of-the-art assemblers. For the H. magnus dataset, Tile-RCM achieved a 1.2× improvement in N50 over Hifiasm , and a 18.1× improvement over HiFlye . For the input N. coibor , Tile-Grappolo outperformed Hifiasm by 1.3× in N50. These results highlight the quality improvements that Tile-X provides in real-world applications, demonstrating its potential as a powerful tool for large-scale genome assembly. View this table: View inline View popup Download powerpoint Table 5: Real-world long read inputs analysis: Quality comparison of the output contigs generated by the different tools on two real-world inputs. Symbol − indicates that the corresponding runs required more than 252GB of memory, which was the system maximum memory. Boldface values show the best results for the given input. 4 Conclusion In this paper, we revisited the long read assembly problem through the lens of read reordering. We presented Tile-X , a suite of algorithms that use various ordering schemes, to achieve both performance and qualitative gains. We also proposed a new variant of ordering that uses sparsification. Our findings indicate that (a) ordering helps reduce the computational burden of assembly for state-of-the-art assemblers; and (b) sparsified ordering delivers significant performance gains while preserving quality. Our current work does not harness the full potential of ordering yet—i.e., assembly performance can be improved if we use the pairwise ordering information to output the assembly without using a third party assembler— a direction that is of immediate future interest. Other future directions include: a) introducing a way to control sparsification rate and thereby associated trade-offs; b) providing qualitative guarantees with ordering for repetitive regions; and c) applying Tile-X on long read data sets obtained through a range of sequencing technologies. Disclosure of Interests The authors have no competing interests to declare that are relevant to the content of this article. Acknowledgements This research was supported in parts by NSF grants CCF 1919122 and CCF 2316160. References [1]. ↵ Wenger , A. M. et al. Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome . Nature biotechnology 37 , 1155 – 1162 ( 2019 ). OpenUrl CrossRef PubMed [2]. ↵ Deamer , D. , Akeson , M. & Branton , D. Three decades of nanopore sequencing . Nature biotechnology 34 , 518 – 524 ( 2016 ). OpenUrl CrossRef PubMed [3]. ↵ Liu , Y. et al. Comparison of structural variants detected by pacbio-clr and ont sequencing in pear . BMC genomics 23 , 830 ( 2022 ). OpenUrl CrossRef PubMed [4]. ↵ Liu , L. , Yang , Y. , Deng , Y. & Zhang , T. Nanopore long-read-only metagenomics enables complete and high-quality genome reconstruction from mock and complex metagenomes . Microbiome 10 , 209 ( 2022 ). OpenUrl CrossRef PubMed [5]. ↵ Hon , T. et al. Highly accurate long-read hifi sequencing data for five complex genomes . Scientific data 7 , 399 ( 2020 ). OpenUrl CrossRef PubMed [6]. ↵ Mason , C. E. & Elemento , O. Faster sequencers, larger datasets, new challenges ( 2012 ). [7]. ↵ Dohm , J. C. , Peters , P. , Stralis-Pavese , N. & Himmelbauer , H. Benchmarking of long-read correction methods . NAR Genomics and Bioinformatics 2 , qaa037 ( 2020 ). OpenUrl [8]. ↵ Luo , J. et al. Systematic benchmarking of nanopore q20+ kit in sars-cov-2 whole genome sequencing . Frontiers in microbiology 13 , 973367 ( 2022 ). OpenUrl CrossRef PubMed [9]. ↵ Rautiainen , M. & Marschall , T. Mbg: Minimizer-based sparse de bruijn graph construction . Bioinformatics 37 , 2476 – 2478 ( 2021 ). OpenUrl CrossRef PubMed [10]. ↵ Wong , J. et al. Linear time complexity de novo long read genome assembly with goldrush . Nature Communications 14 , 2906 ( 2023 ). OpenUrl CrossRef PubMed [11]. ↵ Xiao , C.-L. et al. Mecat: fast mapping, error correction, and de novo assembly for single-molecule sequencing reads . nature methods 14 , 1072 – 1074 ( 2017 ). OpenUrl CrossRef PubMed [12]. ↵ Chin , C.-S. et al. Phased diploid genome assembly with single-molecule real-time sequencing . Nature methods 13 , 1050 – 1054 ( 2016 ). OpenUrl CrossRef PubMed [13]. ↵ Chin , C.-S. & Khalak , A. Human genome assembly in 100 minutes . BioRxiv 705616 ( 2019 ). [14]. ↵ Nurk , S. et al. Hicanu: accurate assembly of segmental duplications, satellites, and allelic variants from high-fidelity long reads . Genome research 30 , 1291 – 1305 ( 2020 ). OpenUrl Abstract / FREE Full Text [15]. ↵ Cheng , H. , Concepcion , G. T. , Feng , X. , Zhang , H. & Li , H. Haplotype-resolved de novo assembly using phased assembly graphs with hifiasm . Nature methods 18 , 170 – 175 ( 2021 ). OpenUrl CrossRef PubMed [16]. ↵ An , X. et al. Boa: A partitioned view of genome assembly . Iscience 25 ( 2022 ). [17]. ↵ Barik , R. , Minutoli , M. , Halappanavar , M. , Tallent , N. R. & Kalyanaraman , A. Vertex reordering for real-world graphs and applications: An empirical evaluation . In 2020 IEEE International Symposium on Workload Characterization (IISWC) , 240 – 251 ( IEEE , 2020 ). [18]. ↵ Cuthill , E. & McKee , J. Reducing the bandwidth of sparse symmetric matrices . In Proceedings of the 1969 24th national conference , 157 – 172 ( 1969 ). [19]. ↵ Lu , H. , Halappanavar , M. & Kalyanaraman , A. Parallel heuristics for scalable community detection . Parallel Computing 47 , 19 – 37 ( 2015 ). OpenUrl CrossRef [20]. ↵ Karypis , G. & Kumar , V. Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices ( 1997 ). [21]. ↵ Rahman , T. , Bhowmik , O. & Kalyanaraman , A. An efficient parallel sketch-based algorithm for mapping long reads to contigs . In 2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , 157 – 166 ( IEEE , 2023 ). [22]. ↵ Rahman , T. , Bhowmik , O. & Kalyanaraman , A. An efficient parallel sketch-based algorithmic workflow for mapping long reads . IEEE/ACM Transactions on Computational Biology and Bioinformatics ( 2024 ). [23]. ↵ Garey , M. R. & Johnson , D. S. Computers and intractability , vol. 174 ( freeman San Francisco , 1979 ). [24]. ↵ Liu , J. W. Reordering sparse matrices for parallel elimination . Parallel computing 11 , 73 – 91 ( 1989 ). OpenUrl CrossRef [25]. ↵ Pinar , A. & Heath , M. T. Improving performance of sparse matrix-vector multiplication . In Proceedings of the 1999 ACM/IEEE conference on Supercomputing, 30–es ( 1999 ). [26]. ↵ Petit , J. Experiments on the minimum linear arrangement problem . Journal of Experimental Algorithmics (JEA) 8 ( 2003 ). [27]. ↵ Newman , M. E. Modularity and community structure in networks . Proceedings of the national academy of sciences 103 , 8577 – 8582 ( 2006 ). OpenUrl Abstract / FREE Full Text [28]. ↵ Engler , F. W. , Hatfield , J. , Nelson , W. & Soderlund , C. A. Locating sequence on FPC maps and selecting a minimal tiling path . Genome Research 13 , 2152 – 2163 ( 2003 ). OpenUrl Abstract / FREE Full Text [29]. ↵ Hartmanis , J. Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson) . Siam Review 24 , 90 ( 1982 ). OpenUrl CrossRef [30]. ↵ Papadimitriou , C. H. & Steiglitz , K. Combinatorial optimization: algorithms and complexity (Courier Corporation , 1998 ). [31]. ↵ Bomze , I. M. , Budinich , M. , Pardalos , P. M. & Pelillo , M. The maximum clique problem . Handbook of Combinatorial Optimization: Supplement Volume A 1 – 74 ( 1999 ). [32]. ↵ Benson , D. A. et al. Genbank . Nucleic acids research 41 , D36 – D42 ( 2012 ). OpenUrl CrossRef PubMed [33]. ↵ Dierckxsens , N. , Li , T. , Vermeesch , J. R. & Xie , Z. A benchmark of structural variation detection by long reads through a realistic simulated model . Genome biology 22 , 1 – 16 ( 2021 ). OpenUrl CrossRef PubMed [34]. ↵ Hotaling , S. , Wilcox , E. R. , Heckenhauer , J. , Stewart , R. J. & Frandsen , P. B. Highly accurate long reads are crucial for realizing the potential of biodiversity genomics . BMC genomics 24 , 117 ( 2023 ). OpenUrl CrossRef PubMed [35]. ↵ Yekefenhazi , D. et al. Chromosome-level genome assembly of nibea coibor using pacbio hifi reads and hi-c technologies . Scientific Data 9 , 670 ( 2022 ). OpenUrl CrossRef PubMed [36]. ↵ Kolmogorov , M. , Yuan , J. , Lin , Y. & Pevzner , P. A. Assembly of long, error-prone reads using repeat graphs . Nature biotechnology 37 , 540 – 546 ( 2019 ). OpenUrl CrossRef PubMed View the discussion thread. Back to top Previous Next Posted April 25, 2025. Download PDF Supplementary Material Email Thank you for your interest in spreading the word about bioRxiv. NOTE: Your email address is requested solely to identify you as the sender of this article. Your Email * Your Name * Send To * Enter multiple addresses on separate lines or separate them with commas. You are going to email the following Tile-X: A vertex reordering approach for scalable long read assembly [Proceedings] Message Subject (Your Name) has forwarded a page to you from bioRxiv Message Body (Your Name) thought you would like to see this page from the bioRxiv website. Your Personal Message CAPTCHA This question is for testing whether or not you are a human visitor and to prevent automated spam submissions. Share Tile-X: A vertex reordering approach for scalable long read assembly [Proceedings] Oieswarya Bhowmik , Ananth Kalyanaraman bioRxiv 2025.04.21.649853; doi: https://doi.org/10.1101/2025.04.21.649853 Share This Article: Copy Citation Tools Tile-X: A vertex reordering approach for scalable long read assembly [Proceedings] Oieswarya Bhowmik , Ananth Kalyanaraman bioRxiv 2025.04.21.649853; doi: https://doi.org/10.1101/2025.04.21.649853 Citation Manager Formats BibTeX Bookends EasyBib EndNote (tagged) EndNote 8 (xml) Medlars Mendeley Papers RefWorks Tagged Ref Manager RIS Zotero Tweet Widget Facebook Like Google Plus One Subject Area Bioinformatics Subject Areas All Articles Animal Behavior and Cognition (7624) Biochemistry (17651) Bioengineering (13873) Bioinformatics (41887) Biophysics (21424) Cancer Biology (18566) Cell Biology (25465) Clinical Trials (138) Developmental Biology (13365) Ecology (19871) Epidemiology (2067) Evolutionary Biology (24293) Genetics (15591) Genomics (22478) Immunology (17715) Microbiology (40331) Molecular Biology (17150) Neuroscience (88492) Paleontology (666) Pathology (2828) Pharmacology and Toxicology (4817) Physiology (7635) Plant Biology (15114) Scientific Communication and Education (2044) Synthetic Biology (4286) Systems Biology (9817) Zoology (2268)