# lh3/bwa architecture

> Architecture diagram of the GitHub repository lh3/bwa, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-04-11). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/lh3/bwa
- Repository: https://github.com/lh3/bwa

## Overview

##### Main Components
- (a) Command-Line Interface (CLI) Entry Point: Represent the main executable (main.c) and its argument parsing. This is where the user invokes different sub-commands (e.g., index, mem, aln, samse/sampe).
- (b) Indexing Engine: Highlight the FM-index construction portion. Files like QSufSort.c/h and bwtindex.c indicate the indexing step, where the reference genome is processed and the FM-index is built.
- BWA-backtrack (handling shorter Illumina sequences).
- BWA-SW (for longer but locally aligned sequences).
- BWA-MEM (for longer reads and recommended in most cases).
Different source files (e.g., bwa-mem.c, bwa-mem.h, bwtaln.c, bwtaln.h) support these modules.
- (d) Utility and Helper Libraries: Mark out components for common data structures and algorithms. For instance, the kbtree, khash, kstring, kseq, and ksort libraries are contained in separate source (and header) files used by multiple components.
- (e) Auxiliary Tools and Scripts: The bwakit directory contains post-processing scripts, additional helper programs (e.g., run-HLA, typeHLA.js, and other helper scripts) which enhance or augment the basic alignment functionalities.
- (f) Build and Infrastructure: Although not part of runtime, include a component for build and continuous integration (e.g., Makefile, .github/workflows/ci.yaml), which illustrates the development lifecycle.

##### Relationships and Interactions
- The CLI layer (main.c) accepts user commands and directs them to appropriate sub-systems (indexing or one of the alignment engines).
- When using the index command, the flow moves from reading a reference genome file to constructing the FM-index (which uses QSufSort, BWT-specific modules) and then outputs the index data.
- For alignment commands, data flows from the input FASTA/FASTQ files through the selected alignment engine which consults the FM-index data structure built earlier. Each algorithm might invoke shared utilities for memory management, multi-threading (e.g., kthread.c), and common data structure operations.
- The auxiliary tools (found in bwakit) interface with the main BWA tool either by being invoked as supplementary commands or as post-processing scripts to handle specific tasks (e.g., HLA typing, ALT contig post-processing).

##### Architectural Patterns and Design Principles
- Modular Design: The division into multiple smaller, function-specific modules (indexing, different aligners, utilities) aids separation of concerns and reuse.
- Command Abstraction: The CLI parses commands and leverages sub-components depending on the chosen algorithm.
- Reusability & Extensibility: Multiple utilities (e.g., k* libraries) and helper scripts show that the project is designed to be extended (for instance, bwakit builds on the core functionality for platform-specific or extended functionalities).

##### Relevant Technologies and Dependencies
- Programming Language: C (with Makefile used for building).
- External Library: zlib is the only required dependency.
- Platform-Specific: The project is designed to be compiled on systems supporting GNU-style builds, and there are precompiled binaries in the bwakit package.
- Source Control & CI: Presence of a .github/workflows/ci.yaml indicates integration with GitHub Actions for testing and continuous integration.

## Diagram (Mermaid)

