вычисления расстояния Левенштеина на разных языках программирования доступны в [ 2 ]. Это расстояние между двумя строками длины m и n вычисляется методом динамического программирования [ 3 ], выполняющим O(mn) операции с линеинои памятью O(min(n, m)).

Напомним, что ДНК состоит из двух комплементарных цепеи. Поэтому в зависимости от цепи, каждыи ген транскрибируется в определённом направлении, а некодирующие области различаются в зависимости от взаимного направления транскрипции фланкирующих генов. Участок РНК, соответствующии вырожденному инвертированному повтору на ДНК, может образовать шпильку, то есть вторичную структуру, в которои комплементарные нуклеотиды из начала и из конца соединяются между собои. Середина образует петлю, в которои цепь РНК изгибается в пространстве. Нуклеотиды петли не обязательно комплементарны. Петля не может быть короче трёх и обычно содержит не меньше четырёх нуклеотидов. Большие петли уменьшают стабильность шпильки. Нуклеотиды, не входящие в состав петли, образуют плечи шпильки. Некомплементарность нуклеотидов плеч также уменьшает стабильность шпильки, поскольку некомплементарные нуклеотиды образуют выпячивания. Мы классифицируем шпильки по трём параметрам: длине плеча, длине петли и расстоянию между одним плечом и участком, комплементарным другому плечу в метрике Левенштеина.

Шпильки играют важную роль в регуляции экспрессии генов, поскольку во многих случаях служат терминаторами транскрипции, то есть прерывают процесс создания РНК по ДНК. Примеры рассмотрены в работах [ 4-9 ]. Шпильки участвуют в регуляции экспрессии генов, часто образуя сложные структуры; они могут служить для предотвращения конфликтов, возникающих в ходе транскрипции генов на комплементарных цепях ДНК [ 10-11 ]. Шпилька на 3'-конце РНК служит для стабилизации транскрипта, предотвращая его разрушение ферментами РНКазами.

Также вырожденные инвертированные повторы могут служить саитами кооперативного связывания транскрипционных факторов с ДНК. В этом случае две копии фактора связывают два участка ДНК, расположенные на комплементарных цепях ДНК. С другои стороны, инвертированные повторы возникают в результате хромосомных перестроек, в частности, на краях вставок мобильных элементов. Сравнительныи анализ хромосомных структур даёт важную информацию об эволюции генома [ 12 ]. Материалы NC_016768 Mycobacterium tuberculosis KZN 4207 NC_016804 Mycobacterium bovis BCG str. Mexico NC_016946 Mycobacterium intracellulare ATCC 13950 NC_016947 Mycobacterium intracellulare MOTT-02 NC_016948 Mycobacterium intracellulare MOTT-64 NC_017522 Mycobacterium tuberculosis CCDC5180 NC_017523 Mycobacterium tuberculosis CCDC5079 NC_017524 Mycobacterium tuberculosis CTRI-2 NC_017904 Mycobacterium sp. MOTT36Y NC_018027 Mycobacterium chubuense NBB4 NC_018078 Mycobacterium tuberculosis KZN 605 NC_018143 Mycobacterium tuberculosis H37Rv NC_018289 Mycobacterium smegmatis str. MC2 155 Методы

Независимо рассматривались кодирующие области (гены) и некодирующие (межгенные) области трёх типов:  межу сходящимися генами;  между расходящимися генами;  между последовательно расположенными генами.

