Г. А. Хазиев, О. А. Зверков, С. А. Пирогов, А. В. Селиверстов, В. А. Любецкий

Минимальное расстояние между случайной последовательностью и совершенными палиндромами

Для последовательности x рассматривается величина imp(x) — минимальное расстояние Левенштейна, нормированное на длину x, между x и словами вида wc(w), где w пробегает префиксы x, а преобразование c обращает порядок букв и заменяет каждую букву на комплементарную. Мы провели масштабные вычислительные эксперименты для независимых случайных нуклеотидных последовательностей различной длины и GC-состава. Показано, что последовательности, расстояние от которых до совершенного палиндрома значительно меньше типичного, встречаются редко. Среднее и медиана imp(x) существенно зависят от GC-состава. Для длинных последовательностей их зависимость от длины ослабевает, тогда как для коротких последовательностей остается выраженной. Среднеквадратичное отклонение изменяется с GC-составом значительно слабее. Полученные эмпирические квантили могут использоваться при выборе порогов для поиска несовершенных палиндромов в биоинформатических данных.

КЛЮЧЕВЫЕ СЛОВА: палиндром, случайная последовательность, GC-состав, биоинформатика.