Indexing huge collections of strings, such as those produced by the widespread sequencing technologies, heavily relies on multistring generalizations of the Burrows–Wheeler transform (BWT) and the longest common prefix (LCP) array, since solving efficiently both problems are essential ingredients of several algorithms on a collection of strings, such as those for genome assembly. In this article, we explore a multithread computational strategy for building the BWT and LCP array. Our algorithm applies a divide and conquer approach that leads to parallel computation of multistring BWT and LCP array.

Indexing huge collections of strings, such as those produced by the widespread sequencing technologies, heavily relies on multistring generalizations of the Burrows-Wheeler transform (BWT) and the longest common prefix (LCP) array, since solving efficiently both problems are essential ingredients of several algorithms on a collection of strings, such as those for genome assembly. In this article, we explore a multithread computational strategy for building the BWT and LCP array. Our algorithm applies a divide and conquer approach that leads to parallel computation of multistring BWT and LCP array.

Bonizzoni, P., Della Vedova, G., Pirola, Y., Previtali, M., Rizzi, R. (2019). Multithread multistring burrows-wheeler transform and longest common prefix array. JOURNAL OF COMPUTATIONAL BIOLOGY, 26(9), 948-961 [10.1089/cmb.2018.0230].

Multithread multistring burrows-wheeler transform and longest common prefix array

Bonizzoni, Paola;Della Vedova, Gianluca;Pirola, Yuri;Previtali, Marco;Rizzi, Raffaella
2019

Abstract

Indexing huge collections of strings, such as those produced by the widespread sequencing technologies, heavily relies on multistring generalizations of the Burrows-Wheeler transform (BWT) and the longest common prefix (LCP) array, since solving efficiently both problems are essential ingredients of several algorithms on a collection of strings, such as those for genome assembly. In this article, we explore a multithread computational strategy for building the BWT and LCP array. Our algorithm applies a divide and conquer approach that leads to parallel computation of multistring BWT and LCP array.
Articolo in rivista - Articolo scientifico
Burrows-Wheeler transform; longest common prefix array; multithreading; parallel algorithms;
Burrows–Wheeler transform longest common prefix array multithreading parallel algorithms
English
2019
26
9
948
961
reserved
Bonizzoni, P., Della Vedova, G., Pirola, Y., Previtali, M., Rizzi, R. (2019). Multithread multistring burrows-wheeler transform and longest common prefix array. JOURNAL OF COMPUTATIONAL BIOLOGY, 26(9), 948-961 [10.1089/cmb.2018.0230].
File in questo prodotto:
File Dimensione Formato  
journ-art-19-jcb.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 914.71 kB
Formato Adobe PDF
914.71 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/265924
Citazioni
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 8
Social impact