Учитывались только кодирующие области, размеченные в аннотациях геномов. Для этого исследования написана программа, реализующая оригинальныи алгоритм поиска вырожденных инвертированных повторов и привязки их к областям генома. Программа написана на языке Python и работает следующим образом:  Из основного кода вызывается функция find_hairpins_in_file, она получает на вход gbk-файл, с помощью вспомогательных функций получает из него нуклеотидную последовательность, находит на ней координаты генов. Затем для каждой межгенной области (добавляя 20 н. с каждой стороны) вызывается функция find_cross_hairpins, после чего результаты делятся по типам межгенных областей и возвращаются в основную программу, где для всех файлов уже вычисляются средние величины и т.д.  Функция find_cross_hairpins получает на вход последовательность нуклеотидов, минимальную длину плеча шпильки (по умолчанию это 7 н.), максимальную величину петли (по умолчанию это 14 н). В цикле по величине петли ищутся шпильки с минимальной длиной плеча (минимальная длина повышается, если петля достигает ее значения) и удовлетворяющие заданному расстоянию Левенштейна между плечами. Каждая найденная шпилька, передается в функцию find_all_possible_hairpins (с условием, чтобы в итоге максимальная длина плеча была ограничена 35 н.). Параметры шпилек и их расстояния до генов записываются в массив. Вызывается функция check_and_delete_hairpins. Этот результат возвращается в find_hairpins_in_file.  Функция find_all_possible_hairpins получает на вход последовательность, у которой посередине найдена шпилька, и параметры этой шпильки. Функция добавляет по одному нуклеотиду с каждой стороны и проверяет, можно ли ожидать шпильку большей длины. Возвращает все возможные варианты более длинных шпилек.  Функция check_and_delete_hairpins получает на вход массив из шпилек с их параметрами и расстояниями до генов. Сортирует шпильки по расстоянию до левого гена. Вычисляет отношение перекрытия соседних шпилек к длине (оба плеча и петля) более короткой из них, если перекрытие превышает порог (по умолчанию - 70%), то удаляет короткую шпильку. При одинаковой длине удаляет ту, в которой больше расстояние Левенштейна между плечами. Возвращает оставшиеся шпильки.

Время счёта на процессоре с двумя ядрами составило примерно 10 минут на один геном. Результаты и обсуждение

Всего рассмотрено 187759 межгенных областеи, из них 123737 последовательных, 31994 сходящихся и 32028 расходящихся (рис. 1).

Большое число вырожденных инвертированных повторов, соответствующих шпилькам с длинои петли четыре нуклеотида, позволяет предполагать, что значительная доля этих повторов деиствительно соответствует шпилькам на РНК. Две зависимости расстояния между шпилькои и ближаишим геном от параметров шпильки существенно различаются между собои для двух типов межгенных областеи. Это говорит о различнои роли шпилек в зависимости от типа области. Они Рис.1. Соотношение чисел межгенных областей трёх типов в геномах рассмотренных микобактерий Размер петли Рис.2. Зависимость среднего расстояния между шпилькой и ближайшим к ней геном от размера петли для разных размеров плеча шпильки в области между сходящимися генами Рис.3. Зависимость среднего расстояния между шпилькой и ближайшим к ней геном от размера петли для разных размеров плеча шпильки в области между расходящимися генами Для последовательных генов заметен рост расстояния между шпильками всех размеров и 7-9 10-15 16+ началом гена при увеличении петли. Также с увеличением петли растет расстояние между короткими шпильками и концом гена. При величине петли в 6-8 нуклеотидов, среднее расстояние между короткими шпильками и началом гена, становится больше, чем между началом гена и длинными или средними шпильками. В областях между расходящимися генами шпильки находятся ближе к генам, чем в областях между сходящимися генами.

Рис.4. Зависимость среднего расстояния между шпилькой и ближайшим к ней геном от размера петли для разных размеров плеча шпильки и разных вариантов примыкания шпильки к гену в области между последовательными генами В областях между последовательными генами короткие шпильки в среднем находятся ближе к началам генов, а средние и длинные ближе к концам. Средние длины некодирующих областеи между последовательно расположенными и сходящимися генами приблизительно равны для разных таксономических групп (табл.1). А некодирующие области между расходящимися генами в среднем значительно длиннее у всех групп. В то время как среднее расстояние до ближаишего гена более короткое именно для расходящихся генов. То есть этот эффект нельзя объяснить простым увеличением длин некодирующих областеи.

Табл.1. Среднее расстояние между генами в зависимости от типа расположения генов для разных таксономических групп Последовательные гены Расходящиеся гены Сходящиеся гены Микобактерии Актинобактерии Цианобактерии

Фирмикуты Выводы 77,1 100,4 135,9 112,9 174,6 211,0 251,8 259,0 71,4 104,7 124,4 146,4 Определены интервалы типичных значении параметров шпилек и расстоянии от них до ближаиших генов у микобактерии. Полученные результаты могут служить основои для дальнеишего предсказания регуляции экспрессии генов. Также полученные результаты могут быть использованы для предсказания частоты хромосомных перестроек, в результате которых возникают инвертированные повторы. Это позволяет уточнить ранее рассмотренную модель эволюции генома.

Работа выполнена за счёт гранта Российского научного фонда (проект 14-50-00150). Литература