д.ф.-м.н. проф. зав лаб Любецкий Василий Александрович Институт проблем передачи информации РАН ( Лаборатория математических методов и моделей в биоинформатике (

С 2000 года нами опубликовано: 2 монографии и 1 вузовский учебник (по математике) и 23 статьи в математических журналах (Успехи мат. наук, Труды института им. Стеклова, Мат. Заметки и т.д.) А также – опубликовано 36 статей в биологических и информатических журналах (Молекулярная биология, Биофизика, Биохимия, FEMC, ВМС, JBCB, inSB,...) Подготовлено 2 докторские и 3 кандидатские диссертации (все – физ.-мат. науки, «теоретические основы информатики», «биоинформатика»)

Ежегодно наши аспиранты и сотрудники делают доклады примерно на 4-х международных конференциях (математических, биологических, информатических) За это время аспиранты и сотрудники приняли участие в выполнении: 25 грантов, 2 целевых грантов, 2 научных программ и 2 совместных тем по линии РАН-СНРС. Лауреаты премии «За лучшую публикацию в журнале Молекулярная биология» за 2005 год и премий некоторых зарубежных университетов

Тесно сотрудничаем с кафедрой «математической логики и теории алгоритмов» мех-мата МГУ, в частности, читаем там курс «Модели и алгоритмы в биоинформатике». Сотрудничаем с факультетом биоинформатики и биоинженерии МГУ, с факультетом ВМК. Регулярно ведем курсовые и дипломные работы, аспирантов. Сотрудничаем с аспирантурой Париж-7. Включая оплачиваемую работу.

1) Проблемы эффективности; 2) Модели и алгоритмы основных молекулярных процессов в клетке: геномы бактерий, растений, водорослей и простейших..... ДНК=геном – последовательность в 4х-буквенном алфавите {A,C,T,G} с характерной длиной 3 миллиона – 6 миллиардов позиций. Каждая буква называется «нуклеотид».

Модели и алгоритмы (компьютерный счет) Данные Результат

ген 1ген 2ген 3 инструкция для химической реакции – создается фермент; или для создания другой молекулы: белка или РНК сигнал 2сигнал 3 лидерная область 2 лидерная область 3 Ген считывается по сигналу из лидерной области! Ген и сигнал эволюционируют! инструкция для химической реакции 2 инструкция для химической реакции 3

Один из возможных типов сигналов (= регуляций): сайт посадки репрессор/активатор

Даны n последовательностей. Задача: найти систему сай- тов (=сигнал,мотив) s = {s 1,...,s k }, состоящую из сайтов s 1,...,s k, где k n. Все сайты имеют одинаковую длину. Определяем качество системы как сумму попарных близостей сайтов, составляющих систему (=качество сигнала). Leader region 1 Leader region n

Ищем систему сайтов с максимальным значением качества, т.е. ищем минимум целевого функционала F в пространстве всех возможных систем:

Идея нашего алгоритма. Делим все последовательности на две примерно равные части и лучшую систему в одной части объединяем с лучшей системой в другой части. Пусть 1 ( ) – лучшая система в одной части как функция от (и фиксирована последовательность *), а 2 ( ) – аналогичная система в другой части как функция от. Индуктивный шаг: от 1 () и 2 () переходим к () по правилу: лучшая система 1 ( )+ 2 ( ), полученная пере- бором всех и в *последователь- ностях Lead. reg. n Lead. reg. 1

Пример. Даны n=14 последовательностей, каждая с длиной m=201; ищем систему сайтов с длиной 15

Работа алгоритма:

Результат работы алгоритма:

Качество потенциального сигнала растет в процессе счета: Quality Iteration

Последовательное изменение качества сигнала в ходе алгоритма: Quality Iteration

