17 декабря в 16:30 состоится очередное заседание семинара «Компьютерная алгебра». Руководитель семинара – д.ф.-м.н. С.А. Абрамов.
На заседании семинара будет представлен доклад на тему:
«Анализ несовершенных палиндромов»
Автор доклада:
Г.А. Хазиев (Институт проблем передачи информации имени А. А. Харкевича РАН)
Аннотация
Последовательность x называется совершенным палиндромом, если c(x) = x, где c – инверсия строки с заменой букв на комплементарные. Иначе последовательность называется несовершенным палиндромом. Последовательности, близкие к совершенным палиндромам, имеют различные приложения в биоинформатике. Рассматривается модификация алгоритма Нидлмана-Вунша, позволяющая вычислить минимальное редакционное расстояние между строкой и некоторым совершенным палиндромом за квадратичное время. Этот алгоритм реализован на языке Python использованием библиотеки numba. Обсуждается функция imp(x), оценивающая близость строки x к совершенному палиндрому. Рассматриваются алгоритмы выделения подпоследовательности в x, близкой к совершенному палиндрому. Один из этих алгоритмов удаляет некомплементарный участок, близкий к центру строки, т.е. удаляет петлю (loop). Такой участок характерен для несовершенных палиндромов, встречающихся в биологических задачах. В докладе также будет рассмотрена модификация алгоритма поиска минимального расстояния до совершенного палиндрома с некоторым обобщением понятия комплементарности.
Работа выполнена в рамках государственного задания ИППИ РАН, утвержденного Минобрнауки России.
Заседание семинара будет проходить в дистанционном режиме через Zoom. Ссылка для подключения будет направлена участникам семинара по электронной почте. По вопросу участия в семинаре просьба обращаться по электронной почте: moscowcaconf@gmail.com
