SigAlign

一个 Similarity-Guided Alignment Algorithm

什么是 SigAlign？

SigAlign 是一个用于生物序列对齐的库，对齐两个序列以识别相似性，这是生物信息学和计算生物学中分析序列数据的关键步骤。如果您对序列对齐不熟悉，可以在 维基百科 上快速了解。

SigAlign 是一个 非启发式 算法，输出满足两个截止值的对齐

1. 最小长度
2. 每长度最大惩罚

在 SigAlign 中，惩罚是根据 gap-affine 方案 计算的，该方案对错配、间隙打开和间隙扩展施加不同的惩罚。

核心目的

SigAlign 设计为

• ⚡️ 快速 收集高度相似的对齐
• 💡 易于 定制和解释结果
• 🧱 小巧灵活，作为其他工具的基本构建块

SigAlign 并不打算

• 对齐超长读段
• 搜索低相似度对齐

快速入门示例

对于 Rust 开发者

• 作为 Rust 库，SigAlign 可以利用 Rust 中最丰富的特性。
  • 在 crates.io 上注册： https://crates.io/crates/sigalign/
  • API 文档： https://docs.rs/sigalign/

use sigalign::{
    Aligner,
    algorithms::Local,
    ReferenceBuilder,
};

// (1) Build `Reference`
let fasta =
br#">target_1
ACACAGATCGCAAACTCACAATTGTATTTCTTTGCCACCTGGGCATATACTTTTTGCGCCCCCTCATTTA
>target_2
TCTGGGGCCATTGTATTTCTTTGCCAGCTGGGGCATATACTTTTTCCGCCCCCTCATTTACGCTCATCAC"#;
let reference = ReferenceBuilder::new()
    .set_uppercase(true) // Ignore case
    .ignore_base(b'N') // 'N' is never matched
    .add_fasta(&fasta[..]).unwrap() // Add sequences from FASTA
    .add_target(
        "target_3",
        b"AAAAAAAAAAA",
    ) // Add sequence manually
    .build().unwrap();

// (2) Initialize `Aligner`
let algorithm = Local::new(
    4,   // Mismatch penalty
    6,   // Gap-open penalty
    2,   // Gap-extend penalty
    50,  // Minimum length
    0.2, // Maximum penalty per length
).unwrap();
let mut aligner = Aligner::new(algorithm);

// (3) Align query to reference
let query = b"CAAACTCACAATTGTATTTCTTTGCCAGCTGGGCATATACTTTTTCCGCCCCCTCATTTAACTTCTTGGA";
let result = aligner.align(query, &reference);
println!("{:#?}", result);

对于 Python 开发者

• SigAlign 的 Python 绑定可在 PyPI 上找到： https://pypi.ac.cn/project/sigalign/
  • 使用 pip 安装包： pip install sigalign

from sigalign import Reference, Aligner

# (1) Construct `Reference`
reference = Reference.from_fasta_file("./YOUR_REFERENCE.fa")

# (2) Initialize `Aligner`
aligner = Aligner(4, 6, 2, 50, 0.2)

# (3) Execute Alignment
query = "CAAACTCACAATTGTATTTCTTTGCCAGCTGGGCATATACTTTTTCCGCCCCCTCATTTAACTTCTTGGA"
results = aligner.align_query(reference, query)

# (4) Display Results
for target_result in results:
    print(f"# Target index: {target_result.index}")
    for idx, alignment in enumerate(target_result.alignments):
        print(f"  - Result: {idx+1}")
        print(f"    - Penalty: {alignment.penalty}")
        print(f"    - Length: {alignment.length}")
        print(f"    - Query position: {alignment.query_position}")
        print(f"    - Target position: {alignment.target_position}")

对于 Web 开发者

• SigAlign 提供了 WebAssembly (WASM) 构建，为基于 Web 的应用开辟了潜力。虽然它目前无法通过包管理器（如 npm）使用，但正在计划 Web 支持。
• 在 example 目录中可以找到示例 WASM 实现。以下是一个 TypeScript 示例，展示了通过此 WASM 包装器应用 SigAlign：

import init, { Reference, Aligner, type AlignmentResult } from '../wasm/sigalign_demo_wasm';

async function run() {
    await init();

    // (1) Construct `Reference`
    const fasta: string = `>target_1
ACACAGATCGCAAACTCACAATTGTATTTCTTTGCCACCTGGGCATATACTTTTTGCGCCCCCTCATTTA
>target_2
TCTGGGGCCATTGTATTTCTTTGCCAGCTGGGGCATATACTTTTTCCGCCCCCTCATTTACGCTCATCAC`;
    
    const reference: Reference = await Reference.build(fasta);
    
    // (2) Initialize `Aligner`
    const aligner: Aligner = new Aligner(
        4,    // Mismatch penalty
        6,    // Gap-open penalty
        2,    // Gap-extend penalty
        50,   // Minimum aligned length
        0.2,  // Maximum penalty per length
    );

    // (3) Execute Alignment
    const query: string = "CAAACTCACAATTGTATTTCTTTGCCAGCTGGGCATATACTTTTTCCGCCCCCTCATTTAACTTCTTGGA";
    const result: AlignmentResult = await aligner.alignment(query, reference);

    // (4) Parse and Display Results
    const parsedJsonObj = JSON.parse(result.to_json());
    console.log(parsedJsonObj);
}

run();

• 要深入了解SigAlign在Web上的实现，请访问SigAlign的游览页面。该页面使用了上述示例中的WASM包装器。

许可证

SigAlign遵循MIT许可证发布。

引用

Bahk, K.，& Sung, J. (2024). SigAlign: an alignment algorithm guided by explicit similarity criteria. Nucleic Acids Research, gkae607. https://doi.org/10.1093/nar/gkae607