In this paper we present an efficient external memory algorithm to compute the string graph from a collection of reads, which is a fundamental data representation used for sequence assembly. Our algorithm builds upon some recent results on lightweight Burrows-Wheeler Transform (BWT) and Longest Common Prefix (LCP) construction providing, as a by-product, an efficient procedure to extend intervals of the BWT that could be of independent interest. We have implemented our algorithm and compared its efficiency against SGA-the most advanced assembly string graph construction program

Bonizzoni, P., DELLA VEDOVA, G., Pirola, Y., Previtali, M., Rizzi, R. (2014). Constructing String Graphs in External Memory. In Algorithms in Bioinformatics (pp.311-325). Springer [10.1007/978-3-662-44753-6_23].

Constructing String Graphs in External Memory

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;PIROLA, YURI;PREVITALI, MARCO;RIZZI, RAFFAELLA
2014

Abstract

In this paper we present an efficient external memory algorithm to compute the string graph from a collection of reads, which is a fundamental data representation used for sequence assembly. Our algorithm builds upon some recent results on lightweight Burrows-Wheeler Transform (BWT) and Longest Common Prefix (LCP) construction providing, as a by-product, an efficient procedure to extend intervals of the BWT that could be of independent interest. We have implemented our algorithm and compared its efficiency against SGA-the most advanced assembly string graph construction program
paper
String Graph; Burrows-Wheeler Transform; Bioinformatics; External Memory; Algorithms
English
International Workshop on Algorithms in Bioinformatics (WABI) SEP 08-10
2014
Algorithms in Bioinformatics
978-3-662-44752-9
2014
8701
311
325
reserved
Bonizzoni, P., DELLA VEDOVA, G., Pirola, Y., Previtali, M., Rizzi, R. (2014). Constructing String Graphs in External Memory. In Algorithms in Bioinformatics (pp.311-325). Springer [10.1007/978-3-662-44753-6_23].
File in questo prodotto:
File Dimensione Formato  
conf-paper-14-wabi.pdf

Solo gestori archivio

Descrizione: Articolo principale
Dimensione 286.96 kB
Formato Adobe PDF
286.96 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/52951
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
Social impact