Параллельная реализация вычислительно трудоемких алгоритмов: поиск мультибоксового регуляторного сигнала в группе геномов «Однобоксовый» сигнал: - полный переборO(m n ) - наш алгоритмO(n 2 m 3 ) «Двухбоксовый» сигнал: - полный переборO(m n d n ) - наш алгоритмO(n 2 m 3 d 3 ) (n – число последовательностей, m – максимальная длина, d – интервал расстояний между боксами сигнала) Волновая вычислительная схема на двумерной ε-сети перестановок мощностью порядка n 2 (в полном пространстве n! перестановок): 1)отсутствует жёсткая привязка к числу процессоров кластера 2)линейный рост производительности от числа доступных процессоров в широком диапазоне (проверено на МВС-1000М МСЦ, до 512 CPU) Пример для n=45, m=201, 8 CPU

Wavelike computation scheme Using 2D queue of permutations (P,Q) instead of straight one Q 7,8 (77) ===== Q 5,8 (72) Q 4,8 (73) Q 2,8 (78) Q 0,8 (74) Q 7,7 (69) Q 6,7 (71) Q 5,7 (64) Q 4,7 (65) Q 2,7 (70) ===== Q 0,7 (67) n=45, m=201, l=15, 8 CPU s Q 7,6 (62) Q 6,6 (61) Q 5,6 (56) Q 4,6 (57) ===== Q 2,6 (63) Q 1,6 (60) Q 0,6 (58) Q 7,5 (55) Q 6,5 (53) Q 5,5 (48) Q 4,5 (49) Q 3,5 (51) Q 2,5 (54) Q 1,5 (52) Q 0,5 (50) Q 7,4 (46) Q 6,4 (45) Q 5,4 (40) Q 4,4 (41) Q 3,4 (43) Q 2,4 (47) Q 1,4 (44) Q 0,4 (42) Q 7,3 (37) Q 6,3 (36) Q 5,3 (32) Q 4,3 (33) Q 3,3 (35) Q 2,3 (39) Q 1,3 (38) Q 0,3 (34) Q 7,2 (29) Q 6,2 (30) Q 5,2 (24) Q 4,2 (25) Q 3,2 (28) Q 2,2 (31) Q 1,2 (27) Q 0,2 (26) Q 8,1 (76) Q 7,1 (23) Q 6,1 (20) Q 5,1 (16) Q 4,1 (17) Q 3,1 (21) Q 2,1 (22) Q 1,1 (19) Q 0,1 (18) Q 9,0 (75) Q 8,0 (66) Q 7,0 (15) Q 6,0 (9) Q 5,0 (10) Q 4,0 (8) Q 3,0 (13) Q 2,0 (14) Q 1,0 (12) Q 0,0 (11) P 9 (68) P 8 (59) P 7 (7) P 6 (6) P 5 (5) P 4 (4) P 3 (3) P 2 (2) P 1 (1) P 0 (0) P 10 (79) …

Параллельная реализация вычислительно трудоемких алгоритмов: реконструкция эволюции регуляторного сигнала в группе геномов Усовершенствованная параллельная схема аннилинга MC 3 (= Metropolis-Coupled Markov Chain Monte-Carlo): 1)лучшее покрытие множества минимальных конфигураций 2)меньшая зависимость от выбранной начальной точки 3)более быстрая сходимость к одному из предполагаемых абсолютных минимумов функционала «энергии» Индивидуальные режимы охлаждения Периодический обмен параметрами охлаждения между находящимися в окрестности различных локальных или условных минимумов цепями с разной температурой способствует выходу из оврагов и локальных минимумов поверхности отклика. σ 1 (0) σ 1 (1) σ1(n1)σ1(n1) … … σ 2 (0) σ 2 (1) σ2(n2)σ2(n2) … … σ k (0) σ k (1) σk(nk)σk(nk) … … σ s (0) σ s (1) σs(ns)σs(ns) … … ……… σ k (n k +1)σ s (n s +1) βkβk βsβs

Показана лидерная область перед геном, в ней «окно» с концами x и y, а в окне образуются «спирали» ген левое плечо правое плечо xy

«Спираль» с «плечами», склеиваются G с C и A с T :

Реальные еще очень простые вторичные структуры (=наборы спиралей):

