The colored longest common prefix array computed via sequential scans

Marinella Sciortino, Giovanna Rosone, Davide Verzotto, Giovanna Rosone

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (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.
Original languageEnglish
Title of host publicationString Processing and Information Retrieval, 25th International Symposium, SPIRE 2018, Lima, Peru, October 9-11, 2018, Proceedings
Number of pages15
Publication statusPublished - 2018

Publication series


All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Cite this