Предложен алгоритм для задачи построения дерева КОГа на основе множественного выравнивания белковых последовательностей, связанный с пошаговым удалении столбцов с высокой энтропией из исходного выравнивания. Этот алгоритмический подход реализован компьютерной программой.
Разработана модель эволюции видов на основе объединения двух подходов: вложения дерева белков в дерево видов и выбора наиболее экономного эволюционного сценария. На ее основе разработана компьютерная программа, с помощью которой выполнен отбор генов (белков), нарушающих согласованность белковых деревьев, и получены оптимальные сценарии эволюционного развития семейства микроорганизмов.
На основе разработанной нами ранее программы проведено систематическое оценивание качества КОГов (Кластеров Ортологических Групп генов) и их филогенетических деревьев.
Разработана компьютерная программа, которая по дереву генов (или по набору ортологичных аминокислотных последовательностей - в этом случае используется аппарат нечётких множеств) и дереву видов ищет события горизонтального переноса гена. С ее помощью проведён массовый поиск таких событий по всему спектру бактериальных групп, выявлено более 100 пар, 10 из которых соответствуют предковым горизонтальным переносам.
Создан алгоритм и компьютерная программа, с помощью которой проведён анализ множественных повторов в бактериальных геномах. Эта программа может использоваться для анализа повторяющихся последовательностей в одном или сразу во многих геномах. Она тестировалась на геноме Neisseria meningitides; например, один из найденных кластеров содержит несколько сотен ρ-независимых терминаторов. Другие кластеры соответствуют мобильным IS-элементам (IS30, IS1016C2, IS1106). Кроме известных повторов найдено несколько кластеров, функции которых неизвестны: например, повтор длиной в 26 нуклеотидов, который высоко консервативен и распространен в нескольких сотнях копий в геноме. Эта повторяющаяся последовательность имеет сложную палиндромную структуру, а копии расположены только в межгенных участках и часто вблизи генов патогенеза бактерии. Похожий феномен наблюдался и в других бактериях.
Проведён компьютерный анализ кривизны ДНК регуляторных участков rrn оперонов в бактериях. Для этого использовались два подхода: предсказание сайтов связывания белков и анализ кривизны ДНК для изучения регуляции rrn оперонов белками FIS/H-NS, конкурирующими за сайты связывания, в протеобактериях. Значимые участки кривизны ДНК найдены в регуляторных областях rrn оперонов вокруг -100 и -120 позиций от старта транскрипции, главным образом, в трех филогенетических группах: Enterobacteriales, Vibrionales and Pasteurellales. Сгруппированные сайты связывания белка FIS также были предсказаны только в этих трех филогенетических группах. В других протеобактериях найдены только несколько значимых сайтов кривизны в регуляторных областях rrn оперонов, а сгруппированные FIS сайты не были обнаружены. Возможно, регуляция rrn оперонов конкурирующими белками H-NS/FIS консервативна только в этих трех гамма-протеобактериальных группах.
Проведён сравнительный анализ метионовых регулонов в Грам-положи-тельных бактериях. В одних случаях найдены регуляторные системы РНК (S-боксовый РНК-овый переключатель и T-боксовый механизм антитерминации), в других - системы регуляции экспрессии на уровне ДНК. Идентифицировано большое количество метионин-специфичных регуляторных сигналов и описан метиониновый регулон в доступных геномах Грам-положительных бактерий. Показано, что S-боксы широко распространены в бациллах и клостридиях, а метионин-специфичные Т-боксы - в Лактобациллах. Позиционный анализ метионин-специфичных сайтов позволил идентифицировать несколько новых членов метионинового регулона (энзимов и транспортеров).
Найдены предполагаемые регуляторные элементы перед генами метаболизма триптофана, цистеина и разветвлённых аминокислот у Актинобактерий. Перед оперонами биосинтеза гистидина, треонина, фенилаланина, тирозина, аргинина и лизина в этой таксономической группе консервативная вторичная структура РНК не обнаружена, хотя ортологичные гены регулируются на уровне РНК в других таксонах: метионин с помощью S-боксов (РНК переключателей) лизин с помощью L-боксов (РНК переключателей), гистидин, треонин и фенилаланин аттенюацией, тирозин и аргинин T-боксами.
Найдена классическая аттенюация перед генами аминоацил-тРНК-синтетаз trpS и leuS в геномах некоторых Streptomyces, что отличает их от типичного случая, в котором гены аминоацил-тРНК-синтетаз регулируются T-боксами. Аналогичная ситуация наблюдается у гамма-протеобактерий, где такие гены (pheST оперон) регулируются аттенюацией.
Одно из наших предсказаний состоит в том, что аттенюация cys оперонов в Mycobacterium spp. и P. acnes, и cbs оперона в B. longum вовлекает Rho-зависимую терминацию по аналогии с tna опероном в E. coli.
Наиболее интересным представляется случай leuA генов у Актинобактерий. Участки перед этими генами содержат несколько консервативных элементов (с общим названием LEU-элемент), допускающими несколько толкований. По структуре они напоминают РНК переключатели: компактная структура с черенком в основании. Черенок образован последовательностью лейциновых кодонов и областью Шайна-Дальгарно. Таким образом, Актинобактерии образуют таксономическую группу, у которой черенок РНК переключателя непосредственно перекрывает место инициации трансляции без вспомогательных регуляторных шпилек. Однако, в отличие от всех известных РНК переключателей, выравнивание LEU-элементов не содержит большого числа консервативных нуклеотидов, которые могли бы быть вовлечены в формирование третичной структуры, связывающей лиганд, как это имеет место в пуриновом РНК переключателе, для которого пространственная структура найдена. Таким образом, прямое связывание маленькой молекулы лейцина с LEU-элементами не кажется правдоподобным.
Еще загадка состоит в существовании последовательности, гомологичной LEU-элементу внутри гена транспосазы. Последнее может быть ключом к объяснению возникновения LEU-элементов. Возможно, транспосаза из B. longum представляет собой предковое состояние, в котором LEU-элемент вовлечён в стабилизацию или регуляцию транспозиции. Ситуации, когда регуляторные элементы включены в состав генов, не распространены, но могут иметь место. Возможно, что другие транспосазы в результате мутаций утратили возможность образовывать такие структуры. Отметим, что аминокислотные последовательности не претерпели значительных изменений, так как большинство замен были синонимичными. В некоторый момент ген транспосазы встроился перед геном leuA в геноме предка Актинобактерий. Большая часть кодирующей последовательности была удалена, а структурный элемент был вовлечен в регуляцию лежащего ниже гена leuA.
Развиты полученный нами ранее алгоритм и компьютерная программа LLLM для построения потенциальных структур классической аттенюаторной регуляции в геномах бактерий. С его помощью проведен массовый поиск и во многих случаях найдены потенциальные сигналы аттенюаторной регуляции (в иных случаях алгоритм указал на предположительную причину их отсутствия) у гамма-, альфа- и бета-протеобактерий (биосинтез разветвленных и ароматических аминокислот, гистидина и треонина, фенилаланил-тРНК-синтетазы), а также и у грамположительных бактерий: из групп Bacillales, Lactobacillales, Clostridiales, Bacteroidetes/Chlorobi и Thermotogales (биосинтез гистидина); описана эволюционная динамика аттенюаторной регуляции транскрипции.
Установлены потенциальные оперонные структуры для генов биосинтеза некоторых аминокислот (триптофана, фенилаланина, треонина, гистидина и разветвленных аминокислот) в различных геномах.
Предсказано новое семейство гистидиновых транспортеров - ортологов yuiF у B. subtilis (например, HI0325 у H. Influenzae) и два гистидиновых транспортера BC0629 у B. cereus (ортолог yvsH у B. subtilis) из белкового семейства АРА и ген у L. lactis (ортолог lysQ у E. coli) из семейства АРС.
Получена предположительная функциональная аннотация ряда генов, кодирующих ферменты и находящихся под аттенюаторной регуляцией, а именно: гену ygeA у Pasteurella multocida приписана функция рацемазы разветвленных аминокислот; не ортологичные гены vatB, actХ2 и actХ3, соответственно, у Pasteurella multocida, Mannheimia haemolytica, Polaribacter filamentus кодируют ацетилтрансферазы, участвующие в метаболизме гистидина.
Показано, что биосинтез изолейцина у Xanthomonadales использует треонин дегидратазу TdcB, в отличие от IlvA у E. coli.
Показано, что у Pasteurellales бифункциональный ген thrA аспартат киназы/гомосерин дегидрогеназы регулируется не только треонинином и изолейцином (как это имеет место у E. coli), но и метионином.
Предсказано, что у альфа-протеобактерий ацетолактат синтаза IlvIH регулируется аттенюацией с регуляторными кодонами лейцина, изолейцина и валина.
Предсказано, что оперон his биосинтеза гистидина регулируется гистидин-зависимыми аттенюаторами у Bacillus cereus и Clostridium difficile, но и в тоже время регулируется гистидиновыми Т-боксами у Lactococcus lactis и Streptococcus mutans.
Хорошее выравнивание перечисленных биологических предсказаний рассматривается как подтверждение адекватности программы LLLM.
На основе разработанной нами ранее модели регуляции биосинтеза триптофана построены графики временной зависимости концентраций триптофана, соответствующих ферментов и белка-репрессора между собой.
Продолжено исследование проблемы построения оптимальных стратегий, т.е. стратегий, образующих точку равновесия по Нэшу, для игр в стохастических динамических системах с дискретным временем. Исследованы возможности трансформации правил, с целью построения таких правил игры, которые приводят к менее деструктивным и более устойчивым (по отношению к влиянию внешних возмущений) стратегиям игроков. Исследована возможность кооперации игроков в случае неполной информации. Построен алгоритм, реализующий Nash Bargaining Solution для динамических игр с неполной информацией. Разработанные методы реализованы в виде алгоритмов и соответствующих компьютерных программ.
Продолжено исследование общих свойств категорий преобразователей информации (ПИ). Показано, что многие категории ПИ могут быть построены как моноидальные категории Клейсли. При этом ключевую роль играет функтор T, переводящий объект A в объект TA "распределений на A" и естественное преобразование ψ "переводящее" пару "распределений" в "независимое совместное распределение". Получены явно описанные примеры таких категорий, функторов и естественных преобразований.
Предложена формализация игры с неполной информацией в терминах категорий ПИ. Понятия информативности и семантической информативности продолжены с класса ПИ на классы игр. Показано, что в теоретико-игровом контексте соотношение между информативностью и семантической информативностью имеет более сложный характер, чем в контексте одних ПИ (в задачах принятия решений). В частности, использование в игре более информативных ПИ может приводить к снижению выигрышей игроков, т.е. к более низкой семантической информативности.
Продолжены исследования в области нестандартного анализа и теории множеств. В первой из них доказана теорема о том, что теоретико-множественный универсум ZFC допускает элементарное расширение до полностью насыщенного универсума нестандартной теории множеств BST. Ранее подобные результаты были получены только на основе теории ZFC с глобальной аксиомой выбора, которая использовалась для построения некоторого собственного класса ультрафильтров. В нашей конструкции используется линейная упорядоченность класса всех ультрафильтров, и глобальная аксиома выбора не нужна.
В области "гиперконечной" дескриптивной теории множеств доказано: любое счетно детерминированное подмножество в *N×*N, каждое вертикальное сечение которого является борелевским множеством некоторого аддитивного класса, является счетным объединением счетно детерминированных множеств с вертикальными сечениями классов ниже, чем упомянутый.
Исследованы вопросы, связанные с борелевской сводимостью отношений эквивалентности над вещественными числами. Построена явно определенная трансфинитно возрастающая и конфинальная последовательность борелевских отношений эквивалентности; ранее такой результат был получен только в форме чистой теоремы существования.
Доказано, что континуум-гипотеза не изменится, если конечное множество определить по Дедекинду.
Найдены верхние границы для числа переменных в доказательстве неразрешимости финитарного семантического следования для базисной и формальной логик Виссера относительно семантики Крипке и неразрешимость финитарного следования для базисной и формальной логик Виссера относительно обобщённой реляционной семантики. Семантически логики Виссера определяются подобно интуиционистской пропозициональной логике, но конечными транзитивными шкалами для базисной логики и конечными транзитивными иррефлексивными шкалами для формальной логики. Финитарное семантическое следование для данного класса шкал определяется так: из φ финитарно следует ψ, если формула ψ истинна во всех конечных шкалах из этого класса, в которых истинна φ.
Для каждого натурального n доказана неразрешимость класса формул первого порядка, которые определимы пропозициональными формулами с n переменными в семантике базисной логики Виссера, но не определимы такими формулами с меньшим числом переменных.
Получено новое доказательство разрешимости за полиномиальное время задачи о существовании n-клики в n-дольном графе с двумя в каждой доле вершинами. Алгоритм сводит эту задачу к линейному программированию. Алгоритм вычисляет верхнюю оценку на число таких клик в графе. Доказано, что выпуклая оболочка всех точек, соответствующих n-кликам в полном таком графе, является многогранником, у которого каждые две вершины соединены ребром.
Улучшены оценки в задаче сведения произвольного теста на случайность к частотному тесту. Пусть дано множество S из 0/1-последовательностей длины L, и монотонным правилом выбора назовём правило выбора подпоследовательности из произвольного элемента t множества S, которое на каждом i-ом шаге решает (зная лишь S и начало последовательности t длины i-1, но не зная всей t), добавлять ли i-ю букву слова t в конец строящейся подпоследовательности. Удельным дефектом правила относительно S называется результат деления на L минимума (по всем t из S) произведения длины выбранной подпоследовательности на квадрат отклонения доли нулей в ней от ½. Доказано: для всех достаточно малых d, достаточно больших L и каждого множества S с ненулевым удельным дефектом d существует множество R из poly(1/d) монотонных правил выбора, d₁-покрывающее S, где d₁= [d/ln(1/d)][1-2lnln(1/d)/ln(1/d)]. (Здесь удельным дефектом множества S называется (log₂|S|)/L; семейство R правил d₁-покрывает S, если существует разбиение множества S на |R| подмножеств и такое взаимнооднозначное соответствие между правилами и подмножествами, что удельный дефект каждого правила относительно соответствующего ему подмножества больше d₁.)
Доказано: для всех достаточно малых d множество всех (не обязательно монотонных) правил выбора, задающихся программами с условной относительно L колмогоровской сложностью меньше a=poly(ln(1/d))/d, d₁-покрывает (при d₁= [d/ln(1/d)][1-O(lnln(1/d)/ln(1/d))]) множество M(L,d) всех таких двоичных последовательностей t длины L, что условная колмогоровская сложность K(t|L) не превышает L(1-d), при этом нижняя граница на L эффективно вычисляется по нижней границе на d.

