logannye/rosalind

来源：https://github.com/logannye/rosalind

Rosalind

确定性基因组引擎，内存占用紧凑。全基因组工作负载仅需约 100 MB RAM 即可运行。

Rosalind 是一个用 Rust 编写的引擎，用于基因组比对、流式变异检测以及自定义生物信息学分析，可在普通硬件或边缘设备上运行。它实现了 O(√t) 工作内存、确定性重放以及对新流水线（Rust 插件或 Python 绑定）的即插即用扩展。传统流水线通常需要 50-100+ GB 的 RAM、配置良好的数据中心和不间断的网络连接；Rosalind 则为相反的场景设计：医院工作站、诊所笔记本电脑、现场工具包和教室。

快速概览

• 核心问题：BWA、GATK 等标准工具或云中心工作流通常需要 >50 GB RAM、完整的中间文件副本以及高带宽存储，导致许多医院、公共卫生实验室和教学环境难以使用。
• Rosalind 的应对方案：将工作负载分割为 √t 个块，在块之间复用滚动边界，并评估一个高度压缩的树，使内存保持在 L1/L2 缓存中，同时保证确定性结果。即使对于全基因组，整个流水线也能很好地控制在 100 MB 以下。
• 如何使用：运行 CLI、嵌入 Rust API，或通过插件/Python 扩展构建定制基因组工作流——非常适合快速周转的临床诊断、疫情监测或学生在笔记本电脑上探索真实数据的课程。详见 概览、对比 和 O(√t) 内存的含义。

概览

• O(√t) 工作内存 – 全基因组运行保持在 ~100 MB 以下，无需有损近似。
• 端到端确定性 – 无论运行多少次或分区选择如何，输出都逐比特一致。
• 全历史等价 – 重新计算使结果与无限内存评估完全一致。
• 流式 SAM/BAM/VCF – 无需物化大型中间文件即可输出符合标准的文件。
• 边缘就绪部署 – 可在 8–16 GB 的笔记本电脑/台式机上运行，PHI 数据留在本地。
• 可组合扩展 – 插件/Python 绑定继承相同的内存和确定性保证。

为什么 Rosalind 很重要

1. 在笔记本电脑上进行临床基因组学 – 在许多主要研究中心以外的医院，最快的可用硬件是共享的 8–16 GB RAM 台式机。Rosalind 让临床医生在一个班次内完成患者基因组比对和变异检测，无需租用云机器或将敏感数据传出站点。
2. 边缘疫情监测 – 在野外应急（埃博拉、寨卡、SARS-CoV-2）期间，便携式测序仪和笔记本电脑很常见，但高内存服务器则不然。Rosalind 可流式读取 reads、实时检测变异，并能容忍间歇性连接，实现现场决策。
3. 群体规模研究 – 大学或小型实验室可能拥有中端集群，但仍需处理数千样本的队列。Rosalind 保持每个样本的内存恒定，从而可以在经济高效的实例上并行处理更多基因组。
4. 教育与推广 – 学生可以在个人电脑上实验比对、变异检测和插件开发，使计算基因组学课程更具实操性和公平性。
5. 定制分析 – 开发者可以插入覆盖度仪表盘、质量指标或单细胞类聚合功能，同时享受相同的空间保证，简化从原型到生产的路径。

关键保证

• 空间界限：总内存 space_used ≤ block_size + num_blocks + O(log num_blocks) = O(√t)；仅保留最近的块边界。
• 确定性重放：每个块从前一个边界重新模拟，产生与完整历史相同的结果，即使在资源受限的设备上也是如此。
• 可组合设计：块处理器、插件和绑定使用同一压缩评估器，因此新分析继承相同的保证——非常适合定制 QC 或流行病学仪表盘。
• 内置护栏：回归测试 (tests/space_bounds.rs) 和 scripts/run_scale_test.sh 在 O(√t) 或次线性缩放属性回归时失败。
• 分区不变性：对于有效的块大小和分块选择，输出保持不变；合并是确定性的且与顺序无关。
• 全历史等价：结果与无界历史评估匹配；空间节省来自重新计算，而非信息丢失。

O(√t) 内存的含义（以及 ‘t’ 是什么）

• t ≈ 处理的总碱基数。对于 30× 人类全基因组测序：覆盖度 C ≈ 30，基因组大小 G ≈ 3.1×10⁹，因此 t ≈ C × G ≈ 9.3×10¹⁰。
• √t ≈ 3.0×10⁵，这设置了块缓冲区大小。高度压缩的合并栈有 log₂(t) ≈ 36 层——与块相比可忽略不计。
• 工作集 ≈ (α + β) · √t + γ。假设每个活跃位置 α ≈ 64–128 B，全基因组运行大约在 30–80 MB；即使保守假设也能将界限保持在 <100 MB。
• 该界限成立，因为只有当前块、滚动边界和紧凑的合并栈驻留在内存中；旧状态按需重新计算。
• FM 索引/参考可以内存映射，因此 O(√t) 的主张涉及 Rosalind 相对于数据集大小的动态工作集。

