BOSS: a novel scaffolding algorithm based on an optimized scaffold graph
BOSS: a novel scaffolding algorithm based on an optimized scaffold graph
复制标题
BOSS：一种基于优化脚手架图的新型脚手架算法
DOI：
10.1093/bioinformatics/btw597
复制
发表时间：
2017-01-15
期刊：
影响因子：
5.8
通讯作者：
Wu, Fang-Xiang
中科院分区：
文献类型：
--
作者：
Luo, Junwei;Wang, Jianxin;Wu, Fang-Xiang
动机：支架化是拼接过程中的一个重要步骤，其目的是确定片段化重叠群的方向和顺序，使拼接结果更加完整。大多数现有的脚手架工具采用脚手架图的方法。然而，由于基因组中的重复区域，测序错误和不均匀的测序深度，构建一个准确的支架图仍然是一个挑战性的任务。结果：在本文中，我们提出了一种新的算法（称为BOSS），它采用配对读段的脚手架。为了构建支架图，BOSS利用插入大小的分布来决定是否应该添加两个顶点（重叠群）之间的边以及应该如何对边进行加权。此外，BOSS采用迭代策略来检测虚假的边缘，删除可以保证支架图中没有矛盾。基于构建的支架图，BOSS采用启发式算法对顶点（重叠群）进行排序，然后生成支架。实验结果表明，BOSS产生更令人满意的支架，与其他流行的支架工具上的真实的测序数据的四个基因组。可用性和实施：BOSS可在https://github.com/bioinfomaticsCSU/BOSS公开下载。联系方式：jxwang@mail.csu.edu.cn补充信息：补充数据可从生物信息学在线网站获得。
Motivation: While aiming to determine orientations and orders of fragmented contigs, scaffolding is an essential step of assembly pipelines and can make assembly results more complete. Most existing scaffolding tools adopt scaffold graph approaches. However, due to repetitive regions in genome, sequencing errors and uneven sequencing depth, constructing an accurate scaffold graph is still a challenge task. Results: In this paper, we present a novel algorithm (called BOSS), which employs paired reads for scaffolding. To construct a scaffold graph, BOSS utilizes the distribution of insert size to decide whether an edge between two vertices (contigs) should be added and how an edge should be weighed. Moreover, BOSS adopts an iterative strategy to detect spurious edges whose removal can guarantee no contradictions in the scaffold graph. Based on the scaffold graph constructed, BOSS employs a heuristic algorithm to sort vertices (contigs) and then generates scaffolds. The experimental results demonstrate that BOSS produces more satisfactory scaffolds, compared with other popular scaffolding tools on real sequencing data of four genomes. Availability and Implementation: BOSS is publicly available for download at https://github.com/bioinfomaticsCSU/BOSS. Contact: jxwang@mail.csu.edu.cn Supplementary information: Supplementary data are available at Bioinformatics online.