2.1.2 CIGAR String

CIGAR 字符串是比对结果的一种紧凑文本表示，用来描述一条 read 序列是如何比对到参考序列（在 S2G 中就是选定的图路径）上的。
它不存储碱基本身，而是存储一系列“长度 + 操作”的组合，说明在比对过程中发生了哪些匹配、插入、删除等操作。

1. 基本组成

CIGAR 由若干“操作块”组成，每个块格式是：

<长度><操作符>

常见操作符：

操作符	含义
M	比对匹配（match/mismatch，不区分）
=	序列完全匹配
X	序列不匹配
I	插入（read 中有，参考/图路径中没有）
D	删除（参考/图路径中有，read 中没有）
N	跳过区域（如内含子）
S	软剪切（read 两端未比对上的部分）
H	硬剪切（不包含在序列中的剪切）
P	填充

例如：

10M2I5M1D8M

表示：

• 10 个碱基比对匹配/错配；
• 2 个碱基插入；
• 5 个碱基比对匹配/错配；
• 1 个碱基删除；
• 8 个碱基比对匹配/错配。

如果连续 100 个都是匹配，就写成 100M，而不是写 100 个 M。
所以 CIGAR 是压缩的，长度通常远小于 read 本身。

2. 在 Sequence-to-Graph 中的作用

在 PanGaea 的流水线里：

1. Alignment 阶段用 WFA 计算出 read 与候选图路径之间的最优比对；
2. Traceback Logic 回溯 DP 矩阵，确定每一步是匹配、插入还是删除；
3. 把这些操作合并成 CIGAR 字符串；
4. 最后通过 DMA 写回 host memory。

所以 CIGAR 是碱基级比对的最终输出，告诉下游工具：

这条 read 是如何对齐到这条图路径上的，哪些位置匹配，哪些位置有插入或删除。

3. 在论文中的位置

论文第 4.1 节 Traceback Logic 写道：

“reconstructs the CIGAR string by backtracking through the DP matrices … writes the resulting CIGAR string to a 4 KB region in the GLB before DMA transfer to host memory.”

说明 CIGAR 由 Traceback 单元生成，先放在 GLB，再传给主机。

在公式 (5) 中：

$$\mathrm{DRAM_{fused}}(T) = \underbrace{N_{a}\cdot S_{a}}_{\mathrm{anchor~input}} + \underbrace{T\cdot N_{gc}^{\mathrm{glue}}\cdot S_{cigar}}_{\mathrm{alignment~output}}$$

其中 $S_{cigar} \approx 25$ 字节，表示每条 alignment 的 CIGAR 字符串平均大小。
融合流水线后，DRAM 只需要：

• 读入 anchors；
• 写出最终 CIGAR 结果。

中间数据不再往返 DRAM，所以 CIGAR 成了主要输出之一。

4. 为什么 CIGAR 很小？

因为它是压缩表示：

• 连续相同的操作合并成一个块；
• 只记录长度和操作类型，不记录具体碱基；
• 一条长 read 的比对结果，可能只用几十个操作块就能描述。

论文中取 $S_{cigar} \approx 25$ 字节，说明平均每条 alignment 的 CIGAR 字符串只有少量操作块，非常紧凑。

一句话总结

CIGAR 字符串是碱基级比对结果的紧凑编码，用“长度+操作符”描述 read 与参考/图路径之间的匹配、插入、删除等关系。
在 PanGaea 中，它由 Traceback Logic 生成，是融合流水线最终写回主机的主要输出，平均约 25 字节每条 alignment。