Усовершенствованы разработанные нами
алгоритмы массового поиска:
- аттенюаторной регуляции в одной исходной лидерной области гена;
- консервативных вторичных структур в наборе последовательностей РНК, основанный на выравнивании последовательностей из плеч и консервативных блоков спиралей;
- генов, которые попадают в геномы организмов в результате процессов горизонтального переноса, а также отбора других эволюционно "возникающих" генов;
- для построения дерева происхождения видов.
На основе усовершенствованных алгоритмов совместно с фирмой Integrated genomics продолжены работы в области сравнительной геномики и получены следующие результаты.
Найдены потенциальные сигналы аттенюаторной регуляции, ответственные за биосинтез разветвленных аминокислот, гистидина, треонина, триптофана и фенилаланина у гамма-, альфа- и бета-протеобактерий, у Грам-положительных бактерий из группы Bacillus/Clostridium и групп Thermotogales, Bacteroidetes/Chlorobi.
Описана эволюционная динамика аттенюаторной регуляции транскриции. Показано: у Pasteurellales ген аспартат киназы/гомосерин дегидрогеназы регулируется не только треонином и изолейцином (как у
E. coli), но также метионином; у альфа-протеобактерий оперон
ilvIH регулируется аттенюаторами; гистидиновый оперон his регулируется гистидин-зависимыми аттенюаторами у
Bacillus cereus и
Clostridium difficile и гистидиновым Т-боксом у
Lactococcus lactis и
Streptococcus mutans.
На основе этого предсказаны функции ряда ранее не исследованных семейств генов, в частности, рацемазы разветвленных аминокислот для
ygeA E. coli, гистидиновых транспортёров
yuiF и
yvsH у B. subtilis и
lysQ у L. Lactis.
Исследована эволюция нового класса регуляторных элементов, РНК-переключателей, и показано, что в различных таксономических группах бактерий используются различные механизмы регуляции (аттенюация транскрипции, прямое или непрямое ингибирование инициации трансляции). Впервые обнаружен РНК-переключатель, имеющий функцию активатора (в пути катаболизма лизина).
Продолжено исследование альтернативного сплайсинга. Показано, что как минимум 50% альтернативно сплайсируемых генов человека (т.е. минимум 25% всех генов) имеют специфичные изоформы, не представленные в геноме мыши. Показано, что альтернативный сплайсинг часто приводит к тасованию доменов в белках, а участки альтернативного сплайсинга малой протяженности коррелируют с функциональными участками белков. Отсюда сделано предположение, что альтернативный сплайсинг является одним из основных механизмов порождения эволюционного разнообразия белков.
В части анализа отдельных сложно взаимодействующих систем в клетке проведена полная реконструкция метаболических путей биосинтеза кобаламина, лизина, ароматических аминокислот (в Грам-положительных бактериях), утилизации цинка. Идентифицированы несколько десятков новых ферментов и транспортёров, в частности, метаболический путь ацетилированных предшественников лизина, несколько ферментов в кобаламиновом пути, транспортёры триптофана, лизина, кобаламина и его предшественников, кобальта, цинка. Показана регуляция цинком некоторых паралогов рибосомных белков. Идентифицированы цинк-зависимые факторы патогенеза стрептококков.
Разработан алгоритм для моделирования биосинтеза веществ в бактериальной культуре, в котором основную роль играют две системы регуляции: аттенюаторная и репрессорная. Алгоритм основан на рассмотрении динамики изменения процентного распределения по различным состояниям фрагментов ДНК, участвующих в синтезе. Простота модели позволила избежать сложного и, главное, косвенного описания процесса в терминах дифференциальных уравнений. Алгоритм применён для численного моделирования процесса синтеза триптофана. Полученные результаты показали, что репрессорная система регуляции действует быстрее, чем аттенюаторная, и реагирует на недостаток или избыток триптофана, что соответствует экспериментальным данным.
Используя сравнительный анализ генов и регуляторных областей, найдены консервативные структуры РНК, для которых регуляторный В12-элемент распространен в различных филогенетических группах бактерий перед генами биосинтеза и транспорта кобаламина; и выявлены их консервативные части. Анализ этого возможного регуляторного сигнала показал, что в протеобактериях, также как и в цианобактериях, актинобактериях, CFB группе, регуляция осуществляется преимущественно на уровне трансляции, в то время как в Грам-положительных и некоторых других бактериях - на уровне транскрипции.
Поиск В12-элементов и позиционный анализ позволил идентифицировать большое количество новых генов, потенциально регулируемых В12-элементом. Среди новых генов, ассоциированных с биосинтезом кобаламина, найдены новые типы траспортеров кобальта, кобальтовые редуктазы BluB и т.д. Наиболее интересный результат получен в случае метионин-синтазы и рибонуклеотид-редуктазы, которые регулируются в бактериях, имеющих оба типа В12-зависимого и В12-независимого фермента.
Филогенетических анализ регуляторных В12-элементов выявил большое количество дупликаций, которые, возможно, играют ключевую роль в эволюции кобаламинового регулона.
Сравнительный анализ и другие алгоритмы были применены к анализу регуляторных элементов, генов и оперонов пути биосинтеза лизина во всех доступных бактериях. Идентифицирован регуляторный РНК-элемент, названный ЛИЗ, в регуляторных областях генов, вовлеченных в биосинтез и транспорт лизина. Здесь, как и в случае регуляторных элементов, вовлеченных в регуляцию рибофлавина, тиамина и кобаламина, эта регуляторная РНК-структура является сильно консервативной как на уровне первичной последовательности, так и на уровне вторичной структуры, а возможный механизм регуляции похож на механизм регуляции, найденный для других РНКовых переключателей (
RFN-,
THI-, В12-элементы, S-боксы и пуриновые боксы) и включает в себя аттенюацию как транскрипции, так и трансляции. Нахождение ЛИЗ-элементов в гамма-проте-обактериях и Грам-положительных бактериях (группа бациллы-клостридии) и Thermotogales позволило описать новый лизиновый регулон в этих бактериях. Позиционный анализ регуляторных ЛИЗ-элементов позволил идентифицировать новые возможные транспортеры лизина, а именно LysW, YvsH и LysXY.
Методы сравнительной геномики были применены для анализа регуляции экспрессии генов биосинтеза ароматических аминокислот в Грам-положительных бактериях (группа бациллы-клостридии). Новые Т-боксы были найдены в регуляторных областях генов биосинтеза и транспорта ароматических аминокислот, также как и возможные сайты для нового регулятора транскрипции в Streptococcus and Lactococcus.
При анализе специфичности регуляторных сигналов были найдены новые возможные транспортеры для триптофана.
Сравнение всех доступных геномов показало, что регуляция генов биосинтеза ароматических аминокислот сильно изменчива - в группе бацил-клостридий присутствует, по крайней мере, четыре регуляторных системы для регуляции экспрессии генов биосинтеза и транспорта ароматических аминокислот: две на уровне ДНК и две на уровне РНК, включающие в себя образование альтернативных РНК структур.
Продолжено исследование проблемы построения оптимальных стратегий, т.е. стратегий, образующих точку равновесия по Нэшу, для игр в стохастических динамических системах с дискретным временем. Особое внимание уделено влиянию информации, которой обладают игроки, или влиянию внешних (например, экономических) условий на результат игры. Так, рассмотрены случаи, когда игроки обладают неполной, а возможно и асимметричной информацией о системе. Показано, что как дополнительная информация, так и более благоприятные внешние условия могут негативно сказываться на результатах игры. Разработанные методы реализованы в виде компьютерных алгоритмов. В вычислительных экспериментах исследованы вопросы существования и единственности пары равновесных по Нэшу стратегий.
Продолжено исследование общих свойств категорий преобразователей информации (ПИ) как моноидальных категорий специального вида. Особое вни-мание уделено рассмотрению категорий ПИ, которые могут быть построены как моноидальные категории Клейсли. При построении таких категорий ПИ ключевую роль играет функтор T, переводящий объект A в объект TA "распределений на A", и естественное преобразование, переводящее пару "распределений" в "независимое совместное распределение". Получено необходимое и достаточное условие, при котором построенная категория Клейсли удовлетворяет аксиомам категории ПИ.
Предложена формализация игры с неполной информацией в терминах категорий преобразователей информации. Понятия информативности и семантической информативности продолжены с класса преобразователей информации на классы игр. Показано, что в теоретико-игровом контексте соотношение между информативностью и семантической информативностью имеет гораздо более сложный характер, чем просто в контексте преобразователей информации в задачах принятия решений. В частности, использование более информативных ПИ в игре может приводить к снижению выигрышей игроков, т.е. к более низкой семантической информативности.
Изучался вопрос о полноте расширений базисной и формальной логик Виссера относительно семантики Крипке. Показано, что при естественном определении понятия расширения (например, наложение требования замкнутости по правилу modus ponens) все расширения формальной (но не базисной) логики Виссера оказываются бесконечно-слойными, причем существуют неполные по Крипке логики конечной ширины, среди которых континуум таких логик ширины 2, аксиоматизируемых формулами с одной переменной. Это контрастирует с хорошо известной ситуацией в нормальных модальных логиках и в суперинтуиционистских логиках.
Доказано, что проблема финитарного семантического следования (т.е. верно ли, что формула ψ истинна во всех конечных семантических конструкциях из класса C, в которых истинна формула φ) разрешима для класса модальных шкал с функциональным (детерминированным) отношением достижимости.
Доказано, что проблема финитарного семантического следования неразрешима для класса шкал Крипке формальной логики Виссера и класса обобщенных шкал этой логики, причем эти отношения различны.
Для каждого натурального числа
n доказана неразрешимость класса формул первого порядка, которые модально определимы модальными формулами с
n переменными, но не определимы модальными формулами с меньшим числом переменных.
Доказана возможность модификации семантики Крипке для предикатных вариантов базисной и формальной логик введением в шкалы так называемых "взрывающихся" миров (т.е. миров, в которых истинны все формулы, включая константу "ложь").
В области дескриптивной теории множеств получена теорема о совершенных подмножествах инвариантных
СА-множеств, обобщающая результаты известные ранее для более узкого класса множеств. Доказаны результаты для гиперконечных и гипергладких отношений эквивалентности в модели Соловея. Получено положительное решение давно стоявшей проблемы о существовании определимых нестадартных моделей.
Получены результаты о неустойчивости универсальных методов сжатия информации при небольших нарушениях эргодичности источника.
Изучены экстремальные соотношения между колмогоровской сложностью и аддитивными функциями потерь. Введено и изучено понятие алгоритмической случайности относительно разбиения множества объектов.
Доказано, что любое конечное множество A пар можно разбить на полином от логарифма ¦A¦ частей так, что в каждой части все горизонтальные сечения отличаются друг от друга не более, чем в полином от логарифма ¦A¦ раз, и это же верно для вертикальных сечений (тоже для любой размерности). Это утверждение используется при комбинаторной интерпретации неравенств для шенноновской энтропии.
Продолжались исследования в области, связанной со сведением произвольного теста на случайность к частотному тесту. Доказано, что для всех достаточно больших
L и для каждого множества
S последовательностей из нулей и единиц длины
L с ненулевым удельным дефектом δ существует множество
R из
poly(1/δ) монотонных правил выбора такое, что для любого элемента множества
S существует правило из
R, выбирающее из него подпоследовательность длины не менее
cLδ (
c - константа) c отклонением доли единиц от 1/2 не менее квадратного корня из cδ. Удельный дефект этих правил не меньше cδ
4/3.
Сотрудники сектора в качестве приглашенных докладчиков участвовали в следующих конференциях:
- 1st Int. Con. "Functional Genomics and Disease", Prague, May 2003.
- Int. Moscow Conference on Computational Molecular Biology MCCMB'03, Moscow, Russia, July 22-25, 2003.
- 4th Int. Georgia Tech. Conf. on Bioinformatics, Atlanta, USA, November 2003
- Международная конференция "Колмогоров и современная математика", Москва, 16-21 июня 2003 г.
- Logic Colloquium 2003, Helsinki, Finland, August 14-20.
- Четвёртая Международная конференция "Смирновские чтения", 28-30 мая 2003 г.
- Dagstuhl centennial Seminar on Kolmogorov Complexity and Applications (at the occasion of the 100th anniversary of Andrei N. Kolmogorov's birthday), Dagstuhl, 28 июня - 2 мая 2003 г.
- Международная конференция "Algorithmic Learning Theory", Саппоро, Япония, 2003.
- 11th Annual IEEE Conference on Computational Complexity, Орхус, Дания, 7-10 июля 2003 г.
- Пятая международная конференция "Проблемы управления и моделирования в сложных системах", Самара, 17-22 июня 2003 г.
Сотрудники сектора командировались для чтения лекций и совместной научной работы в ряд университетов и научных центров, таких как: Technische Universitaet Muenchen (Германия), Ludwig Institute of Cancer Research (Нью Йорк, США), AstraZeneca (Нью Йорк, США), Burnham Institute (Сан Диего, США), University of California (Сан Диего, США), Harvard Med. School (Бостон, США), Boston University (США), International Centre for Genetic Engineering and Biotechnology (Триест, Италия), Institut National De Recherche en Informatique et En Automatique (Франция), Institut de recherche en informatique de Toulouse (Франция), Университет г. Вупперталь (Германия), CWI (Амстердам, Нидерланды), Унивеситет Прованса (Марсель, Франция), Университет Париж-7 (Франция).