Выравнивание скрытого палиндрома

Цель работы состоит в обобщении известных алгоритмов для решения новых задач, возникающих в биоинформатике. Рассмотрены алгоритмы для оптимизации редакционного расстояния между последовательностями, из которых первая известна, а вторая вычисляется как скрытый палиндром произвольной длины. Существенно, что длина искомого палиндрома определяется в результате оптимизации. В первой задаче требуется выбрать палиндром из ансамбля палиндромов, определяемых второй входной последовательностью. При этом исходные последовательности могут не содержать искомый палиндром целиком. Но вторая последовательность содержит половину от искомого палиндрома. Первая входная последовательность используется для оптимизации. В другой задаче такой палиндром может быть частичным, когда лишь префикс комплементарен суффиксу. Такой частичный палиндром образует шпильку. Новые алгоритмы работают за квадратичное время, что быстрее, чем полный перебор допустимых палиндромов. Алгоритмы существенно используют линейную зависимость редакционного расстояния от длины сплошной делеции или вставки. С другой стороны, алгоритм для решения первой задачи позволяет вычислить сходство данной последовательности с каким-либо палиндромом. Однако в общем случае сравнение двух разных последовательностей не сводится к поиску палиндромов в каждой из них. Также обсуждается быстрый поиск субоптимальных решений. Созданы программные реализации рассмотренных алгоритмов. Они доступны по адресу lab6.iitp.ru/~/pali. Приведены некоторые примеры нуклеотидных последовательностей с вырожденными инвертированными повторами. В частности, рассмотрены инвертированные повторы в некодирующих областях ДНК пластид у цветковых растений и гены микроРНК. Также обсуждается возможное применение нашего метода для поиска консервативных вторичных структур РНК.