T A лидерная область Два состояния сигнала. Результат определяется тем, какая из двух альтернативных вторичных структур образуется: «Т» или «А»

Результат одной нашей моделей регуляции:

Примеры результатов счета в этой модели Мы считали функцию p=p(c) для практически всех лидерных областей аминокислотных оперонов и аминоацил-тРНК синтетаз. Имеется высокое согласие с экспериментом, с одной стороны, и предсказание многих новых случаев такой регуляции, с другой стороны. Здесь показаны thrA опероны у гамма-протеобактерий.

Два основных направления нашей работы в Биоинформатике: 1)Модели и алгоритмы регуляции генов, 2)Модели и алгоритмы эволюции этих регуляций (=сигналов)

Дано дерево G, у которого длины ребер соответ- ствуют времени переходу от предка к потомку. Даны современные последовательности Ищем все предковые последовательности 1234 = m..ACTG..

Иногда ищется и само дерево : тогда даны только современные последователь- ности. Эти заданные последовательности – организмы, виды, гены, белки, сигналы

Классическая аттенюаторная регуляция биосинтеза треонина у гамма-протеобактерий VC = Vibrio cholerae, VV = Vibrio vulnificus, VP = Vibrio parahaemolyticus, AB = Actinobacillus actinomycetemcomitans, HI = Haemophylus influenzae, PQ = Mannheimia haemolytica, VK = Pasterella multocida, YP = Yersinia pestis, EO = Erwinia carotovora, TY = Salmonella typhi, XCA = Xanthomonas campestris, EC = Escherichia coli, KP = Klebsiella pneumoniae, SON = Shewanella oneidensis ?конфигурация σ

Наша модель эволюции сигнала: Такая функция минимизируется с помощью алгоритма аннилинга. На каждом его шаге текущая конфигурация заменяется на новую из определенного списка возможностей с вероятностью или остается прежней с вероятностью. Нами доказана сходимость к глобальному min при условии

σjσj σ'jσ'j Показано одно ребро от некоторой конфигурации σ. На этом ребре за время t j происходят: замены букв со скоростями R, вставки букв и делеции букв. tjtj Сначала выравниваем позиции у σ j и σ' j, при этом возникают пустые позиции. Длины участков с пустыми позициями обозначим l jm. Тогда: Слагаемое H 1 (σ) в функции H j-е ребро

hjhj h'jh'j Показано одно ребро от конфигурации σ. На этом ребре произошел переход от вторичной структуры h j в σ j к вторичной структуре h ' j в σ' j. Тогда: Слагаемое H 2 (σ) в функции H j-е ребро σjσj σ'jσ'j

Решение (фрагмент): эволюция предкового сигнала

Поиск и эволюция сигнала другого типа («промотора»): некоторой комбинации слов с условиями на них и расстояния TTGaca н... TAtaaT стр. ген

На следующем слайде показан удивительно консервативный (=устойчивый при эволюции) прмотор (перед геном psbA в пластидах) На слайде через один показан противопо- ложный случай: быстро эволюционирующий (меняющийся) промотор среди цветковых растений (перед геном ndhF в пластидах). Он имеет четыре варианта A, B, C, D, сменяю- щие друг друга. Сами эти промоторы найде- ны, но здесь не приведены.

