Combinatorial and Algorithmic Aspects of Sequence Processing

Summary

Sequences (aka strings or words) form the most basic and natural data structure. They occur whenever information is electronically transmitted (as bit streams), when natural language text is spoken or written down (as words over, for example, the Latin alphabet), in the process of heredity transmission in living cells (as DNA sequence) or the protein synthesis (as sequence of amino acids), and in many more different contexts. Given this universal form of representing information, algorithms to efficiently search through, analyze, (de-)compress, match, and encode and decode strings are therefore of chief interest. Combinatorial problems about strings lie at the core of such algorithmic questions. Many such combinatorial problems are common in the string processing efforts in the different fields of application.

The object of concern of this seminar, sequences, implies a large degree of generality. It plays an essential role in many fields and constitutes a true cross section area. Hence, the seminar was designed to bring together researchers from different disciplines whose interest are string processing algorithms and related combinatorial problems on words. Scientists working in the following fields were invited to consider the seminar's topic from a wide range of perspectives:

• Combinatorics on words
• Computational biology
• Stringology
• Natural computing
• Machine learning

This Dagstuhl seminar was attended by 40 researchers from 13 countries. Everyone of the five topics above was about equally represented. Given the extremely interdisciplinary approach of this meeting it was an obvious necessity to hold a tutorial on each one of the participating research areas. These tutorials were held over the first and the morning of the second seminar day (see the scientific schedule below). They provided a good introduction for the non-specialists and triggered the first scientific discussions and exchanges.

Given the quality of presentations on this seminar and the constructive intensity of discussions between and after the talks, it is self-evident that follow-ups will be attempted. After this initial meeting of different communities, where common problems were identified, personal contacts established and first cooperations initiated, further events can be sharpened in focus and more on particular cross section topics regarding combinatorial and algorithmic problems in sequence processing.

Finally, we would like to say that the organization of a meeting for researchers of so unusually diverse fields bears a certain risk. However, it can be said that the event turned out better than expected. It was more than worthwhile to have taken that risk. We are grateful to all participants for their contributions to this successful seminar as well as to the staff of Schloss Dagstuhl for their perfect service.