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

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Traditional long read assembly methods face challenges in ordering DNA reads, often delaying this step until after assembly.
• This inherent difficulty increases computational burden and can impact assembly quality and scalability.

Purpose of the Study:

• To introduce Tile-X, a novel graph-theoretic approach for pre-assembly read ordering.
• To demonstrate that upfront read ordering can enhance genome assembly efficiency, quality, and parallelization.

Main Methods:

• Developed Tile-X, a method utilizing overlap graphs and vertex reordering techniques.
• Explored standard reordering schemes (Tile-RCM, Tile-Metis, Tile-Grappolo) and a custom heuristic (Tile-Far) for read selection.
• Implemented parallel partitioned assembly following read reordering.

Main Results:

• Tile-X improved NGA50 (a measure of assembly quality) by up to 2.1× on PacBio HiFi datasets.
• Achieved reductions in runtime (up to 3.5×) and memory usage (up to 3.3×).

Conclusions:

• Pre-assembly read ordering using Tile-X offers significant advantages over traditional methods.
• Tile-X enables more efficient, accurate, and scalable genome assembly, particularly for large datasets.