前段时间为了写资料而搜寻 swarm 相关内容无果，在谷歌学术翻到一篇 swarm 的学术论文（严格来说就是 swarm 的paper），在学习过程中主要对 swarm 的工作流程做了了解。
想写一篇总结，但写着写着差点变成了文献翻译，不知道现在算不算解读。整理出的内容适合入行不久，想了解 de novo OTU聚类方法的情况（主要是swarm）（虽然现在OTU已经out，已经有了更好的 denoise 方法，但作为新人多学习还是没有坏处的），如果想引用这篇学术论文：
Cite this as
Mahé F, Rognes T, Quince C, de Vargas C, Dunthorn M. 2014. Swarm: robust and fast clustering method for amplicon-based studies. PeerJ 2:e593https://doi.org/10.7717/peerj.593
持续更新，禁止转载。
以下为正文内容。
简介
在Swarm 出现之前，流行的 de novo 聚类方法存在两个基本缺陷：1. 任意的全局聚类阈值；2. 质心选择所引起的输入顺序（input-order）依赖。
于是，实现一种精确、快速、全新的聚类方法，解决上述两个基本问题，产生有意义的 OTU ，并减少聚类参数的影响，成为 Swarm 的开发目的。
Swarm的聚类步骤可以概括为：首先使用局部阈值迭代地聚类几乎相同的扩增子，然后根据 OTU 内部结构和扩增子丰度来优化结果。在这里，只对聚类过程进行详细描述。
Swarm keyword：快速，准确，双阶段，凝聚，无监督(de novo)单链接聚类
详细流程描述
de novo聚类启发式算法是快速且贪婪的，传统 de novo 算法使用的聚类思想：
从扩增子池中选择一个扩增子作为新OTU的中心（质心），将其与池中其它所有的扩增子进行比对。那些与质心全局聚类阈值相距小于 t （用户自己设置的相似度阈值）的扩增子，都归属于一个OTU，随后OTU关闭。
只要池中还有扩增子。这一步骤就会重复。如图1所示。
BioMarKs 项目和 TARA OCEANS 项目使用不同标记和不同测序平台，进行了两项大规模的环境多样性研究，研究凸显了贪婪 de novo 聚类的局限性。人们发现如果一个物种的扩增子丰度很高，那么另一个与其生态环境非常不同、但基因相近的物种的扩增子会被划分为前者的OTU归属，导致错误的生态解释。
Swarm是为了解决这一问题而开发出的新方法，可以避免固定的全局聚类阈值，以及由质心的选择而产生的输入顺序（input-order）依赖。
在growth阶段，Swarm 使用 k-mer 比对和一种速度非常快的全局成对比对算法，计算对齐扩增子对的序列差异来描述OTU；在breaking阶段，Swarm使用扩增子丰度信息和OTU内部结构，细化聚类结果。
我们可以这样构思：
· 扩增子可以被抽象地看作一个扩增子空间（amplicon-space）中的离散坐标。空间中的每个位置代表一个可能的扩增子，这个扩增子或不存在于数据集中（空丰度（null abundance）），亦或存在于数据集（观察到的丰度（observed abundance））。
· 一个给定扩增子的直接邻近是具有一个核苷酸差异（一个置换、插入或删除）的所有可能扩增子。这个概念可以扩展到 d 邻近（d-neighbors），即：具有 d 个核苷酸差异的扩增子。 在这个理论基础上，OTU（cluster）是扩增子空间中非零丰度的连续区域。Swarm立于一个假设之上：每个 OTU 是被空白区域清楚划分开的，也就是说，扩增子本身并不会构成一个巨大的连续体。如果这个条件成立，那么OTU就被允许迭代地增长，直到达到它们的自然极限（即扩增子空间的空白区域）。
Swarm搜索扩增子空间的方式如下所述：
1. 首先，Swarm 处理输入文件并创建一个扩增子池，然后创建一个空的 OTU。
2. 将池中第一个可用的（即存在的）扩增子取出，作为该OTU的 seed（指代表序列，下文或称作 “种子”）。
3. 计算差异数：将 seed 与池中其余所有扩增子作比对，将差异数存储在存储器中。当找到了最佳的成对全局比对，差异数就是两个扩增子之间的核苷酸不匹配 (替换、插入或缺失) 数量。
4. 对于与 seed 差异数等于或小于 d（用户选择的聚类阈值）的扩增子，将其从池中删除并添加到OTU中，在OTU中成为 subseed （指子代表序列 / 子种子，基于种子选出）。
5. 再将每个 subseed 与池中其余扩增子作比对，但是注意：这一步只选择那些与 seed 最多有 2d 差异的扩增子。不过事实上，与 seed 差异大于 2d 的扩增子不可能与其中一个 subseed 的差异小于等于 d 。那么，这一过滤步骤可以概括为：g 代的一个 subseed ，即 g 种子，与池中剩余扩增子作比对，但只比对那些与 seed 差异在 ( g+1 ) * d 范围内的。一系列比对之后，将差异数等于或小于 d 的扩增子从池中取出，加入OTU中，成为 ( g+1 ) 种子。
6. 只要还有新的扩增子被捕获，这个迭代的 growth 过程就一直在每一代 subseed 身上重复。
7. OTU随后关闭。第一个可用扩增子从池中取出，成为新的OTU的种子，这个过程重复进行直到池中不再有扩增子。
如图所示：
这一聚类过程生成稳定的 OTU，它不考虑第一个 seed 的选择。Swarm在没有施加一个特定的形状或大小的情况下，勾勒出 OTU 的轮廓，并且无论最初选择的是哪个扩增子，都可以得到相同的 OTU 。
从 OTU 结构上来看，Swarm确保了每个OTU中任一扩增子都至少有一个差异数小于等于 d 的邻近扩增子。换句话说，每个 OTU 都是一个连续的扩增子集合（没有空隙）。
宏观来看，每个 OTU 之间至少有 d+1 的间距，由此可得推论：使用d = 1将使得扩增子空间的分割最优化。
tips：
如果对以下内容感兴趣，可以去翻阅原文：
1. 如果 “ 扩增子本身并不会构成一个巨大的连续体 ” 假说在某些时候不成立，Swarm该如何解决问题？
2. 计算扩增子的差异数时，成对全局对齐是一种资源消耗很大的方法，如何避免不必要的成对全局对齐？
3. 为了加速剩余的成对比较，Swarm实现了一种新的精确全局成对对齐算法，了解这种算法。
4. Swarm如何根据 OTU 内部结构和扩增子丰度来优化结果？
5. d 值的大小会造成什么影响？
6. Swarm的速度？
7. Swarm 与之前常用的 de novo 方法比较。
关于文中出现的术语 “sedd” 讲解：扩增子聚类之术语“ seed ”
学了这么久，第一次写生信文章_(:з」∠)_，才疏学浅，文中内容或图片若有错误的地方望指出，如果有疑问也可以提出，一起讨论吖。
