GraphBin:利用组装图对宏基因组contigs进行精细化分类
Bins在文章中的具体含义
动机：宏基因组分析的关键步骤是将reads组装成更长的contigs,然后将contigs分组，这些分组属于宏基因样本中存在的不同物种。
结果：新的分类方法GraphBin，利用装配图并应用标签传播算法来细化现有工具的分类结果。第一次在宏基因组分类中使用组装图和标签传播方法。
1.介绍
为了研究给定宏基因组样本的分类结构，我们需要鉴定现有物种，在组装前将读取的数据进行分类(Reads can be binned)。
虽然(binning reads)可以通过减少计算成本来简化组装过程，但由于读取长度短，可靠性差。
因此许多宏基因组分析先将reads组装成包含更多基因组信息的更长的configs,然后将这些contigs归入不同分类组。
得到binned contigs,他们就可以用来构建宏基因组样本中发现的不同物种的部分或全部基因组。
常用的组装方法：
1.基于成分的方法(composition)：每个分类组都有独特的核苷酸，并通过比较核苷酸含量进行分类（为了能够计算，将序列组成信息转化为数值特征向量，根据k-mers频率对物种进行划分）大多数采用传统的机器学习方法2.基于丰度的分类方法(Abundance-based binning methods)是基于一种假设：在单个样本中，宏基因组序列丰度分布遵循Lander-Waterman模型或者在多个宏基因组样本中高度相关。使用泊松分布，计算量较大，对密切相关菌株序列效果较好。
3.上面两种方法的结合：采用了PCA,概率模型，EM算法等技术
除了以上三种方法，还有BMC3C,COCACOLA,d2sBin等方法
现有方法对短序列，低丰度物种以及近缘物种的序列分类效果不好。因此希望使用装配过程中的contigs的附加信息解决这些问题。
2.方法
GraphBin流程图：
首先预处理步骤获得组装图，将reads组装到contigs中获得组装图，然后使用现有的装箱工具将contigs装箱，同时标记组装图，Graph精炼/优化组装图中contigs中的标签（step1），最后，GraphBin执行标签传播和精炼，并输出精炼的装箱结果（分类的过程）
2.1 预处理
2.1.1 将reads组装成configs然后构建组装图
组装工具通过reads中的重叠信息来构造组装图，然后利用重叠信息连接，形成一个连续的序列，该序列中每个read可以通过正确的方式被访问。
在组装图中，contigs表示顶点，configs之间的连接信息表示边
（如果两个contigs之间有显著重叠，组装图中会有一条边连接两个相应的顶点）
该论文中每个边有相同的权重。
相互连接的contigs更可能属于相同的物种。
因此我们可以通过contigs之间的连通信息来判断bin，通常在可视化组装图之后，通过手动细化contigs，可以改善bin结果。
metaSPAdes,SGA,MEGAHIT都是可以从reads构建组装图（算是一些组装工具吧）
metaSPAdes是从原始reads中构建de Bruijin图，然后将其转换为组装图，然后重构组装图中与宏基因组中configs相对应的路径。
SGA使用重叠布局共识的思想，首先修正原始读取中的错误，然后基于修正后的读取之间的重叠构建一个字符串图。
MEGAHIT基于简洁的de Bruijin图。
2.1.2 使用现有的工具组装contigs并标记组装图
选择两种组装工具：MetaWatt（最大似然估计）和MaxBin2（只能对长度大于1000bp的contigs进行组装）来进行组装（在2017年CAMI challenge中表现较好，但是现在是否表现好有待商榷）
reference-free binning tools？MetaBat2（2019）（组装长度大于1500bp）、SolidBin（2019）（光谱聚类方法，对长度超过1000bp的configs进行组装）、BusyBeeWeb（2017）（500bp或更长的contigs进行分类，基于web的应用程序通常计算资源有限，因此对于输入的数据的大小进行限制）三种装箱工具
在组装图中，contigs表示顶点，configs之间的连接信息表示边
当contigs被组装后，初始组装图中的相应的顶点就会被标记。顶点用不同的颜色表示属于不同容器的contigs
2.2 基于组装图优化contigs的标签
对于连接在一起的顶点或者位于附近的顶点很有可能是一类，他们之间有更多的相似性，因此，这些顶点应该有相同的标签。优化这些标签使得分类结果更准确。
广度优先搜索：分层搜索过程：从图中某一个顶点开始，由该顶点开始依次访问所有未被访问过的邻居节点，然后，再顺序访问所有邻居中还未被访问的节点，直到所有节点能被访问到。
如果节点被标记，则$L_{(i)}=1$,若未被标记则$L_{(i)}=0$
$d_{L_{(i)}}$表示已经标记的顶点与顶点之间的距离。当$d_{L_{(i)}} \rightarrow \infty $表示所有被标记的顶点不能从i到达。
$CLV_{(i)}$表示顶点i最近的标记顶点的集合，当$d_{L_{(i)}} \rightarrow \infty $，$CLV_{(i)}=\varnothing$
$CLV_{(i)}={j|d(i,j)=d_{l_{(i)}}\ and\ \ L_{(j)}=1}$
给定一个顶点，使用广度优先搜索，找到该顶点与标记顶点之间的距离满足$d_{L_{(i)}}$的点的集合，记作$CLV_{(i)}$
如上图中，$d_{L_{(4)}}=1$则$CLV_{(4)}=\{2,6\}$,同理得到$d_{L_{(13)}}=2$，$CLV_{(13)}=\{8,9\}$
模糊顶点：如果顶点i最近的标记顶点中至少有一个不同于顶点标记的顶点，则该顶点成为模糊顶点，如上图的顶点13就是模糊顶点。
模糊顶点会影响后续的传播过程，因此它会被删除，如上图中的6、7、13顶点，优化后就变成了(b)图。
2.3 运行标签传播和改进
标签传播是一种半监督机器学习技术，可以使用标记数据将标签传播到邻近的未标记数据
标签传播算法通过将标签分配给图中相应标记数据的顶点来进行初始化，在迭代过程中，顶点将其标签传播到邻近的顶点，最后，对具有相似标签的顶点进行聚类。
如果孤立组件中的所有顶点都没有通过现有的装配标签进行预测，则无法通过标签传播来推断孤立组件中的顶点的标签。
改进过程就是删除图中的模糊顶点。
3.实验设计
3.1 数据集
根据未出生婴儿的肠道宏基因组(通常称为沙龙数据集)模拟了几个宏基因组数据集,进而获得了三个最丰富的物种,比例如下:
1.(Enterococcus faecalis)粪肠球菌:70.8%
2.(Staphylococcus aureus)金黄色酿脓葡萄球菌:18.9%
3.Cutibacterium avidum 3.4%
同时在NCBI数据库中下载了完整的参考基因组.
模拟两个数据集,一个包含1和2,简称ES,另外一个包含1,2,3,简称ESC
沙龙数据集:通过对reads进行18次组合形成沙龙数据集
CAMI DATA数据集:选择三个不同的复杂性的微生物群落.
• CAMI_l: Sample from low complexity
• CAMI_m: Sample 1 with 5 kbp insert size from medium complexity
• CAMI_h: Sample 1 from high complexity
3.2 获得contigs,组装图和标签
六个模拟数据集:ES+metaSPAdes, ES+SGA, ES+MEGAHIT,ESC+metaSPAdes, ESC+SGA and ESC+MEGAHIT.
沙龙(sharon)数据集:Sharon+metaSPAdes, Sharon+SGA and Sharon+MEGAHIT
CAM_1数据集:CAMI_l+metaSPAdes, CAMI_l+SGA and CAMI_l+MEGAHIT
CAM_m数据集:CAMI_m+metaSPAdes, CAMI_m+SGA and CAMI_m+MEGAHIT.
CAM_h数据集:CAMI_h+metaSPAdes, CAMI_h+SGA and CAMI_h+MEGAHIT
利用2.1.2中现成的组装工具来得到组装图和标签.
3.3 评估标准
为了确定所有数据集中的contigs的ground-truth物种,我们能使用TAXAssign v0.4对contigs进行标记(https://github.com/umerijaz/TAXAassign)
这个工具:TAXAssign使用BLAST(基本局部对比搜索工具)在NCBI中以给定百分比进行搜索,而对于孤立的contigs(对应的零度顶点)不进行搜索.
为了评估GraphBin,使用了四个量:1.precision,2.recall召回率,3.F1-score,4.ARI(Adjusted Rand Index).
4 结果和讨论
Graph能够提升性能的因素是提供了contigs连接之间的有价值的信息,这些信息是其他工具所没有的.
蓝色表示原始工具得分,橙色代表graphbin得分.
可以看到graphbin在每一个数据集中都能获得更好的效果.
4.1 模拟数据集的结果
对于某些性能指标效果不好的原因是丢弃了一些短的bp序列,因此一些相关的指标大大降低.
4.2 沙龙数据集的结果
F1的增加不像模拟数据集那么显著,主要是因为真实数据集的复杂性增加,不均匀的覆盖和物种之间共享的基因组片段,导致装配图出现变化.
4.3 CAMI数据集的结果
随着数据集复杂性的增加，分类结果的改善逐渐减小,也就不是很明显了.
高复杂度数据集可能组装错误的contigs或者物种之间共享的contigs,导致初始分箱结果错误,
影响标签传播过程,导致精度和ARI下降,同时对于高复杂度的数据集,bintools对于bins数量的估计可能变得不准确.
4.4 装配图的可视化
属于粪肠杆菌和金黄色葡萄球菌的Contigs分别呈绿色和黄色,灰色表示未考虑和被丢弃的contigs表示灰色,红色圈表示被错置的contigs.
4.5 配置环境
实验的源代码是使用Python 3.6.5实现的，运行在Linux系统上，该系统有Ubuntu 18.04.1 LTS、16G内存和Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz, 4个CPU核。
5 结论
现有的分类工具在分类短序列,低丰度物种序列以及近缘物种序列时存在问题,大多数现有的bin工具会丢弃短序列(如小于1000bp)
GraphBin通过使用装配图中发现的信息，然后进行标签传播，来细化现有的分箱工具的分箱结果。
实验结果表明，该方法通过修正误分的contigs和对被现有工具丢弃的contigs进行bin分享，对bins结果进行了改进
存在的问题:
我们的方法目前使用二元连通性信息(即未加权边)，标签传播算法在预测物种边界上顶点的标签时存在不一致的问题,可能会导致GraphBin的精度降低
我们还打算通过引入概率模型和更多基因组特征(如重叠长度和覆盖信息)来改进标签传播算法。
此外，复杂宏基因组数据集的组装过程可能会在组装图中产生错误组装的contigs(例如，来自不同基因组的片段拼接)以及不可靠的连接(例如，由于嵌合读)。因此，
可以改进地方:如何利用噪声组装图改进宏基因组分类是值得探讨的问题。
