LSG: An External-Memory Tool to Compute String Graphs for Next-Generation Sequencing Data Assembly

摘要

Abstract The large amount of short read data that has to be assembled in future applications, such as in metagenomics or cancer genomics, strongly motivates the investigation of disk-based approaches to index next-generation sequencing (NGS) data. Positive results in this direction stimulate the investigation of efficient external memory algorithms for de novo assembly from NGS data. Our article is also motivated by the open problem of designing a space-efficient algorithm to compute a string graph using an indexing procedure based on the Burrows–Wheeler transform (BWT). We have developed a disk-based algorithm for computing string graphs in external memory: the light string graph (LSG). LSG relies on a new representation of the FM-index that is exploited to use an amount of main memory requirement that is independent from the size of the data set. Moreover, we have developed a pipeline for genome assembly from NGS data that integrates LSG with the assembly step of SGA (Simpson and Durbin, 2012), a state-..." /> rel="meta" type="application/atom+xml" href="http://dx.doi.org/10.1089%2Fcmb.2015.0172" /> rel="meta" type="application/rdf+json" href="http://dx.doi.org/10.1089%2Fcmb.2015.0172" /> rel="meta" type="application/unixref+xml" href="http://dx.doi.org/10.1089%2Fcmb.2015.0172" /> 展开▼