2016/04/12 by Bonizzoni, Paola, Della Vedova, Gianluca, Pirola, Yuri +2
#Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Genomics (q-bio.GN)
paper · doi:10.48550/arxiv.1604.03587
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 paper, we explore a novel approach to compute the string graph, based on the FM-index and Burrows-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 SGA assembler as a standalone module to construct the string graph. The new integrated assembler has been assessed on a standard benchmark, showing that FSG is significantly faster than SGA while maintaining a moderate use of main memory, and showing practical advantages in running FSG on multiple threads.