Scripts to reproduce results: "Columba: Fast Approximate Pattern Matching with Optimized Search Schemes"

Reproducibility Material for the Paper "Columba: Fast Approximate Pattern Matching with Optimized Search Schemes" This repository contains the scripts, datasets, and configuration files required to reproduce the benchmarking results from our paper Columba: Fast Approximate Pattern Matching with Optimized Search Schemes. The focus is on evaluating the performance of Columba and several competing mappers across a diverse set of scenarios, including mapping to the human reference genome, bacterial pan-genomes, and human pangenomes of varying sizes. Getting Started Before running any benchmarks, install the tools, download required datasets and build indexes by executing the scripts below. These scripts will set up the expected directory structure and ensure all tools are available on your system.It does assume CMake and the dependencies of the tools are installed (zlib, seqtk (for ropebwt3)). Note that if seqtk is not installed ropebwt3 will not be able to locate the occurrences. Note that you need sufficient storage to download all data (7.2GB for the human reference index and reads, 53GB for the bacterial pangenome, and 900GB for the human pangenomes). Note that you need at least 70GB of memory to successfully run build_indexes_human.sh and that it may take some time. Note that you need at least 500GB of memory to successfully run bash build_indexes_bact.sh and that it will take longer than the human indexes. Idem for the human pangenomes. # Install required tools (Columba, BWA, Yara, etc.) bash install_tools.sh # Download reference genomes and read datasets bash download_data.sh # Build indexesbash build_indexes_human.shbash build_indexes_bact.shbash build_indexes_human_pangenome.sh 1. Human Reference Genome Benchmarks The script run_benchmarks_human.sh evaluates mapping accuracy and runtime for single-end and paired-end reads against the linear human reference genome (GRCh38). Tools evaluated: Columba (0, 2, 4, 6, and 8% error rates) Yara (0, 2, 4, 6, and 8% error rates) BWA-ALN (0, 2, 4, 6, and 8% error rates) BWA-MEM(2) (2% error rate) Bowtie1 (up to 3 errors) Bowtie2 (with and without --very-sensitive) The script benchmarks multiple error rates and extracts timing/memory statistics for each run 10 times. Results are saved in output_human/ and summarized in: summary_human_SE.txt (single-end) summary_human_PE.txt (paired-end) To run the benchmark: bash run_benchmarks_human.sh To analyze the output SAM files: bash analyze_human.sh 2. HLA-Typing We refer to the instruction in instructions_HLA.txt. 3. Bacterial Pan-Genome Benchmarks The script run_benchmarks_bact.sh benchmarks various tools on a concatenated bacterial pan-genome using single-end reads. Both single-threaded and multi-threaded performance are evaluated. Tools evaluated: Columba (vanilla, RLC) — 0, 2, 4, 6, and 8% error rates Yara — 0, 2, 4, 6, and 8% error rates BWA-ALN — 0, 2, 4, 6, and 8% error rates BWA-MEM ropeBWT3 For the multi-threaded benchmark, the maximum error rate for lossless tools is fixed at 6%, and the script loops over thread counts 1–64 to assess scalability. Each benchmark is run 10 times. Results are saved in output_bact/ and summarized in: summary_bact.txt (single-threaded) summary_bact_multi.txt (multi-threaded) To run the benchmark: bash run_benchmarks_bact.sh To analyze the SAM output: bash analyze_bact.sh 4. Human Pangenome Benchmarks The script run_benchmarks_human_pangenome.sh evaluates mapping to pangenomes of different sizes (2 to 64 haplotypes) built from HPRC assemblies. Each pangenome is benchmarked independently to assess performance scaling. Tools included: Columba (vanilla, RLC) (6% error rate) ropeBWT3 For each pangenome size, the script benchmarks 10 iterations using a fixed error rate and single-threaded execution. Results are stored in subdirectories of output_human_pangenome/ and summarized in summary_human_pangenome.txt. To run: bash run_benchmarks_human_pangenome.sh To analyze the SAM/PAF output: python3 compare_sam_paf.py . Where and are the respective outputs form Columba and ropeBWT3. Structure install_tools.sh: installs all required mapping tools download_data.sh: downloads all necessary datasets download_data_*.sh: downloads the respective dataset. extract_data*.sh: Extracts the necessary datasets build_indexes_*.sh: builds the necessary indexes run_benchmarks_*.sh: benchmark scripts for each experiment functions.sh: shared utility functions for benchmarking analyze_*.sh : Will automatically compare SAM output of Columba to Yara and BWA-MEM extract_timings.py, compare_sam_paf.py, compare_sam.py, inspect_*.py, extract_sub_from_fasta.py, number_reads_per_alignment.py: postprocessing scripts instructions_HLA.txt: instructions for the HLA experiment Human_Pangenome_Accession.txt: The used accession numbers for the human pan-genome Contact For questions or issues, please contact the authors via the corresponding author listed in the paper