BWT construction and search at the terabase scale
Motivation: Burrows-Wheeler Transform (BWT) is a common component in full-text indices. Initially developed for data compression, it is particularly powerful for encoding redundant sequences such as pangenome data. However, BWT construction is resource intensive and hard to be parallelized, and many methods for querying large full-text indices only report exact matches or their simple extensions. These limitations have hampered the biological applications of full-text indices. Results: We developed ropebwt3 for efficient BWT construction and query. Ropebwt3 indexed 320 assembled human genomes in 65 hours and indexed 7.3 terabases of commonly studied bacterial assemblies in 26 days. This was achieved using up to 170 gigabytes of memory at the peak without working disk space. Ropebwt3 can find maximal exact matches and inexact alignments under affine-gap penalties, and can retrieve similar local haplotypes matching a query sequence. It demonstrates the feasibility of full-text indexing at the terabase scale. Availability and implementation: https://github.com/lh3/ropebwt3
Code (1)
Tasks
Data CompressionSimilar Papers 제목 키워드 기반
Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search
Approximate Nearest Neighbor Search (ANNS) is essential for modern data-driven applications that require efficient retrieval of top-k results from massive vector databases. Although existing graph-based ANNS algorithms a…
SchedulingPaReNeRF: Toward Fast Large-scale Dynamic NeRF with Patch-based Reference
With photo-realistic image generation Neural Radiance Field (NeRF) is widely used for large-scale dynamic scene reconstruction as autonomous driving simulator. However large-scale scene reconstruction still suffers f…
Autonomous DrivingDecoderImage GenerationImage Reconstruction+2Colmap-PCD: An Open-source Tool for Fine Image-to-point cloud Registration
State-of-the-art techniques for monocular camera reconstruction predominantly rely on the Structure from Motion (SfM) pipeline. However, such methods often yield reconstruction outcomes that lack crucial scale informatio…
Image to Point Cloud RegistrationPoint Cloud RegistrationSOAR: Scale Optimization for Accurate Reconstruction in NVFP4 Quantization
NVFP4 has recently emerged as an efficient 4-bit microscaling format for large language models (LLMs), offering superior numerical fidelity with native hardware support. However, existing methods often yield suboptimal p…
Relative NN-Descent: A Fast Index Construction for Graph-Based Approximate Nearest Neighbor Search
Approximate Nearest Neighbor Search (ANNS) is the task of finding the database vector that is closest to a given query vector. Graph-based ANNS is the family of methods with the best balance of accuracy and speed for mil…
graph construction