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.
GCF_000005845.2 (Assembly Name: ASM584v2)U00096.3 /
NC_000913.3GCF_000005845.2_ASM584v2_genomic.fnaReference 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.
The baseline execution consists of the following processing stages:
$)
is appended to the sequence.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.
The application exhibits several parallel computing characteristics:
Performance bottlenecks include memory bandwidth constraints associated with traversing large tables, potential thread load imbalance due to variable search depths, and the computational cost of Suffix Array sorting on multi-gigabase datasets.