TTGACATGGCT=ATATAAGTCATGTTATACT Arabidop TTGACACGGG=CATATAAGGCATGTTATACT... ASpinacia TTCACGATA==TATATAAGTCATACTATACT Cycas TTGACATACA=GATATGTCTCATATTATACT Cryptomer TTGACATTGAT=ACATGGATCATATTATACT Pinus TTGACTTTAAT=AAACCATTTCTGTTATACT Welwitsch TTGACACGGAT=AGGTTTTT=GTGATATGCT Adiantum TTGACATCAAT=AGATAAGTTGTGTTATACT Angiopter TTGACATATAT=GGAAAGATCATGTTATACT Psilotum TTGACACAAA=AAGAAAGATTGTGTAATATT Huperzia TTGACATAC=TAATGGGATATGTGTAATAAT Aneura TTGACATAA=TCATATGTTATGTGTAATACT Marchantia TTGACATAA=TAATACATTTTGTGTAATACT Physcomitr TTGACATTT=TTATACTTTACATACTATAAT Chara TTGACATTAGTTATACGT=TTGTGCAATACT Chaetospha TTGACAGCT=TAAGGTTAAT=ATGTAATAAT Staurastr TTGACAACAG=CATTAACTATCTGTAATAAT Zygnema TTGACAAATA=AACATCATTT=TGGCATAAT Mesostig TTGATTAATATAA=ATTAATTA=GTTATAAT Bigelowiel

Magnoliophyta A eudicotyledons Amagnoliids A core Astem A Asterids AVitales A,CCaryoph Arosids BRanun AProteales A,C Campanul Alamiids Aeurosids1Myrtales B,Ceurosids2Geraniales B Cucurbitales B Malpighiales D Rosales B Fabales B Sapindales B,C Malvales B,C Brassicales C

Пример интересной темы для исследования – связь (РЕР) промоторов и предпочитаемых ими сигма- субъединиц. Например, нами показано, что промотор С предпочтительно связывает Sig4-субъединицу РНК- полимеразы. Аналогично для фаговых промоторов и полимераз.

Переходы, возможные в нашей модели регуляции, которая связана со спиралями: (1) Правый конец y окна сдвигается на один нуклеотид вправо или остается на месте или подается сигнал «Т». Альтернатива: когда правый конец y доходит до начала гена, то подается сигнал «А». При этом вторичная структура в окне формирует выбор между Т или А; (2) Левый конец x окна сдвигается на три нуклеотида вправо или остается на месте, что зависит от частоты c предшествующего считывания регулируемого гена; (3) Вторичная структура преобразуется в окне, т.e. текущая вторичная структура ω трансформируется в новую структуру ω'.

В модели с предыдущего слайда ищется (выход алгоритма) зависимость p(c) – частота наступления состояния «Т» (несчитывания гена), при каждом фиксированном значении частоты считывания («концентрации») c. При наличии такой регуляции график p(c) имеет вид, показанный на слайдах 24 и 25. При ее отсутствии график p(c) имеет вид почти постоянной функции или даже убывающей функции.

Что можно читать по этим темам: 1а) тип сигнала – «вторичная структура»: [Lyubetsky, Pirogov, Rubanov, Seliverstov, 2007, Journal of Bioinformatics and Computational Biology, vol 5, no 1, p ], 1b) тип сигнала – «промотор»: [Селиверстов, Лысенко, Любецкий, 2009, Физиология растений РАН, том 56, 5; Seliverstov, Lyubetsky Молекулярная биология, представлена] 2) Модели эволюции этих регуляций, т.е. эволюции сигналов 1а и 1b: [Любецкий, Жижина, Рубанов, 2008, Гиббсовский подход в задаче эволюции регуляторного сигнала экспрессии гена, ППИ, 4; Горбунов, Любецкий МолБио, представлена] Статьи можно получить от авторов по адресу:

Наши биологические результаты (дает некоторый обзор, для слушателей не обязателен) 1. Проведена реконструкция эволюционных событий молекулярного уровня: построены деревья белков и согласующие их деревья видов, найдены события потенциальных горизонтальных переносов, потерь и дупликаций генов, случаи массовой дупликации генов в предковом геноме, статистические характеристики эволюционных событий по вершинам дерева видов и по таксономическим группам, сравнивались сценарии горизонтальных переносов против дупликаций и потерь генов. [In the book: Bioinformatics of Genome Regulation and Structure II. Springer Science & Business Media, Inc. 2005]

