2 Methods
2.2 Algorithm Overview
SPAdes 构建组装图和contig
规范化顶点和边的正反向
深入的利用 pair-end read 之间额外的连接信息
利用contig，pair-end links 和 coverage 信息进行分割分支和收缩无分支路径，来解开组装图的缠绕
最终输出 strain-specific 序列
2.3 Preprocessing
2.3.1 Canonize Strandedness
SPAdes 生成的组装图中有正负两个方向的链，这样在组装图中可能不能明显的显示相关性。VStrain 执行链方向的规范化，对每个顶点选择一个方向，所有邻接的边都用这个顶点选择的方向。随机选一个初始顶点，确定他的方向，然后检查边是否和他的方向一致，不一致就反转这条边。迭代运行，知道所有节点都有确定的方向，或者一个顶点必须有两个方向。对于后者，VStrain 将这个顶点分割成一对顶点，表示正向和反向链。没有入度的顶点称为source vertices 没有出度的称为 sink vertices。
2.3.2 Inferring Paired-End Links
用唯一kmer构建read和vertices之间的mapping关系。
如果一对pair-end reads中一个read 有顶点u中的至少一个k+1 mer， 另一个read中有顶点v中的至少一个k+1 mer，uv之间添加PE link。
2.4 Graph Disentanglement
解开纠缠图迭代的将分支顶点分割，然后构建无分支路径。
2.4.1 Branching Vertex Splitting
分支顶点 braching vertex ：入度或出度大于1.如果分支顶点入度出度都大于1，称为non-trivial vertex 复杂顶点，否则叫 trivial vertex 简单顶点。
对于简单顶点，如果v有多个入度，根据入度数量n，将v分成n个顶点，一一对应连接并赋予入节点和这个顶点对应的属性。如果v有一个出节点，将v分成的n个顶点分别连接这个出节点，并分别赋予入节点和这个顶点对应的属性。
对于复杂顶点v，如果有相同的入度（u_i,0->n）和出度（w_i,0->n）称为平衡顶点。将顶点根据入度/出度的分成n个顶点，如果ui和wi之间有PE link 或在一个contig中，将这两条边替换成ui-vi vi-wi，这种平衡分割对应uw之间的双射（一一对应的），大部分都可以被contig或PE link 推理出来。如何uw使用contig 和PE link 信息构成的时部分双射，VStrain利用覆盖深度信息找更多的一一对应匹配。如果ui-vi是u中最对应wi的，同时vi-wi 也是w中最对应ui的，ui wi 构成一个覆盖深度对。
不是所有复杂分支顶点都是平衡的，对应非平衡的顶点v，首先在他的邻接简单分支节点执行简单分割，目标是是构成平衡。若上面的能够通过contig ，PE link 或 coverage 信息构建双射，Vstrain 执行平衡分割
2.4.2 Non-branching Path Contraction
压缩非分支路径（将一个简单路径压缩成一个顶点）并将对应路径的属性添加到相应的顶点上。（mapping pair / coverage）
2.5 Contig-Based Path Extraction
执行完上面的步骤后，还可能有分支顶点，它们会混乱菌株完整路径的生成。
VStrain 迭代的选择最长的contig，然后再两个方向上拓展相应的子路径。如果当前顶点vn有多个vn+1分支节点，查看vn-1 和 vn+1的节点间 之间有没有1-1 的匹配信息。有的话就连接这个vn-1 vn vn+1形成更长的路径，否则，就停止延伸。如果vn时sink vertex 也停止，如果vn是同一个开始顶点在另一方向访问过的顶点，终止拓展，组合这两个拓展形成一个循环路径。
如果当前选择的contig可以拓展成一个完全路径（个人理解时有source 和 sink的路径）VStrain将这个路径输出为一个strain，否则，将这个路径压缩成一个顶点，等待未来的拓展，同时会更新覆盖深度图，VStrain 会将路径上的所有非分支节点覆盖深度中值估计为这个路径的覆盖深度，并在所有遍历的顶点中减少这个路径的覆盖深度。
VStrain 迭代的提取最有信心的路径，更新组装图，这可以得到更准确的构建。