Об алгебре сравнения строк расскажут на семинаре в ЛЭТИ

Об алгебре сравнения строк расскажут на семинаре в ЛЭТИ

Приглашаем всех желающих на семинар преподавателя Уорикского университета Александра Тискина, посвященный решению задачи выравнивания последовательностей.

26.03.2019 168

Семинар будет посвящен классической задаче вычисления наибольшей общей подпоследовательности (Longest Common Subsequence, LCS) для пары строк, известной в биоинформатике как задача выравнивания последовательностей (Sequence Alignment).

Решение из учебника основано на методе динамического программирования и кажется единственно возможным. Однако, предварительно обобщив задачу, ее можно эффективно решить при помощи рекурсии, где «склеивание» подзадач производится при помощи структуры, определяемой через тропическое матричное умножение и похожей на классическую группу кос.

Такое решение представляет не только теоретический интерес, но и позволяет получить эффективные алгоритмы для сравнения сжатых строк без их декомпрессии, параллельного сравнения строк, а также решения некоторых практических задач биоинформатики.

В ходе семинара слушатели получат идеи для самостоятельного исследования.

28 марта, 17:25