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
No
paper
Scientifica
String Graph; Burrows-Wheeler Transform; Bioinformatics; External Memory; Algorithms
English
International Workshop on Algorithms in Bioinformatics (WABI) SEP 08-10
978-3-662-44752-9
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].
Bonizzoni, P; DELLA VEDOVA, G; Pirola, Y; Previtali, M; Rizzi, R
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