```mermaid
flowchart TD
    subgraph "CLI Layer"
        CLI["CLI Entry Point\n(main.c)"]:::cli
    end

    subgraph "Core Processing"
        IDX["Indexing Engine\n(QSufSort, bwtindex)"]:::core
        BA["BWA-backtrack Engine\n(bwa, bwtaln)"]:::core
        BS["BWA-SW Engine\n(bwtsw2 modules)"]:::core
        BM["BWA-MEM Engine\n(bwamem)"]:::core
    end

    subgraph "Shared Utilities"
        UTIL["Utility Libraries\n(kbtree, khash, kseq, ksort, kstring, kthread, etc.)"]:::util
    end

    subgraph "Auxiliary Tools"
        AUX["Auxiliary Tools & Scripts\n(bwakit)"]:::aux
    end

    subgraph "Build & CI"
        BUILD["Build & Infrastructure\n(Makefile, .github/workflows/ci.yaml)"]:::build
    end

    subgraph "External Dependencies"
        ZLIB["zlib Library"]:::external
    end

    %% Data Flow
    CLI -->|"invokes:index"| IDX
    CLI -->|"invokes:align"| BA
    CLI -->|"invokes:align"| BS
    CLI -->|"invokes:align"| BM

    IDX -->|"producesFM-index"| BA
    IDX -->|"producesFM-index"| BS
    IDX -->|"producesFM-index"| BM

    BA ---|"uses"| UTIL
    BS ---|"uses"| UTIL
    BM ---|"uses"| UTIL
    IDX ---|"uses"| UTIL

    AUX -->|"postprocesses"| CLI
    AUX -->|"enhances"| BM

    BUILD ---|"build/CI"| CLI
    BUILD ---|"build/CI"| IDX
    BUILD ---|"build/CI"| BA
    BUILD ---|"build/CI"| BS
    BUILD ---|"build/CI"| BM
    BUILD ---|"build/CI"| AUX

    UTIL ---|"compression"| ZLIB

    %% Click Events
    click CLI "https://github.com/lh3/bwa/blob/master/main.c"
    click IDX "https://github.com/lh3/bwa/blob/master/QSufSort.c"
    click IDX "https://github.com/lh3/bwa/blob/master/QSufSort.h"
    click IDX "https://github.com/lh3/bwa/blob/master/bwtindex.c"
    click BA "https://github.com/lh3/bwa/blob/master/bwa.c"
    click BA "https://github.com/lh3/bwa/blob/master/bwa.h"
    click BA "https://github.com/lh3/bwa/blob/master/bwtaln.c"
    click BA "https://github.com/lh3/bwa/blob/master/bwtaln.h"
    click BS "https://github.com/lh3/bwa/blob/master/bwtsw2_main.c"
    click BS "https://github.com/lh3/bwa/blob/master/bwtsw2_aux.c"
    click BS "https://github.com/lh3/bwa/blob/master/bwtsw2_chain.c"
    click BS "https://github.com/lh3/bwa/blob/master/bwtsw2_core.c"
    click BS "https://github.com/lh3/bwa/blob/master/bwtsw2_pair.c"
    click BS "https://github.com/lh3/bwa/blob/master/bwtsw2.h"
    click BM "https://github.com/lh3/bwa/blob/master/bwamem.c"
    click BM "https://github.com/lh3/bwa/blob/master/bwamem.h"
    click BM "https://github.com/lh3/bwa/blob/master/bwamem_extra.c"
    click BM "https://github.com/lh3/bwa/blob/master/bwamem_pair.c"
    click UTIL "https://github.com/lh3/bwa/blob/master/kbtree.h"
    click UTIL "https://github.com/lh3/bwa/blob/master/khash.h"
    click UTIL "https://github.com/lh3/bwa/blob/master/kseq.h"
    click UTIL "https://github.com/lh3/bwa/blob/master/ksort.h"
    click UTIL "https://github.com/lh3/bwa/blob/master/kstring.c"
    click UTIL "https://github.com/lh3/bwa/blob/master/kstring.h"
    click UTIL "https://github.com/lh3/bwa/blob/master/kthread.c"
    click UTIL "https://github.com/lh3/bwa/blob/master/kvec.h"
    click AUX "https://github.com/lh3/bwa/tree/master/bwakit"
    click AUX "https://github.com/lh3/bwa/blob/master/README.md"
    click AUX "https://github.com/lh3/bwa/blob/master/bwa-postalt.js"
    click AUX "https://github.com/lh3/bwa/tree/master/run-HLA"
    click AUX "https://github.com/lh3/bwa/tree/master/run-bwamem"
    click AUX "https://github.com/lh3/bwa/tree/master/run-gen-ref"
    click AUX "https://github.com/lh3/bwa/blob/master/typeHLA-selctg.js"
    click AUX "https://github.com/lh3/bwa/blob/master/typeHLA.js"
    click AUX "https://github.com/lh3/bwa/blob/master/typeHLA.sh"
    click BUILD "https://github.com/lh3/bwa/tree/master/Makefile"
    click BUILD "https://github.com/lh3/bwa/blob/master/.github/workflows/ci.yaml"

    %% Styles
    classDef cli fill:#f9c,stroke:#333,stroke-width:2px;
    classDef core fill:#bbf,stroke:#333,stroke-width:2px;
    classDef util fill:#cfc,stroke:#333,stroke-width:2px;
    classDef aux fill:#fc9,stroke:#333,stroke-width:2px;
    classDef build fill:#ff9,stroke:#333,stroke-width:2px;
    classDef external fill:#ddd,stroke:#333,stroke-width:2px,stroke-dasharray:5 5;
```