为什么这不同

• 分区不变的确定性 – 无论块大小或分区如何，每次运行的输出都逐比特一致；非常适合临床审计、SOP 锁定和事件调查。
• 严格、测试强制执行的 O(√t) 内存 – 全基因组运行完全低于 100 MB；CI 门控在界限回归时失败。
• 全历史等价 – 重新计算（而非截断）保证与无界内存评估结果一致。
• 真正的流式读取 → 变异 – 无需物化大型中间文件；减少 IO/存储压力和首次结果时间。
• 无需重型基础设施的标准支持 – 在保持流式和内存优势的同时，生成可互操作的 SAM/BAM/VCF。
• 缓存驻留执行 – 将状态保持在 L1/L2 中，减少在普通硬件上的缓存未命中和页面交换，提高大型服务器之外的实际吞吐量。
• 可组合扩展继承保证 – 插件和 Python 绑定共享相同的压缩评估器和工作空间池，保留内存界限和确定性。

临床相关性

• PHI 数据留在本地——在 8–16 GB 的医院台式机和现场笔记本电脑上舒适运行，无需云传输。
• 逐比特可重现简化了 CAP/CLIA 审计、SOP 锁定和事件审查。
• 可预测的 <100 MB 工作集避免了内存溢出，并使共享调度器/工作站保持稳定。
• 流式友好操作容忍间歇性连接，并在现场最小化临时文件生成。

对比方式

核心能力

• FM 索引比对 – 分块 Burrows–Wheeler/FM 索引搜索，每个块使用 rank/select 检查点，仅需 O(√t) 工作状态，使在中等配置笔记本上比对整个参考基因组成为可能。
• 流式变异检测 – 实时 pileups 结合贝叶斯评分，保持内存有界的同时实时发出变异；非常适合远程监测、床边基因组学或交互式 notebook。
• 符合标准的输出 – 可互操作的 SAM/BAM/VCF，流式友好 IO，最小化大型中间文件和排序/索引开销。
• 插件与 Python 生态系统 – 实现 GenomicPlugin trait 或调用 PyO3 绑定以添加自定义分析，无需重复内存——例如 RNA 表达摘要或诊断中的覆盖度缺失检查。
• 滚动边界 – 在 DFS 评估期间仅保留最新的块摘要；丢弃旧摘要，保证 O(b + T + log T) = O(√t)。

Rosalind 如何实现 O(√t) 空间

1. 块分解 – 工作负载被分割为 √t 个块，带有确定性摘要；一次只有一个块的缓冲区在内存中，避免整个 reads 缓存。
2. 高度压缩树 – 子摘要在一个高度为 O(log√t) 的隐式树中合并；无指针 DFS 每层仅存储 2 位，并实时重新计算端点。
3. 流式账本 – 每个块 2 位跟踪完成状态，防止重复合并或存储中间树。
4. 工作空间池 – 单个可复用分配在组件（比对、pileups、插件）之间共享，避免分配器抖动并保持界限。
5. 执行流程 – (reads) → 块比对 → 滚动边界更新 → 树合并 → 流式输出（变异、度量、分析）。该流水线镜像典型的比对器+变异检测工作流，但内存需求大幅降低。

仓库布局

• src/framework/ – 通用压缩评估器和配置辅助函数。
• src/genomics/ – FM 索引、比对摘要、pileups、变异检测和共享类型。
• src/plugin/ – 插件 trait、执行器、注册表和示例 RNA-seq 定量插件。
• src/python_bindings/ – 将 Rosalind 暴露给 Python 的 PyO3 桥接。
• src/main.rs – 命令行界面（align/variants 子命令）。
• examples/ – CLI 示例（包括 verify_installation.rs）和规模性能基准测试；包含用于实验的小型合成数据集。
• scripts/ – 实用脚本（玩具数据集生成、SAM 与 BAM 基准测试）。
• tests/ – 单元、属性和集成测试（比对、变异检测、空间界限）。
• tests/common/、tests/snapshots/ – 快照框架和 CLI/VCF 测试使用的黄金 fixture。

安装与构建

先决条件

• Rust 1.72+（推荐 rustup）
• Python 3.9+（用于 PyO3 绑定；如果默认解释器不合适，设置 PYO3_PYTHON=/path/to/python）
• BAM 输出所需的原生压缩头文件（Debian/Ubuntu 上为 libbz2-dev 和 liblzma-dev，macOS 上为 brew install bzip2 xz）

