CPM 2019

30th Annual Symposium on Combinatorial Pattern Matching

Pisa, Italy, June 18-20, 2019


Papers and Proceedings

Local information


Keynote speakers

Paweł Gawrychowski (University of Wrocław, Poland)

Paweł Gawrychowski

How to exploit periodicity

Periodicity is a fundamental combinatorial property of strings. We say that p is a period of a string s[1..n] if s[i]=s[i+p] for every i such that both s[i] and s[i+p] are defined. While this notion seems interesting on its own, it can be often used as a tool for designing efficient algorithms. At a high level, many of such algorithms operate differently depending on whether a given string does or does not have a small period, where small usually means smaller than half of its length (or, say, quarter). In other words, we design an algorithm that is efficient if the given string is repetitive, and another algorithm that is efficient if the given string is non-repetitive, in every case carefully exploiting either the periodicity or the fact that input looks “random”, and then run the appropriate algorithm. Of course, in some cases, one needs to proceed in a more complex manner, and instead of classifying the whole string look at its substrings and process each of them differently depending on its structure. I will survey some of such results, including the recent generalization of periodicity that can be applied in approximate pattern matching.

Antonio Restivo (University of Palermo, Italy)

Antonio Restivo

Some variations on Lyndon words

Michal Ziv-Ukelson (Ben Gurion University of the Negev, Israel)

Michal Ziv-Ukelson

Stringology combats microbiological threats

A major concern worldwide is the acquisition of antibiotic resistance by pathogenic bacteria. Genomic elements carrying resistance and virulence function can be acquired through horizontal gene transfer, yielding a broad spread of evolutionary successful elements, both within and in between species, with devastating effect. Recent advances in pyrosequencing techniques, combined with global efforts to study infectious diseases, yield huge and rapidly-growing databases of microbial genomes. This big new data statistically empowers genomic-context based approaches to functional analysis: the idea is that groups of genes that are clustered locally together across many genomes usually express protein products that interact in the same biological pathway (e.g. operons). Identifying and interpreting microbial gene context in huge data requires efficient string-based data mining algorithms. Additionally, new computational challenges are raised by the need to study the grammar\semantics and evolutionary spreading patterns of microbial gene context. We will review previous related works on the subject and discuss some new problem variants inspired by this application.