The colored longest common prefix array computed via sequential scans

Marinella Sciortino, Giovanna Rosone, Davide Verzotto, Giovanna Rosone

Risultato della ricerca: Otherpeer review

2 Citazioni (Scopus)


Due to the increased availability of large datasets of biological sequences, tools for sequence comparison are now relying on efficient alignment-free approaches to a greater extent. Most alignment-free approaches require the computation of statistics when comparing sequences, even if such computations may not scale well in in internal memory when very large collections of long sequences are considered. In this paper, we present a new conceptual data structure, the colored longest common prefix array (cLCP), that allows to efficiently tackle several problems with an alignment-free approach. In fact, we show that such a data structure can be computed via sequential scans in semi-external memory. By using cLCP, we propose an efficient lightweight strategy to solve the multi-string Average Common Substring (ACS) problem, that consists in the pairwise comparison of a single string against a collection of m strings simultaneously, in order to obtain m ACS induced distances. Experimental results confirm the high practical efficiency of our approach.
Lingua originaleEnglish
Numero di pagine15
Stato di pubblicazionePublished - 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Entra nei temi di ricerca di 'The colored longest common prefix array computed via sequential scans'. Insieme formano una fingerprint unica.

Cita questo