# 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
* **Organism**: *Escherichia coli* str. K-12 substr. MG1655
* **Repository**: National Center for Biotechnology Information (NCBI) RefSeq Database
* **RefSeq Assembly Accession**: `GCF_000005845.2` (Assembly Name: `ASM584v2`)
* **GenBank Accession**: `U00096.3` / `NC_000913.3`
* **File Name**: `GCF_000005845.2_ASM584v2_genomic.fna`

**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 ($SA$) 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]$.
4. **FM-Index Table Building**:
   * **$C$-Table**: Cumulative offsets are computed for the alphabet symbols ($\{\$, A, C, G, T\}$).
   * **$Occ$-Table**: An occurrence matrix is built to record character frequencies in the BWT prefix up to each position.
5. **Backward Search Matching**: For a query string $P$ of length $m$:
   * An initial Suffix Array interval $[L, R]$ is established using the $C$-table for character $P[m-1]$.
   * The range is updated iteratively from right to left for $i = m-2$ down to $0$:
     $$L_{new} = C[P[i]] + Occ(P[i], L)$$
     $$R_{new} = C[P[i]] + Occ(P[i], R + 1) - 1$$
   * If $L \le R$, the number of matching occurrences is calculated as $R - L + 1$.

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:

* **Query-Level Parallelism**: Individual query pattern searches are independent and are distributed across CPU threads using OpenMP.
* **Vectorization (SIMD)**: Fixed-alphabet table lookups and updates can be vectorized using SIMD instructions.
* **Parallel Preprocessing**: Initialization loops during BWT and occurrence matrix construction are partitioned across threads.

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