Удивительная алгебра сравнения строк

Доклад будет посвящен классической задаче вычисления наибольшей общей подпоследовательности (Longest Common Subsequence, LCS) для пары строк, также известной в мире биоинформатики как задача выравнивания последовательностей (Sequence Alignment). Решение из учебника основано на методе динамического программирования и кажется единственно возможным. Мы увидим, что это не так: предварительно обобщив задачу, ее можно эффективно решить при помощи рекурсии, где «склеивание» подзадач производится при помощи на первый взгляд совершенно посторонней структуры — моноида Гекке или «липких кос», определяемого через тропическое матричное умножение и очень похожего на классическую группу кос. Такое решение представляет не только теоретический интерес, но и позволяет получить эффективные алгоритмы для сравнения сжатых строк без их декомпрессии, параллельного сравнения строк, а также решения некоторых практических задач биоинформатики. В последние годы появляется все больше приложений этого метода: приближенный поиск по образцу в режиме малого редакционного расстояния; сравнение динамических строк; сравнение периодических строк; локальное сравнение строк при помощи оракула. Мы опишем основные идеи некоторых из них.