Recently, Holt and McMillan [Bioinformatics 2014, ACM-BCB 2014] have proposed a simple and elegant algorithm to merge the Burrows-Wheeler transforms of a collection of strings. In this paper we show that their algorithm can be improved so that, in addition to the BWTs, it also merges the Longest Common Prefix (LCP) arrays. Because of its small memory footprint this new algorithm can be used for the final merge of BWT and LCP arrays computed by a faster but memory intensive construction algorithm.
Lightweight BWT and LCP merging via the gap algorithm
EGIDI, Lavinia;MANZINI, Giovanni
2017-01-01
Abstract
Recently, Holt and McMillan [Bioinformatics 2014, ACM-BCB 2014] have proposed a simple and elegant algorithm to merge the Burrows-Wheeler transforms of a collection of strings. In this paper we show that their algorithm can be improved so that, in addition to the BWTs, it also merges the Longest Common Prefix (LCP) arrays. Because of its small memory footprint this new algorithm can be used for the final merge of BWT and LCP arrays computed by a faster but memory intensive construction algorithm.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
gap_selfarch.pdf
Open Access dal 19/09/2018
Descrizione: Main paper
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
391.73 kB
Formato
Adobe PDF
|
391.73 kB | Adobe PDF | Visualizza/Apri |
|
lightweightLNCS.pdf
file disponibile solo agli amministratori
Tipologia:
Versione Editoriale (PDF)
Licenza:
DRM non definito
Dimensione
504.22 kB
Formato
Adobe PDF
|
504.22 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.
