The colored longest common prefix array computed via sequential scans

Marinella Sciortino, Giovanna Rosone, Davide Verzotto, Giovanna Rosone

Risultato della ricerca: Conference contribution

3 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
Titolo della pubblicazione ospiteString Processing and Information Retrieval, 25th International Symposium, SPIRE 2018, Lima, Peru, October 9-11, 2018, Proceedings
Numero di pagine15
Stato di pubblicazionePublished - 2018

Serie di pubblicazioni


All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???


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

Cita questo