2. Предложены новые типы регуляции экспрессии генов: 2.1 Регуляция на уровне трансляции, опосредован- ная Т-боксом, например, гена ileS, кодирующего изолейцил-тРНК синтетазу, у Актинобактерий. [BMC Microbiology, 2005, 5:54; Молекулярная биология, 2005, 39(6)] 2.2 Регуляция на уровне трансляции посредством взаимодействия рибосомы, транслирующей лидерный пептид, и вторичной структуры РНК для гена leuA, кодирующего 2-изопропилмалатсинтазу, у Актинобактерий («LEU-элемент»). [BMC Microbiology, 2005, 5:54; Молекулярная биология, 2005, 39(6)]

2.3 Сложные типы классической аттенюаторной регуляции (когда антитерминатор не альтернативен терминатору), например, у лактобацилл перед геном ilvD: это – цепь спиралей или псевдоузел. [готовится к печати] 2.4 Аттенюаторная регуляция генов cysK синтеза цистеина у Актинобактерий, вовлекающая ро-белок для терминации транскрипции: рибосома, транслирующая лидерный пептид, перекрывает сайт связывания ро- белка. [BMC Microbiology, 2005, 5:54] 2.5 Регуляция гена leuA у альфа-протеобактерий, вовлекающая ген лидерного пептида и консервативный псевдоузел («LEU1-регуляция»). [готовится к печати]

2.6 Регуляция, опосредованная аномально длинной спиралью РНК, генов, кодирующих транспортёры двухвалентных катионов (mntH) и ферменты, зависимые от металлов (никель-зависимая глиоксалаза и др.), у бруцелл. Выясняется роль этой регуляции в выживании бруцеллы при незавершённом фагоцитозе (бруцеллез). [Биофизика, в печати] 2.7 Статистические данные о расположении длинных спиралей в геномах Актинобактерий относительно кодирующих областей: длинные спирали концентрируются в некодирующих областях вблизи 3'-концов высоко экспрессируемых генов (включая тРНК) или между сходящимися навстречу друг другу генами. Выясняется роль таких шпилек в снятии конформационного напряжения ДНК и при терминации транскрипции путем образования крест- шпилек на ДНК. [МолБиол, 2007, 41(4)]

3. Найдены новые случаи известных типов регуляции у бактерий: 3.1 Предсказана белок-ДНКовая регуляция на уровне транскрипции и также промоторы генов синтеза пролина у протеобактерий родов Pseudomonas и Shewanella. [Молекулярная биология, 2007, 41(3)] 3.2 Предсказано много случаев белок-ДНКовой репрессии/активации. В частности, охарактеризован GlpR-регулон (регуляция метаболизма глицерол-3- фосфата). [Молекулярная биология, 2003, 37(5) – совместно с М.С. и его сотрудниками].

3.3 Проведен широкомасштабный поиск регуляции на уровне транскрипции посредством Т-боксов. [Молекулярная биология, 2005, 39(6)] 3.4 Предсказана классическая аттенюаторная регуляция: (a) у протеобактерий (включая дельта-протеобактерии) и у видов из таксономических групп бацилл/клостридий и бактероидов [FEMS 2004], (b) у Актинобактерий [BMC Microbiology, 2005, 5:54]

3.5 Предсказана регуляция на уровне трансляции посредством тиаминового рибопереключателя для гена ykoE, кодирующего субъединицу ABC транспортёра: происходит перекрывание сайта связывания рибосомы иногда прямо черенком рибопереключателя, а иногда дополнительной спиралью РНК – происходит быстрая смена этих механизмов регуляции у очень близких видов (показана эволюция этого механизма). [Информационные процессы, 2006, 6 (1)]

4. Белок-РНКовая регуляция в пластидах: 4.1 Корреляция сплайсинга с белок-РНКовой регуляцией трансляции в хлоропластах растений и водорослей. [Journal of Bioinformatics and Computational Biology, 2006, 4, 4, 783; Биофизика, 2006, 51, тематический выпуск 1] 4.2 Связь вторичной структуры РНК с редактированием инициирующего кодона в хлоропластах у мхов и папоротников. [Биофизика, 2006, 51, тематический выпуск 1] 4.3 Найдена высоко консервативная регуляция экспрессии генов psaA, psbA и psbB (вне связи со сплайсингом) [Journal of Bioinformatics and Computational Biology, 2006, 4(4)].

