架构设计

bwa-rust 采用模块化设计，分为五个主要模块。

整体架构

┌─────────────────────────────────────────────────────────────┐
│                     CLI Layer (main.rs)                      │
│                  clap 命令解析 + 调度                         │
├─────────────┬─────────────┬──────────────┬──────────────────┤
│    io/      │   index/    │    align/    │      util/       │
│  输入输出    │   索引构建   │   比对算法    │     工具函数     │
├─────────────┼─────────────┼──────────────┼──────────────────┤
│  FASTA      │   SA        │  Seed        │  DNA 编码        │
│  FASTQ      │   BWT       │  Chain       │  反向互补        │
│  SAM        │   FM        │  SW/Extend   │                  │
│             │  Builder    │  Candidate   │                  │
│             │             │  MAPQ        │                  │
│             │             │  Pipeline    │                  │
└─────────────┴─────────────┴──────────────┴──────────────────┘

模块详解

`io/` — 输入输出

文件	功能
`fasta.rs`	FASTA 解析：多 contig、自动归一化、空序列检测
`fastq.rs`	FASTQ 解析：4 行制记录、seq/qual 长度校验
`sam.rs`	SAM 输出：header 写入、CIGAR/MAPQ/AS/XS/NM 标签

`index/` — 索引构建

文件	功能	复杂度
`sa.rs`	后缀数组：倍增法构建	O(n log²n)
`bwt.rs`	BWT：从 SA 直接推导	O(n)
`fm.rs`	FM 索引：C 表 + Occ 采样 + 稀疏 SA	O(n) 空间
`builder.rs`	从 FASTA 一键构建入口	-

`align/` — 比对算法

文件	功能
`mod.rs`	`AlignOpt` 配置：打分参数、内存限制
`seed.rs`	SMEM 种子查找，`max_occ` 过滤
`chain.rs`	种子链构建与过滤，`max_chains` 限制
`sw.rs`	带状仿射间隙 Smith-Waterman
`extend.rs`	链扩展 + semi-global refinement
`candidate.rs`	候选收集与去重，clip penalty 排序
`mapq.rs`	MAPQ 估算：得分差比例模型
`pipeline.rs`	批量并行比对 pipeline，`max_alignments` 限制

`util/` — 工具函数

文件	功能
`dna.rs`	DNA 编码：`{0:$, 1:A, 2:C, 3:G, 4:T, 5:N}`、归一化、反向互补

内存防护机制

为防止高度重复序列导致内存爆炸，引入三层限制：

┌────────────────────────────────────────────────────────────┐
│                     三层内存防护                            │
├────────────────────────────────────────────────────────────┤
│                                                            │
│  1. max_occ = 500                                         │
│     跳过 SA 区间 > 500 的种子                              │
│     防止 poly-A 等重复序列展开数万位置                      │
│                         ↓                                  │
│  2. max_chains_per_contig = 5                             │
│     每个 contig 最多提取 5 条链                            │
│     防止重复区域产生过多候选                               │
│                         ↓                                  │
│  3. max_alignments_per_read = 5                           │
│     每个 read 最多输出 5 个比对结果                        │
│     控制最终输出规模                                       │
│                                                            │
└────────────────────────────────────────────────────────────┘

参数	默认值	作用
`max_occ`	500	跳过 SA 区间超过此值的种子
`max_chains_per_contig`	5	每个 contig 最多提取的链数
`max_alignments_per_read`	5	每个 read 最终输出的比对数量上限

索引文件格式

.fm 文件使用 bincode 序列化：

字段	类型	说明
magic	`u64`	`0x424D_4146_4D5F5253` ("BWAFM_RS")
version	`u32`	格式版本（当前为 2）
sigma	`u8`	字母表大小（6）
block	`u32`	Occ 采样块大小
c	`Vec<u32>`	C 表
bwt	`Vec<u8>`	BWT 序列
occ_samples	`Vec<u32>`	Occ 采样表
sa	`Vec<u32>`	SA（完整或稀疏）
sa_sample_rate	`u32`	稀疏采样间隔
contigs	`Vec<Contig>`	contig 元信息
text	`Vec<u8>`	原始编码文本
meta	`Option<IndexMeta>`	构建元数据

对齐流程

FASTQ read
    │
    ├─ 正向归一化 ──────────────┐
    │                          │
    ├─ 反向互补 ──────────────┐│
    │                         ││
    ▼                         ▼▼
┌──────────────────────────────────────┐
│ SMEM 种子查找                         │
│ • max_occ 过滤重复种子                │
└──────────────────────────────────────┘
    │
    ▼
┌──────────────────────────────────────┐
│ 种子链构建与过滤                       │
│ • DP 评分 + 贪心剥离                  │
│ • max_chains_per_contig 限制          │
└──────────────────────────────────────┘
    │
    ▼
┌──────────────────────────────────────┐
│ SW 扩展 + semi-global refinement     │
│ • 生成 CIGAR + NM                    │
└──────────────────────────────────────┘
    │
    ▼
┌──────────────────────────────────────┐
│ 候选去重与排序                         │
│ • clip penalty 排序                  │
└──────────────────────────────────────┘
    │
    ▼
┌──────────────────────────────────────┐
│ 主/次比对输出                          │
│ • max_alignments_per_read 限制        │
└──────────────────────────────────────┘
    │
    ▼
  SAM 行

与 BWA 的差异

方面	BWA (C)	bwa-rust
索引格式	`.bwt/.sa/.pac` 多文件	单一 `.fm` 文件
SA 构造	DC3/IS O(n)	倍增法 O(n log²n)
MEM 查找	双向 BWT	单向 backward_search
链构建	复杂贪心+DP	简化 DP + 贪心剥离
MAPQ	复杂统计模型	简化得分差比例模型
并行	pthread	rayon
配对端	✅ 支持	📋 v0.2.0
BAM 输出	✅ 支持	📋 v0.4.0

技术栈

依赖	用途
Rust 2021 (MSRV 1.70)	系统编程语言
clap 4.5	CLI 参数解析
serde + bincode	索引序列化
rayon	数据并行
criterion	基准测试
tikv-jemallocator	内存分配器

安全性保证

toml

[lints.rust]
unsafe_code = "forbid"  # 全项目禁止 unsafe

零 unsafe 代码：所有内存安全由编译器保证
jemalloc 分配器：非 Windows 平台使用 jemalloc

测试覆盖

类型	数量
单元测试	151
集成测试	11
模块测试	5
文档测试	1
总计	168

架构设计 ​

整体架构 ​

模块详解 ​

io/ — 输入输出 ​

index/ — 索引构建 ​

align/ — 比对算法 ​

util/ — 工具函数 ​

内存防护机制 ​

索引文件格式 ​

对齐流程 ​

与 BWA 的差异 ​

技术栈 ​

安全性保证 ​

测试覆盖 ​

架构设计

整体架构

模块详解

`io/` — 输入输出

`index/` — 索引构建

`align/` — 比对算法

`util/` — 工具函数

内存防护机制

索引文件格式

对齐流程

与 BWA 的差异

技术栈

安全性保证

测试覆盖