> For the complete documentation index, see [llms.txt](https://book.ncrnalab.org/teaching/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://book.ncrnalab.org/teaching/7.deduplication.md).

# 7.Deduplication

{% hint style="info" %}
**主要问题**：在处理带 UMI 的 NGS 数据时，一般需要进行 deduplication（去重）的前处理，这一过程一般几十分钟到几小时。但是我们在实际科研当中，却发现有些去重工作需要耗时几天甚至 1-2 周的时间。请针对这一异常耗时问题，在 AI 的协助下寻找解决方法，力争将时间压缩到几小时的范围内。
{% endhint %}

## I. 背景介绍

高通量测序（NGS）常以测序读段数估计核酸分子的丰度，但建库过程中的 PCR 扩增会为同一模板产生多个副本，而且不同模板的扩增效率可能不同。因此，read count 并不必然等于原始 molecule count；若把 PCR 副本视为独立分子，扩增偏倚可能进入表达量估计和下游统计分析。<sup>\[1]\[2]</sup>

唯一分子标识符（unique molecular identifier，**UMI**）是在 PCR 扩增前引入原始核酸分子的短核苷酸标签。经过扩增和测序后，来源于同一原始分子的 reads 通常携带相同或相近的 UMI，因此可以将这些 reads 归并为一个分子级证据，从而识别 PCR duplicates，并更准确地估计原始分子数量。然而，UMI 碰撞、PCR 错误和测序错误都可能改变 UMI 与原始分子之间的对应关系；仅按 UMI 序列是否相同进行合并，可能造成错误去重。因此，实际分析通常需要结合比对位置、链方向、片段边界、细胞条形码等信息，并采用能够处理 UMI 错误的归并规则，在减少 PCR 扩增偏倚的同时尽可能保留真实的独立分子。<sup>\[1]\[2]</sup>

<figure><img src="https://4115668567-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LPVsf5VZbQ7h14X29qW%2Fuploads%2F0fgJDg92JPIw8RN55c7t%2Fdedup%E5%8E%9F%E7%90%86.png?alt=media&amp;token=94505ecc-536a-463f-9ee3-af8e9dbd8100" alt=""><figcaption></figcaption></figure>

*图 1｜UMI 去重示意。PCR 扩增前标记原始分子，扩增后将属于同一分子的 reads 折叠为分子级证据。本图为课程示意图。*

从完成分子捕获到获得最终测序 reads，实验过程中通常还会经历两轮建库 PCR，以及一轮或多轮测序相关扩增。即使使用高保真 DNA 聚合酶，扩增轮数增加后仍会积累一定数量的碱基替换，测序过程也会引入碱基误判和插入／缺失（indel）。如果错误发生在 UMI 序列中，同一原始分子的扩增产物就可能携带几个相近但不完全相同的 UMI。若将每个不同的 UMI 都计作一个独立分子，最终的分子数便会被高估。

Smith 等在真实数据中发现，同一比对位置内平均编辑距离为 1 的 UMI 组合较随机预期富集约 25 倍，而可能由单碱基缺失造成的相邻位置 UMI 组合仅富集约 1.1 倍。这里的 25 倍是相对于随机模型的富集程度，并不是碱基替换与 indel 突变率的比值。这一现象说明，同一位置上只相差一个碱基的 UMI 很多来自 PCR 或测序错误。基于这一特点，UMI-tools 先将比对位置相同的 reads 归为一组，再以 UMI 为节点、read 数量为节点权重，连接编辑距离为 1 的 UMI，构建 UMI 网络。`cluster`、`adjacency` 和 `directional` 等方法使用不同规则拆分网络；其中 `directional` 还会参考相邻 UMI 的数量差异，判断低频 UMI 是否可能由高频 UMI 经 PCR 或测序错误产生。同一簇中的 UMI 最终被视为来自同一个原始分子。<sup>\[2]</sup> 随着测序深度和局部 UMI 多样性上升，候选 UMI 比较、Python 数据结构操作、BAM 输入输出以及结果排序都可能成为瓶颈。已有研究表明，改变邻近 UMI 的查询方式和底层数据结构，可以在保持网络分组规则的同时降低计算开销。<sup>\[3]</sup>

<sup>**参考文献：**</sup>

* \[1] Kivioja, T., Vähärautio, A., Karlsson, K., et al. (2012). Counting absolute numbers of molecules using unique molecular identifiers. *Nature Methods*, 9(1), 72–74. [DOI／原文](https://doi.org/10.1038/nmeth.1778).
* \[2] Smith, T., Heger, A., & Sudbery, I. (2017). UMI-tools: modeling sequencing errors in Unique Molecular Identifiers to improve quantification accuracy. *Genome Research*, 27(3), 491–499. [DOI／原文](https://doi.org/10.1101/gr.209601.116)；[开放全文](https://pmc.ncbi.nlm.nih.gov/articles/PMC5340976/).
* \[3] Liu, D. (2019). Algorithms for efficiently collapsing reads with Unique Molecular Identifiers. *PeerJ*, 7, e8275. [DOI／原文](https://doi.org/10.7717/peerj.8275)；[开放全文](https://pmc.ncbi.nlm.nih.gov/articles/PMC6921982/).

## II. 任务目标

本作业的任务是解决 UMI 去重异常耗时的问题。请借助 AI 查找合适的工具或优化思路，在保证结果可靠的前提下，尽量把完整数据的处理时间从数天缩短到数小时。

AI 可以帮助检索工具、解释算法、分析日志和修改代码，但关键结论仍需通过软件文档、论文或实际运行结果核实。

最终需要回答两个问题：

* 方法加速了多少?
* 所得结果是否可信?

## III. 数据集与下载链接

我们提供三个不同大小的待去重的 BAM 文件做为输入数据（input）：

* **Big** 是完整的原始数据；
* **Small** 是从 Big 中抽取的小数据集，用于快速调试；
* **Big-downsample** 是从 Big 按固定随机种子抽样得到的中量数据集，用于在运行完整 Big 之前做过渡测试，也可以按 下文 Help 中的 Step 3 中的命令自行生成。

| 数据集                | 提供文件                                                                  | 用途                |
| ------------------ | --------------------------------------------------------------------- | ----------------- |
| Small              | `small.bam`、`small_feature_count.txt`                                 | 调试命令，快速比较不同方案     |
| Big                | `big.bam`、`big_feature_count.txt`                                     | 测试最终方案的运行效率和结果一致性 |
| Big-downsample（可选） | `big_downsampled_input_sorted.bam`、`big_downsample_feature_count.txt` | 在运行 Big 之前进行过渡测试  |

做为检查输出的参考文件，我们还提供了标准的 UMI-tools 流程生成 featureCounts 结果。例如，Big 数据的参考结果（`big_feature_count.txt`）由常规 `umi_tools dedup` 去重后再经 featureCounts 生成。该去重流程约需 4 天，这一步已经完成，结果随数据一并提供，其核心命令为：

```bash
umi_tools dedup \
    -I INPUT_SORTED_BAM \
    -S OUTPUT_DEDUPLICATED_BAM \
    --output-stats=OUTPUT_STATS_PREFIX \
    > UMI_TOOLS_LOG 2>&1
```

这条命令既是参考结果的来历，也是后续加速方案要对齐的基线。请先弄清楚各参数的含义，以及当前数据的 UMI 存储方式、单双端模式和去重方法，再选择替代方案。同学们不需要再运行这条命令处理 Big input BAM，只需运行自己的加速方案，对所得去重 BAM 进行 featureCounts，再与参考结果直接比较。

此外，我们还提供了运行 featureCounts 所需的基因注释文件 `gencode.v38.gtf`（即下文 Help 中的 Step 5 中的 `-a` 参数）。用同一份注释文件、同一组参数去计数，各级数据的结果才具有可比性。

{% hint style="warning" %}
**注意：** UMI 去重结果与每个 UMI family 中的 reads 数量有关，先抽样再去重与先去重再抽样并不等价。Big-downsample 的结果只能与它自己的参考 `big_downsample_feature_count.txt` 比较，不能与完整 Big 数据的 `big_feature_count.txt` 直接比较。
{% endhint %}

### 下载链接

上述文件（`big.bam`、`small.bam`、`big_downsampled_input_sorted.bam`、`big_feature_count.txt`、`small_feature_count.txt`、`big_downsample_feature_count.txt`、`gencode.v38.gtf`）都放在同一个云盘下载目录中： 【[Download Link](https://cloud.tsinghua.edu.cn/d/e3215eb0090f4b3dac1e/?p=%2FFiles%2FPART_V\&mode=list)】

## IV. 作业任务

### Track 1：寻找更快的处理方案（必做）

借助 AI、软件文档和相关论文，寻找能够提高 UMI 去重速度的工具或流程。可以更换工具，也可以优化排序、索引、线程、内存、临时目录和 BAM 输入输出。所选方法应与当前流程具有相同或相近的去重规则，并依次在 Small 和 Big 数据上测试。Big-downsample 可作为中间验证，但不是必做内容。

所用工具、关键参数和运行结果填入结果表；选择依据，以及它与 `umi_tools dedup` 在处理逻辑上的异同，写进报告的设计构思部分。

### Track 2：优化算法或代码（进阶／加分）

在 Track 1 的基础上，可以进一步分析现有程序的耗时环节，并从算法或代码层面进行优化，例如改进相邻 UMI 搜索、UMI 网络构建、数据结构、并行计算或 BAM 读写。

选择 Track 2 的同学需要在设计构思部分说明优化思路和实现方式。如果修改了原有的 UMI 归并规则，还需在结果表的备注中注明，并解释这一变化可能对结果造成什么影响。

## V. 作业提交形式

Small 和 Big 都要完成并提交：Small 数据量小，用于快速调试方法和排查问题；Big 用于给出最终结果。Big-downsample 是可选的中间测试，不能替代前两者。

### 提交内容

整份报告合并为一个 PDF 或者 MD 文件提交，包含以下两部分。

**第一部分：设计构思。** 说明你如何在 AI 的协助下完成工具选择：为什么选这个工具或方案、它为什么比 `umi_tools dedup` 更快，中间经历了哪些尝试和迭代，以及最终版方案的设计思路。这部分重在讲清判断依据，而不是罗列问过 AI 哪些问题；结论仍需用软件文档、论文或实际运行结果来支撑。

**第二部分：结果评估。** 包含 Small 和 Big 各一张逐基因相关性散点图，以及一张性能与结果一致性表。散点图按 Step 6 的要求绘制，并在图中或图注标明 Pearson correlation、Spearman correlation 和纳入比较的基因数。表格必须包含以下字段，Small 和 Big 各占一列：

| 字段                                  | 说明                                      |
| ----------------------------------- | --------------------------------------- |
| Track（1 / 2）                        | 只完成必做内容填 1；做了算法或代码优化填 2                 |
| 方法及版本                               | 所用工具或方案，以及版本号                           |
| 关键参数                                | 除输入输出路径外，影响结果或性能的主要参数                   |
| CPU 型号、使用 CPU 数、可用内存（GiB）           | 运行所用计算节点的配置与实际占用                        |
| 耗时 Elapsed Time                     | 加速方案从开始到结束的实际经过时间，请注明计时范围               |
| 内存 Memory (peak RSS)                | 去重进程运行期间的峰值常驻内存，而非计算节点的总内存或申请内存，请注明统计方法 |
| 输入 / 输出 reads 数                     | 去重前后的序列条数；本作业数据为单端测序，按 reads 计          |
| 去重比例                                | 输出分子数与输入 reads 数之比，或你所用的等价统计            |
| 相关系数 Pearson / Spearman correlation | 自己的逐基因计数与参考 featureCounts 的相关系数         |
| 备注                                  | 结果与参考值有明显差异，或修改了原有归并规则时补充说明             |

不同数据集的规模差异很大，计时和内存请分别记录，不要用 Small 的结果去估计 Big。如额外报告了 Big-downsample，可在表中另加一列。

报告按“学号\_姓名.pdf/.md”命名后提交。

## VI. Help 帮助

### 基础软件

* 常规 deduplication 软件 UMI Tools 介绍和使用指南：[UMI-tools 官方文档](https://umi-tools.readthedocs.io/en/latest/) · [Quick start](https://umi-tools.readthedocs.io/en/latest/QUICK_START.html) · [`dedup` 命令参考](https://umi-tools.readthedocs.io/en/latest/reference/dedup.html) · [网络去重方法](https://umi-tools.readthedocs.io/en/latest/the_methods.html) · [官方 GitHub 仓库](https://github.com/CGATOxford/UMI-tools)

### 步骤指引

### Step 1. 检查数据和运行环境

首先确认 BAM 是否完整、是否按坐标排序，并查看 UMI 和细胞条形码等信息存放在哪个字段。同时记录所用计算节点的 CPU、内存和软件版本。

```bash
samtools quickcheck -v INPUT_BAM
samtools view -H INPUT_BAM
samtools view INPUT_BAM | head
```

### Step 2. 在 Small 数据上调试

先在 Small 数据上运行候选方法，检查程序能否正常结束，并比较输入输出 reads 数量、去重比例和运行时间。对去重后的 BAM 运行 featureCounts，与提供的 `small_feature_count.txt` 比较。Small 数据适合快速试错，不建议一开始就在 Big 数据上反复运行。

### Step 3. 使用 downsample 数据进行验证（可选）

Big-downsample 是从 Big input BAM 中按固定随机种子抽取的中量数据，已提供 `big_downsampled_input_sorted.bam` 及其参考 `big_downsample_feature_count.txt`，可以直接用于测试。下面的命令展示了它的生成方法：

```bash
# 示例：随机种子为 2026，抽取约 2% 的模板
samtools view \
    -@ 8 \
    -b \
    -s 2026.02 \
    -o big_downsampled_input_sorted.bam \
    big.bam

samtools index -@ 8 big_downsampled_input_sorted.bam
```

`-s` 参数中，小数点前为随机种子，小数部分为抽样比例。例如，`2026.02` 表示使用随机种子 2026，抽取约 2% 的模板。自行抽样时应记录随机种子和抽样比例；只有使用提供的 Big-downsample input，才能直接与提供的 downsample 参考结果比较。

### Step 4. 运行 Big 数据

在 `big.bam` 上只运行经过 Small 验证的加速方案，不需要再运行标准 UMI-tools 基线。保留完整命令、运行日志、软件版本和资源使用记录，并对自己的去重 BAM 完成下面的定量比较。

### Step 5. 生成 featureCounts 基因计数

对自己的去重 BAM 运行 featureCounts，得到逐基因的计数结果，供 Step 6 与参考结果比较。通用命令如下：

```bash
featureCounts \
    -O \
    -t exon \
    -g gene_id \
    -M \
    -s 1 \
    -Q 0 \
    -a gencode.v38.gtf \
    -o OUTPUT_COUNTS.txt \
    INPUT.bam \
    > FEATURECOUNTS.log 2>&1
```

上述命令按 exon 计数，以 `gene_id` 汇总；`-O` 允许一条 read 分配给多个相互重叠的 feature，`-M` 允许多重比对 reads 参与计数，`-s 1` 表示正向链特异性，`-Q 0` 表示不设置最低比对质量阈值。除输入和输出路径外，请保持这些参数与参考结果一致。

### Step 6. 绘制逐基因相关性散点图

以每个基因为一个点，横轴为提供的参考 featureCounts（Small 用 `small_feature_count.txt`，Big 用 `big_feature_count.txt`），纵轴为自己的 featureCounts。建议对 counts 进行 `log1p` 转换，并画出 `y = x` 参考线。图中或图注中至少给出 Pearson correlation、Spearman correlation 和纳入比较的基因数。

除相关性外，还要检查输入输出 reads 数量、去重比例、`featureCounts` 的 assigned/unassigned 统计和计数差异较大的基因。如果结果与参考值不完全一致，请进一步查看差异是否集中在低表达基因、高表达基因或 UMI 密度较高的基因，并判断差异来自参数设置、文件处理还是 UMI 归并算法。相关性很高并不能排除整体计数偏移或部分 reads 丢失。