Burrows-Wheeler Transform and FM-Index DNA Pattern Search

Problem

An exact DNA pattern search is implemented using the Burrows-Wheeler Transform (BWT) and the FM-Index. The target dataset is the Escherichia coli K-12 MG1655 bacterial genome in FASTA format (GCF_000005845.2_ASM584v2_genomic.fna, containing 4,641,652 base pairs).

Given a reference genome and a batch of short DNA query reads (e.g., 10,000 queries of length 20 bp), the number of occurrences of each query string within the genome is calculated. Substring pattern matching using the BWT and FM-Index is a core operation in biological sequence alignment tools, such as Bowtie and BWA.

The baseline program is written in standard C++ without external library dependencies. Parameters are controlled via command-line arguments: * FASTA file path * Number of query reads * Query read length

The program measures execution time (in milliseconds) and search throughput (queries per second), and performs verification checks against a naive string search.

Data Source & Reference

Reference Citation: > National Center for Biotechnology Information (NCBI). Escherichia coli str. K-12 substr. MG1655 complete genome, NCBI RefSeq Assembly Accession GCF_000005845.2, GenBank Accession U00096.3, Bethesda, MD, USA, 2013.

How the Algorithm Works

The baseline execution consists of the following processing stages:

  1. FASTA Parsing: The FASTA file is read, non-ACGT characters are filtered out, and a sentinel character ($) is appended to the sequence.
  2. Suffix Array Construction: A Suffix Array (SASA) is generated by lexicographically sorting all suffix positions of the text.
  3. BWT String Generation: The Burrows-Wheeler Transform string is constructed using BWT[i]=Text[SA[i]−1]BWT[i] = Text[SA[i] - 1].
  4. FM-Index Table Building:
  5. Backward Search Matching: For a query string PP of length mm:

The program incorporates range tracking for sample queries, correctness verification against std::string::find, and an OpenMP parallel loop (#pragma omp parallel for) for batch query execution.

Parallelism and Bottlenecks

The application exhibits several parallel computing characteristics:

Performance bottlenecks include memory bandwidth constraints associated with traversing large OccOcc tables, potential thread load imbalance due to variable search depths, and the computational cost of Suffix Array sorting on multi-gigabase datasets.