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

Traditional long read assembly relies on computing overlaps between reads, followed by contig construction. Inherent to this process is the subproblem of ordering reads by their (unknown) genomic positions of origin-a challenge current assemblers do not explicitly address. Instead, read ordering becomes available only after assembly completes. We posit that computing a reliable read ordering beforehand, even if imperfect, can significantly reduce the computational burden of assembly, preserve quality, and enable scalable parallelization. We present Tile-X, a graph-theoretic approach that builds an overlap graph, then reorders the reads using vertex reordering techniques, and finally performs parallel partitioned assembly. We explore both standard reordering schemes (Tile-RCM, Tile-Metis, and Tile-Grappolo) and a custom heuristic (Tile-Far) that reduce redundancy by selecting a minimal informative subset of reads. On multiple real and simulated PacBio high-fidelity (HiFi) datasets, Tile-X improves NGA50 up to 2.1× while reducing runtime and memory usage by up to 3.5× and 3.3×, respectively.