Сотрудники лаборатории в качестве приглашенных докладчиков участвовали в следующих конференциях и школах:

• Logic, Algebra and Geometry. St. Petersburg, June 1-7, 2004.
• Models of Arithmetic and Analysis. International Congress, Pisa, June 25-26, 2004.
• Logic Colloquium 2004, ASL European Summer Meeting. Torino, 25-31 July 2004.
• Geometric topology, discrete geometry, and set theory. International conference, Moscow, August 24-28, 2004.
• Eighth Luminy Set Theory Workshop. September 20- 4th, 2004.
• Indexation de texte et découverte de motifs algorithmique des séquences. Lille (France), 9 et 10 décembre 2004.
• Journée sur la Bioinformatique, PRST intelligence logicielle. 25 November, 2004, LORIA, Nancy (France).
• Fourth International Conference on Bionnformatics of Genome Regulation and Structure, BGRS'2004. Novosibirsk, Russia, July 25-30, 2004.
• Шестая международная конференция "Проблемы управления и моделирования в сложных системах". Самара, 14-17 июня 2004.
• EMBO World Phylogenetic Course, 2004. November 1-7, 2004, Rio de Janeiro, Brazil.
• The Annual New Zealand Phylogenetics Meeting 2004. February 15-20, 2004, Mt Ruapehu, New Zealand.
• XIVth International Hutsulian Workshop on Mathematical Theories and their Applications in Physics & Technology, 2004.
• Conference on Fisheries Economics and Management in Honour of Professor Gordon R Munro. Univ. of British Columbia, 2004, August 5-6.
• The SPACC Workshop, University of Portsmouth, UK, 2004, 13-15 September.

Сотрудники лаборатории командировались для чтения лекций и совместной научной работы в ряд университетов и научных центров: Университет Вупперталя, Германия; Институт Макса Планка, Бонн, Германия; Institut National De Recherche en Informatique et En Automatique; Университет Монтаны, США, Миссула, Монтана; National center of atmospheric research, США, Болдер, Колорадо.
В 2004 году в лаборатории подготовлены 3 кандидатских диссертации, две из которых прошли защиту (Л. Данилова, Е. Любецкая). Сотрудники реулярно ведут педагогическую работу в МГУ им. Ломоносова и других университетах.