4.4 Найдена ортологичная консервативная регуляция гена ycf24 на уровне трансляции в пластидах красных водорослей и паразитов из таксона Apicomplexa (Eimeria tenella, Plasmodium spp., Toxoplasma gondii). Более того, у T. gondii эта регуляция охватывает и много других генов, включая те, которые кодируют РНК-полимеразу: этот ген кодирует белок SufB, необходимый для формирования железосероцентров. Выясняется роль пластид в жизни токсоплазм на молекулярном уровне. [Мол. биология, в печати]

5. Промоторы бактериального типа в пластидах и соответствующие им сигма-факторы у растений и водорослей: 5.1 Изучена быстрая эволюция промоторов перед геном ndhF, чья транскрипция у Резушки Таля (Arabidopsis thaliana) существенно зависит от сигма-субъединицы Sig4. [Физиология растений, в печати]. 5.2 Предсказано, что кодируемая в ядре сигма-субъединица Sig4 РНК-полимеразы бактериального типа существовала уже у предка высших двудольных растений и у него же имелся Sig4-зависимый промотор: соответствующие кДНК sig4 найдены по базе EST у винограда Vitis vinifera и двух видов апельсина Citrus clementina и C. sinensis (у апельсинов это псевдоген). Также известен псевдоген sig4 у тополя Populus trichocarpa. А Sig4-зависимые промоторы предсказаны в хлоропластах у всех видов из таксона Eurosids II (включая крестоцветные, апельсин и хлопок), а также у нескольких далёких представителей двудольных: эвкалипта, винограда и платана.

5.3 Исследованы Sig3-зависимые промоторы перед геном psbN у семенных растений и показано общее! для всех однодольных растений значительное отличие области этого промотора от прочих цветковых растений.

5.4 Найдены высоко консервативные хлоропластные промоторы бактериального типа перед генами rbcL, psaA, psbA, psbB, psbE у большинства видов из Streptophyta. Более того, промотор перед геном psbA, кодирующим белок D1 второй фотосистемы, одинаков у Streptophyta, включая рано отделившиеся роды Mesostigma и Chlorocybus, и у вторичного симбионта Bigelowiella natans из таксона Cercozoa.

5.5 Найдены промоторы перед геном rps20 и близлежащие сайты связывания транскрипционного фактора (– ортолога NtcA) в хлоропластах красных и криптофитовых водорослей. При этом сайт для NtcA найден тогда и только тогда, когда дивиргентно располагается ген glnB. У цианобактерий оба белка NtcA и GlnB вовлечены в регуляцию генов метаболизма азота и их взаимная регуляция показана (в частности, NtcA активирует транскрипцию glnB). На этом основании предсказана регуляция в хлоропластах по механизму конкуренции РНК- полимераз, транскрибирующих гены на противоположных цепях ДНК, причем также происходит активация транскрипции glnB.

6. Найдена общая белок-ДНКовая регуляция экспрессии ядерных генов, кодирующих рубредоксин и киназу, фосфорилирующую белки по тирозину, у диатомовой водоросли Thalassiosira pseudonana и у паразитов родов Theileria и Babesia

Эти виды являются вторичными симбионтами и имеют пластиды с общим происхождением от красных водорослей. Однако их ядерные геномы сильно отличаются. Поэтому можно предполагать связь этой регуляции с пластидами. Интересно, что киназы обычно участвуют в регуляторных каскадах, передающих сигнал от некоторой мембраны, в частности, от пластиды. Пластиды у диатомовых водорослей и паразитов Apicomplexa похожи, а ядерные геномы значительно различаются. С другой стороны, у криптофитовых водорослей рубредоксин кодируется в нуклеоморфе, т.е. непосредственно связан с пластидами. Поэтому можно предположить, что эти очень близкие регуляторные механизмы связаны с появлением пластид.