Keynote speakers
Paweł Gawrychowski (University of Wrocław, Poland)
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)
Some variations on Lyndon words
In this paper we compare two finite words u and v by the lexicographical order of the infinite words u^omega and v^omega. Informally, we say that we compare u and v by the infinite order. We show several properties of Lyndon words expressed using this infinite order. The innovative aspect of this approach is that it allows to take into account also non trivial conditions on the prefixes of a word, instead that only on the suffixes. In particular, we derive a result of Ufnarovskij [V. Ufnarovskij, Combinatorial and asymptotic methods in algebra, 1995] that characterizes a Lyndon word as a word which is greater, with respect to the infinite order, than all its prefixes. Motivated by this result, we introduce the prefix standard permutation of a Lyndon word and the corresponding (left) Cartesian tree. We prove that the left Cartesian tree is equal to the left Lyndon tree, defined by the left standard factorization of Viennot [G. Viennot, Algèbres de Lie libres et monoïdes libres, 1978]. This result is dual with respect to a theorem of Hohlweg and Reutenauer [C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, 2003].
Michal Ziv-Ukelson (Ben Gurion University of the Negev, Israel)
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.