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 FMindex and Burrows-Wheeler Transform (BWT). 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.
Bonizzoni, P., Della Vedova, G., Pirola, Y., Previtali, M., & Rizzi, R. (2016). FSG: Fast string graph construction for de novo assembly of reads data. In 12th International Symposium on Bioinformatics Research and Applications, ISBRA 2016; Minsk; Belarus; 5 June 2016 through 8 June 2016 (pp.27-39). Springer Verlag.
Citazione: | Bonizzoni, P., Della Vedova, G., Pirola, Y., Previtali, M., & Rizzi, R. (2016). FSG: Fast string graph construction for de novo assembly of reads data. In 12th International Symposium on Bioinformatics Research and Applications, ISBRA 2016; Minsk; Belarus; 5 June 2016 through 8 June 2016 (pp.27-39). Springer Verlag. |
Tipo: | slide + paper |
Carattere della pubblicazione: | Scientifica |
Presenza di un coautore afferente ad Istituzioni straniere: | No |
Titolo: | FSG: Fast string graph construction for de novo assembly of reads data |
Autori: | Bonizzoni, P; Della Vedova, G; Pirola, Y; Previtali, M; Rizzi, R |
Autori: | |
Data di pubblicazione: | 2016 |
Lingua: | English |
Nome del convegno: | 12th International Symposium on Bioinformatics Research and Applications, ISBRA 2016 |
ISBN: | 9783319387819 |
Serie: | LECTURE NOTES IN COMPUTER SCIENCE |
Appare nelle tipologie: | 02 - Intervento a convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
conf-paper-16-isbra.pdf | Articolo principale | N/A | Administrator Richiedi una copia |