构建

git clone https://github.com/logannye/rosalind.git
cd rosalind
cargo test                  # 运行完整测试套件
cargo build --release

验证 CLI 是否可用：

cargo run --release -- --help

可选：运行冒烟测试示例以确认完整流水线：

cargo run --example verify_installation

在其他 crate 中使用 Rosalind：

[dependencies]
rosalind = { path = "./rosalind" }

样本数据：examples/data/ 包含小的 FASTA/FASTQ 片段和比对输入，与“快速入门”命令对应，因此无需寻找外部数据集即可重现工作流。需要更大的数据？使用以下命令生成确定性的 ~10× 玩具基因组：

python scripts/generate_toy_data.py examples/data/illumina_toy
cat examples/data/illumina_toy/SHA256SUMS

脚本会生成 reference.fa、配对的 reads_R1.fastq/reads_R2.fastq 以及可重现的 SHA256 校验和，以便安全缓存或共享更大的演示数据。

快速入门

1. 比对 reads（Rust API）

适合将 Rosalind 嵌入自己的流水线或单元测试。

use rosalind::genomics::{BWTAligner, AlignmentResult};

fn align_reads(reads: &[Vec<u8>], reference: &[u8]) -> anyhow::Result<Vec<AlignmentResult>> {
    let mut aligner = BWTAligner::new(reference)?;
    aligner.align_batch(reads.iter().map(|r| r.as_slice()))
}

每个 AlignmentResult 包含 FM 间隔（候选位置）、错配计数和启发式分数——足以驱动下游过滤或组装逻辑。

2. 调用变异（Rust API）

use rosalind::genomics::{AlignedRead, StreamingVariantCaller};

fn call_variants(reads: Vec<AlignedRead>, reference: &[u8]) -> anyhow::Result<Vec<Variant>> {
    let chrom = std::sync::Arc::from("chr1");
    let reference = std::sync::Arc::from(reference.to_vec().into_boxed_slice());
    let mut caller = StreamingVariantCaller::new(chrom, reference, 0, 1024, 10.0, 1e-6)?;
    caller.call_variants(reads)
}

每个 Variant 报告位置、参考/替代等位基因、等位基因频率和质量——足以输入临床报告、监测仪表盘或 QC 脚本。

3. 命令行

非常适合试点、演示或使用样本数据的快速分析。

# 将 FASTQ reads 与 bundled 参考比对并捕获 SAM 输出
cargo run --release -- align \
    --reference examples/data/ref.fa \
    --reads examples/data/reads.fastq \
    --format sam \
    --max-mismatches 2 \
    --reference-offset 0 > examples/data/alignments.sam

# 将坐标排序的 BAM 直接写入磁盘（推荐用于下游工具）
cargo run --release -- align \
    --reference examples/data/ref.fa \
    --reads examples/data/reads.fastq \
    --format bam \
    --output examples/data/alignments.bam

# 从 SAM/BAM 比对中调用变异（默认 VCF 到 stdout）
cargo run --release -- variants \
    --reference examples/data/ref.fa \
    --alignments examples/data/alignments.sam \
    --mapq-threshold 10 \
    --region-start 0

# 或将 VCF 写入磁盘
cargo run --release -- variants \
    --reference examples/data/ref.fa \
    --alignments examples/data/alignments.sam \
    --output examples/data/variants.vcf

注意： rosalind align 在输出 SAM/BAM 之前，通过 O(√t) FM 索引对第一个 FASTA 记录进行索引。在支持多 contig 测序之前，额外的记录将被忽略（打印警告）。

关键参数：

• --max-mismatches 限制种子期间每个读段的汉明距离。
• --format {sam|bam} 切换纯文本 SAM 和 BGZF 压缩 BAM（BAM 需要 --output）。
• --mapq-threshold 在变异检测前过滤低置信度比对。
• --region-start 允许为拼接分析偏移报告的基因组坐标。
• --output/-o 将结果写入磁盘而非 stdout（适用于两个子命令）。

4. Python 绑定

非常适合探索性分析、快速原型设计或教学。使用 maturin 安装绑定：

pip install maturin
maturin develop --release

from rosalind_py import PyGenomicEngine

engine = PyGenomicEngine()
print(engine.list_plugins())

# region_start, region_end, reads[(pos, seq)], block_size
depth = engine.run_rna_seq_plugin(
    region_start=100_000,
    region_end=101_000,
    reads=[(100_020, "ACGTACGT"), (100_050, "TTTACGT")],
    block_size=512,
)

示例插件输出每个碱基的覆盖度，适用于表达定量或 QC 图表。

验证保证