FSG: Fast String Graph Construction for De Novo Assembly
FSG: Fast String Graph Construction for De Novo Assembly
复制标题
FSG：用于 De Novo 组装的快速字符串图构建
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Raffaella Rizzi
中科院分区：
文献类型：
--
作者：
P. Bonizzoni;G. D. Vedova;Yuri Pirola;M. Previtali;Raffaella Rizzi
下一代读取集合的字符串图是一种无损数据表示，对于基于重叠布局共识范式的从头组装程序来说是基础。在本文中，我们探索一种基于 FM 索引以及 Burrows 和 Wheeler 变换来计算字符串图的新颖方法。我们描述了一种简单的算法，该算法仅使用读取集合的 FM 索引表示来构建字符串图，而不访问输入读取。我们的算法已作为独立模块集成到字符串图汇编器（SGA）中来构造字符串图。新的集成汇编器已经在标准基准测试上进行了评估，结果表明快速字符串图 (FSG) 明显快于 SGA，同时保持了主内存的适度使用，并显示了在多线程上运行 FSG 的实际优势。此外，我们还研究了覆盖率对运行时间的影响。
The string graph for a collection of next-generation reads is a lossless data representation that is fundamental for de novo assemblers based on the overlap-layout-consensus paradigm. In this article, we explore a novel approach to compute the string graph, based on the FM-index and Burrows and Wheeler Transform. We describe a simple algorithm that uses only the FM-index representation of the collection of reads to construct the string graph, without accessing the input reads. Our algorithm has been integrated into the string graph assembler (SGA) as a standalone module to construct the string graph. The new integrated assembler has been assessed on a standard benchmark, showing that fast string graph (FSG) is significantly faster than SGA while maintaining a moderate use of main memory, and showing practical advantages in running FSG on multiple threads. Moreover, we have studied the effect of coverage rates on the running times.
影响因子：
7
作者：
Salzberg, Steven L.;Phillippy, Adam M.;Yorke, James A.
通讯作者：
Yorke, James A.