Методы анализа символьных последовательностей развивались, как в прикладных исследованиях (коммуникационные системы, анализ больших биологических молекул; разработка систем акустической диагностики и систем автоматического распознавания речи и др.), так и в теоретических исследованиях (теория автоматов, теория формальных грамматик. алгоритмы поиска вхождений и т.п.). В 80-е годы прошлого столетия были осознаны связи между методами анализа символьных последовательностей в разных областях и сделаны первые попытки вычленить общие их основы. [См., например, Sankoff, D. and Kruskal, J. (eds.) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparision. Addison-Wesley Publishing Co., Reading, Massachusetts, 1983]

Изучение аналогий между проблемами и методами анализа символьных последовательностей из различных прикладных областей является весьма продуктивным. В частности, для анализа текстов на естественных языках, которые являются одним из главных объектов анализа в информационных технологиях, полезно знакомство с методами и подходами к анализу символьных последовательностей, выработанными в биологии. Это связано как с аналогиями между биологическими и естественными текстами, так и, прежде всего, с тем, что именно в биоинформатике разработка методов анализа последовательностей в последние годы происходила наиболее интенсивно.

В предлагаемом мини-курсе предполагается рассмотреть следующие темы:
- обобщения задачи поиска оптимальных путей в графах (гиперграфы, статистические суммы, полукольца) – как алгоритмическая основа многих задач анализа символьных последовательностей;
- скрытые марковские модели и их использование для анализа символьных последовательностей;
- примеры из биологии (сравнительная геномика, распознавание функционально значимых областей) и лингвистики (порождающие грамматики, коллокации, анализ потоков сообщений)