Lab.6 IITP RAS logo
22/07/17
08:46:19

Лаборатория математических методов и моделей в биоинформатике
Института проблем передачи информации им. А.А. Харкевича
Российской академии наук

« back

Научная деятельность лаборатории за период 2005-2007 гг.

За период 2005-2007 гг. исследования сотрудников Лаборатории 6 были поддержаны следующими программами и грантами:

  • грант РФФИ 04-04-48247-а «Участие фитогормонов в транскрипционной регуляции экспрессии хлоропластного генома»;
  • грант РФФИ 04-04-81003-Бел2004_а «Ядерно-пластидное взаимодействие как ведущий фактор биогенеза хлоропластов. Роль фитогормонов»;
  • грант РФФИ 06-04-81024-Бел_а «Молекулярно-мембранные механизмы ответной реакции растительной клетки при тепловом воздействии»;
  • грант РФФИ 06-08-01585-а «Получение и функциональный анализ трансгенных растений, накапливающих уран, для очистки загрязнённых территорий»;
  • грант РФФИ 07-04-01398-а «Взаимодействие сигнальных систем в регуляции транскрипции хлоропластного генома»;
  • грант РФФИ 03-01-00757-а «Основания нестандартной математики»;
  • грант РФФИ 06-01-00608-а «Проблемы нестандартного анализа и теории множеств»;
  • грант РФФИ 07-01-00445-а «Классификация финальных структур Хаусдорфа»;
  • грант РФФИ 06-01-00122 «Колмогоровская сложность и алгоритмическая теория вероятностей»;
  • грант Совета поддержки научных школ при Президенте РФ (номер проекта НШ-358.2003.1) (2003-2005 гг.).
  • федеральная целевая научно-техническая программа «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по государственному контракту № 37.053.11.061 «Модели и алгоритмы информационного взаимодействия в области генетики, лингвистики и цветного зрения»;
  • грант DFG 436 RUS 17/68/05 «Нестандартная теория классов» (2005 г.);
  • грант Howard Hughes Medical Institute (55005610) (2006-наст.вр.);
  • грант INTAS (05-8028) (2006-2007 гг.);
  • грант Российской Академии Наук (программа "Молекулярная и клеточная биология") (2004-2008 гг.);
  • грант Howard Hughes Medical Institute (55000309) (2003-2005 гг.);
  • грант Международного Научно-технического Центра (МНТЦ) Проект 2766 «Новые методы компьютерной аннотации бактериальных геномов: разработка и применение» (2004-2007 гг.);
  • грант Международного Научно-технического Центра (МНТЦ) Проект 3807 «Сравнительная геномика и метагеномика: модели, алгоритмы и массовый анализ; нанотехнологии для избирательного транспорта» (2008-2011г.);
  • Программа Национального научного фонда США, SES-0323129: «Поддержание международной морской кооперации в организации рыбной ловли с учетом изменений в окружающей среде» (2003-2006 гг.);
  • Научная программа «Развитие научного потенциала высшей школы» Подпрограмма I. Фундаментальные исследования Раздел 2. «Университеты России»: грант УР.07.02.572 НИР «Филогенетический мета-анализ: новый подход к изучению макроэволюции трехслойных животных» (Федеральное агентство по образованию);
  • грант РФФИ 05-04-49272-а «Форониды мировой фауны: организация, развитие, таксономическое разнообразие, биогеография, эволюция»;
  • грант РФФИ 05-04-49705-а «Новый подход к изучению филогении Bilateria – мультигенный филогенетический анализ минорных типов»;
  • грант РФФИ 06-04-48918-а «Эволюция, система и филогения вислоногих ракообразных отряда Siphonostomatoida»;
  • грант Федерального агентства по науке и инновациям «Роснаука»: Госконтракт № 02.442.11.7389 НИР «Филогеномика высших многоклеточных»;
  • грант Федерального агентства по науке и инновациям «Роснаука»: Госконтракт № 02.442.11.7207 «Поиск и разведка данных как основной инструмент филогеномики и его применение для реконструкции макрофилогении высших многоклеточных»;
  • грант Федерального агентства по науке и инновациям «Роснаука»: Госконтракт № 02.444.11.7223 «Применение мультифакторного бутстрэп-анализа для решения задач филогеномики многоклеточных животных»;
  • грант Федерального агентства по науке и инновациям «Роснаука»: Госконтракт № 02.444.11.7276 «Новый инструмент филогеномики – филогенетический мета-анализ, и его применение для построения эволюционного древа высших многоклеточных»;
  • целевой грант РФФИ 05-04-58955-з «Участие в Европейской конференции по вычислительной биологии ECCB 2005»;
  • грант РФФИ 08-04-01746-а «Молекулярные синапоморфии в филогеномике многоклеточных животных как критерий надежности реконструкции филогенетических отношений»;
  • целевой грант РФФИ 08-04-09233-моб_з «Участие в съезде общества молекулярной биологии и эволюции (Annual Meeting of the Society of Molecular Biology and Evolution, SMBE)»;
  • Соруководство с российской стороны совместных работ РАН-СНРС (Франция) (№19122) «Эволюция регуляторных сигналов и механизмы регуляции экспрессии генов у бактерий: моделирование и анализ методами автоматической верификации», 2006-07 годы;
  • Соруководство с российской стороны совместных работ РАН-СНРС (Франция) (№47659) «Регуляция экспрессии генов, эволюция регуляторных сигналов у бактерий: анализ вторичной структуры методами автоматической верификации», 2008-09 годы.

Научная деятельность лаборатории проводится в рамках следующих основных направлений научной работы ИППИ РАН:

  • Информационные процессы в живых системах и биоинформатика;
  • Математическая теория информации и управления, многокомпонентные случайные системы.

В рамках направления «Информационные процессы в живых системах и биоинформатика» в лаборатории проводятся исследования по трем темам:

  • модели эволюции белка, вида, регуляторного сигнала; поиск событий молекулярной эволюции, включая горизонтальные переносы генов;
  • модели аттенюаторной и других РНК-овых регуляций, поиск сайтов таких регуляций; поиск сайтов белок-ДНК/РНКовой регуляции транскрипции и трансляции;
  • регуляция транскрипции генов пластид растений и водорослей, идентификация генов сигма-субъединиц РНК-полимераз и их промоторов, модели эволюция промоторов и регуляторных элементов.

Эти исследования ведут к.б.н. А.Г. Витрещак, к.ф.-м.н. К.Ю. Горбунов, д.ф.-м.н. П.В. Голубцов, О.А. Зверков, д.ф.-м.н. В.Г. Кановей, К.В. Лопатовская, д.ф.-м.н. В.А. Любецкий, к.б.н. Е.А. Лысенко, к.б.н. Л.Ю. Русин, к.ф.-м.н. А.В. Селиверстов совместно с сотрудниками других лабораторий: к.ф.-м.н. Е.А. Асариным (лаб. 1), д.ф.-м.н. В.В. Вьюгиным (лаб. 1), д.б.н. М.С. Гельфандом (УНЦ), к.ф.-м.н. Е.В. Любецкой (сектор 2), д.ф.-м.н. Е.А. Жижиной (лаб. 4), к.ф.-м.н. С.А. Пироговым (лаб. 3) и к.т.н. Л.И. Рубановым (лаб. 2).

В рамках направления «Математическая теория информации и управления, многокомпонентные случайные системы» в лаборатории проводятся исследования по теме

  • проблемы эффективного описания объектов, процессов, алгоритмов на основе теорий модельной полноты, интуиционистской и дескриптивной теорий множеств, теории моделей, нестандартного анализа и стохастических игр.

Эти исследования ведут д.ф.-м.н. П.В. Голубцов, к.ф.-м.н. К.Ю. Горбунов, д.ф.-м.н. В.Г. Кановей, д.ф.-м.н. В.А. Любецкий, к.ф.-м.н. А.В. Селиверстов.

I. Обзор результатов, полученных в лаборатории в 2005-2007 годах, по направлению «Биоинформатика»

(1) Проведены работы в области сравнительной геномики регуляции транскрипции. В частности, изучена регуляция генов пластид растений и водорослей и также промоторы этих генов, зависящие от РНК-полимераз бактериального типа (А.В. Селиверстов, В.А. Любецкий). Для этих пластид, особенно высших растений, набор сигма-субъединиц различается даже в относительно близких таксонах, и было показано, что узнаваемые ими промоторы похожи по последовательности. Филогенетическое распределение предсказанных промоторов в общем согласуется с доступными данными о распределении генов сигма-субъединиц. Примечательно, что во многих геномах обнаружены псевдогены, ранее кодировавшие сигма-субъединицы, и как раз в этих геномах соответствующие промоторы отсутствуют или значительно отличаются от их консенсуса, что указывает на чрезвычайную эволюционную пластичность системы промотор – сигма-субъединица. С другой стороны, эти исследования показали высокую консервативность промоторов перед некоторыми генами. Промоторы перед генами rbcL, psbA, psbB, psbE и psaA весьма консервативны не только у цветковых, но и у других наземных растений и многих водорослей из таксона Streptophyta. Для гена psbA консервативный промотор найден даже в хлоропласте у вторичного эндосимбионта Bigelowiella natans из таксона Cercozoa, Chlorarachniophyceae. Однако у голосеменного Cycas taitungensis и мха Anthoceros formosae не удалось найти промотор перед геном psbA, а у Chlorokybus atmophyticus сохранился только -35 бокс промотора. Промотор перед геном psbE предсказан у многих Streptophyta, обладающих геном psbE. Среди них – большинство цветковых, все доступные голосеменные, папоротникообразные и мохообразные, а также водоросли Chaetosphaeridium globosum, Staurastrum punctulatum и Zygnema circumcarinatum. У водорослей Chara vulgaris, Chlorokybus и Mesostigma viride не найден промотор перед геном psbE. Промотор перед геном rbcL консервативен у всех наземных растений и у водоросли Chara. Консервативный промотор перед геном psbB найден у большинства семенных растений, включая голосеменные Cycas и Pinus spp. Промотор перед геном psaA консервативен не только у наземных растений, но и у большинства водорослей таксона Streptophyta, за исключением Chlorokybus и Mesostigma. Для этого исследования разработан алгоритм, который осуществляет эффективный поиск двухбоксового сигнала в заданном наборе нуклеотидных последовательностей. Для исходного набора последовательностей программа отыскивает в каждой последовательности (быть может, кроме небольшого их числа) сайт регуляции, состоящий не из одного, как обычно, а из двух слов с заданными длинами, которые расположены на некотором расстоянии друг от друга. Для этого расстояния указывается интервал возможных значений, причем значениям приписываются веса, которые задается любой ступенчатой функцией (что позволяет выделять предпочтительные расстояния между словами).

В другом исследовании описаны потенциальные регуляторные участки перед генами биосинтеза пролина у гамма-протеобактерий родов Pseudomonas и Shewanella (В.А. Любецкий, А.В. Селиверстов). Здесь предсказан консервативный сайт связывания траскрипционного регулятора, расположенный вблизи промотора.

В тесном сотрудничестве с УНЦ «Биоинформатика» проведен поиск регуляторных структур типа РНК-переключателей в бактериальных метагеномах, а также проведена функциональная аннотация 1443 генов, кодирующих белки, описаны гены стабильных РНК (рибосомных, транспортных и пр.) и также новые потенциальные регуляторные элементы: РНК-переключатели, Т-боксы, DnaA-боксы (А.Г. Витрещак).

(2) Разработана модель эволюции ДНКовых мотивов (К.Ю. Горбунов, В.А. Любецкий). В этой модели рассматривается эволюционное дерево факторов транскрипции, причем каждому из современных факторов соответствует набор узнаваемых им сайтов в ДНК. Алгоритм реконструирует мотивы (матрицы частот) во внутренних узлах дерева (т.е. для предковых факторов), а затем выделяет множество ребер, на которых произошли резкие изменения. На основе этой модели и данных полученных в УНЦ «Биоинформатика» проведен счет и получены эволюционные сценарии для многих факторов транскрипции, включая NrdR (регуляция гена рибонуклеотид-редуктазы и других генов, связанных с репликацией), MntR (регуляция транспорта марганца), LacI (регуляция катаболизма сахаров), FNR/CRP (регуляция реакции на нитритный стресс), Fur (регуляция генов транспорта и метаболизма железа), MUR (регуляция генов транспорта и метаболизма марганца), Rrf2 (большое семейство, состоящее из подсемейств CysR, IscR, NsrR, RirA и регулирующее гены, связанные с метаболизмом серы, железа и реакцией на нитритный стресс).

Разработаны две модели эволюции регуляторного сигнала вдоль эволюционного дерева, включая сигналы классической аттенюаторной регуляции, Т-боксовой регуляции, РНК-переключателей и ряда других, на основе реконструкции современных состояний сигнала в соответствии с принципом минимальности числа эволюционных событий, или на основе минимизации предложенного функционала гиббсовского типа (В.А. Любецкий, К.Ю. Горбунов, Е.А. Жижина и другие). Множественное выравнивание исходных сайтов не предполагается известным. Наоборот, полученная программа кроме восстановления предковых регуляторных последовательностей позволяет строить множественное выравнивание исходных сайтов регуляции с учетом их вторичной структуры.

(3) Разработана модель классической аттенюаторной регуляции экспрессии генов метаболизма аминокислот (В.А. Любецкий, С.А. Пирогов. Л.И. Рубанов и другие). Алгоритм, реализующий эту модель, реализован как общедоступный сервер на сайте http://lab6.iitp.ru. Модель позволяет численно оценивать зависимость уровня репрессии от концентрации аминокислоты и, тем самым, служит еще одним средством предсказания сайтов аттенюаторной регуляции. Получаемые предсказания согласуются с известными экспериментальными и сравнительно геномными данными. С помощью этой модели был проведен массовый поиск классической аттенюаторной регуляции, результаты которого проверены построением соответствующих множественных выравниваний. Предсказаны более 120 новых классических аттенюаторных регуляций у альфа-протеобактерий, бета-протеобактерии, гамма-протеобактерий, дельта-протеобактерий, актинобактерий и бактероидов.

Предложен принципиально новый математический подход к описанию марковских цепей, которые возникают в такого сорта стохастических моделях – на основе так называемой системы переписывания термов (В.А. Любецкий, Е.А. Асарин). Описание позволяет изучать математические свойства модели и компьютерно реализовать модель, не используя метод Монте-Карло, который имеет известные недостатки, сказывающиеся на результатах моделирования.

Проведены исследования РНКовых регуляторных систем в геномах актинобактерий (В.А. Любецкий, А.В. Селиверстов). Впервые найдены структуры типа Т-бокс, регулирующие инициацию трансляции гена изолейцил-тРНК синтетазы ileS (все известные до этого Т-боксы регулируют преждевременную терминацию транскрипции). В ряде геномов перед геном leuA, кодирующем 2-изопропилмалат синтазу, обнаружен новый потенциальный регуляторный сигнал (LEU-элемент), принимающий альтернативные конформации псевдоузла, и показано его возможное происхождение из регуляторного сигнала траспозаз. Идентифицирован белок, возможно, связывающийся с LEU-элементами. РНКовая регуляция (названная LEU1) показана и для генов 2-изопропилмалат синтаз альфа-протеобактерий, однако механизм регуляции в этом случае, по-видимому, основан на комбинации РНКового псевдоузла и короткого гена, кодирующего лидерный пептид.

Предложен алгоритм и на его основе проведен массовый поиск Т-боксовой транскрипционной регуляции, предсказано более 400 потенциальных регуляций (В.А. Любецкий, Л.А. Леонтьев). Анализ полученных результатов, в частности, позволил оценить распределение этой регуляторной системы по основным филогенетическим группам бактерий. В том числе, Т-боксовая регуляция транскрипции предсказана у нескольких альфа- и дельта-протеобактерий, у бактерий из филогенетической группы Chloroflexi и у микоплазм.

Рис. 1. Консервативный псевдоузел и ген лидерного пептида у Micobacterium bovis. Отмечены лейциновые кодоны и стоп-кодон гена лидерного пептида. Полужирным показан сайт GGAGCA связывания рибосомы перед регулируемым геном leuA.

Идентифицированы участки, которые могут регулировать работу генов хлоропластов на уровне сплайсинга или процессинга мРНК (А.В. Селиверстов, В.А. Любецкий). Существование во многих генах хлоропластов самосплайсирующихся интронов приводит к необходимости задержать инициацию трансляции до того, как произойдет сплайсинг: иначе в результате трансляции будут синтезированы нефункциональные белки. Действительно, в 5'-областях ряда генов нами обнаружены консервативные участки, способные к образованию вторичной структуры, существование которых в различных геномах коррелирует с наличием интронов у данных гена и генома. В темноте происходит процессинг, но рибосома не может начать трансляцию из-за того, что регуляторный белок закрывает сайт связывания рибосомы. На свету рибосома связывает зрелую мРНК и происходит трансляция.

Показана корреляция между наличием шпильки, мешающей инициации трансляции, и редактированием мРНК у мохообразных и папоротникообразных для вторичной структуры 5'-лидерных областей генов accD и atpH (В.А. Любецкий, А.В. Селиверстов). Поскольку консервативного сайта здесь не найдено, нами предположено, что вторичная структура обеспечивает задержку инициации трансляции на время, характерное для спонтанного распада шпильки мРНК и достаточное для завершения редактирования.

Предсказана регуляция на уровне процессинга мРНК посредством длинной шпильки с повтором нуклеотидов гена mntH, кодирующего транспортер марганца, и гена gloA, кодирующего никель-зависимую глиоксалазу и еще для нескольких гипотетических генов, один из которых является транспортёром, у бактерий из рода Brucella (В.А. Любецкий, А.В. Селиверстов).

Рис. 2. Структура оперонов и положение длинных шпилек с повтором из 8 нуклеотидов у Brucella spp.

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

(4) Проведены работы в области молекулярной эволюции. Предложен метод удаления филогенетического шума в множественном выравнивании нуклеотидных или аминокислотных последовательностей на основе специального варианта относительной энтропии – энтропии разбиения строк (видов) множественного выравнивания (для каждого фиксированного столбца отдельно) относительно списка надежных клад видов (В.А. Любецкий, Л.А. Русин). Этот метод включает комплекс программ генерации деревьев и фильтрации сайтов, который позволяет строить случайный набор вариантов бинарного разрешения заданного политомического бескорневого дерева путем добавления новых вершин в окрестности каждой вершины со степенью больше трех. Разработан алгоритм и создана программа для эффективного множественного выравнивания последовательностей и также для поиска консервативных участков в наборе нуклеотидных последовательностей на основе известного дерева видов (В.А. Любецкий, А.В. Селиверстов). Предложен алгоритм, реализованный в виде пакета программ, для согласования набора эволюционных деревьев генов с целью построения супердерева - дерева видов (В.А. Любецкий, В.В. Вьюгин, О.А. Зверков). Создан метод реконструкции эволюционных сценариев для семейств белков, включающих дупликации, потери и горизонтальные переносы генов, и проведен массовый счет, который позволил им обнаружить около ста событий горизонтального переноса генов различных тРНК-синтетаз, лигаз и рибосомных белков (В.А. Любецкий, В.В. Вьюгин, О.А. Зверков). Получены суммарные характеристики эволюционных событий на дереве видов, например, события массовой дупликации предкового генома, проведены сравнение эволюционных сценариев и оценка достоверности отдельных событий потенциальных горизонтальных переносов. В частности, из 132 КОГов отобраны те 365 генов, которые в наибольшей степени ответственны за рассогласование деревьев генов и видов. Сравнение различных сценариев показало, например, что гипотеза об одном событии приобретения гена уменьшает число потерь генов в среднем по этим КОГам на 4.4 события потери. Получены оценки различных сценариев: например, в одном допускались горизонтальные переносы, а в другом нет. Получены распределения суммарного числа дупликаций и других эволюционных событий для обоих сценариев по подсемействам прокариотов. Например, в обоих сценариях имеют место около 93 дупликаций генов в последнем общем предке Архей; сделан вывод, что подобные характеристики эволюции численно не зависят от гипотезы о событиях горизонтального переноса.

Разработана компьютерная программа, которая по дереву генов (или по набору ортологичных аминокислотных последовательностей – в этом случае используется аппарат нечётких множеств) и дереву видов ищет события горизонтального переноса гена (В.А. Любецкий, К.Ю. Горбунов). С ее помощью проведён массовый поиск таких событий по всему спектру бактериальных видов, выявлено более 50 пар, 5 из которых соответствуют предковым горизонтальным переносам. Например, обосновано предположение о горизонтальном переносе между предками видов {B. halodurans, B. subtilis, S. aureus} и {V. cholerae, E. coli, Buchnera sp., H. influenzae, P. multocida} гена триптофанил-тРНК синтетазы (КОГ 180).

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

Прведены работы, направленные на построение дерева эволюции животных (Metazoa), а также на анализ эволюционных событий, связанных с относительным временем и механизмами образования дифференциации клеток и многоклеточности (Л.Ю. Русин, В.А. Любецкий совместно с А.В. Алешиным - Институт физико-химической биологии им. Белозерского).

Результаты, полученные в рамках следующих математических работ, существенно используются при построении моделей и алгоритмов, которые лежат в основе нашей работы в области биоинформатики, описанной выше в разделе I.

II. Обзор результатов, полученных в лаборатории в 2005-2007 годах, по теме «проблемы эффективного описания объектов, процессов, алгоритмов на основе теорий модельной полноты, интуиционистской и дескриптивной теорий множеств, нестандартного анализа, стохастических игр (многопараметрической оптимизации)»

В известных научных издательствах опубликованы две монографии: В.Г. Кановея и M. Reeken, В.Г. Кановея и В.А. Любецкого и принята к публикации еще одна монография В.Г. Кановея. Эти книги посвящены исследованиям в тех областях современной математики, где проблема эффективности играет важную роль. Также опубликованы три большие работы В.Г. Кановея и В.А. Любецкого в журналах <Успехи математических наук> и <Труды Математического института им. Стеклова> по отдельным направлениям математических исследований, связанных с эффективностью.

В целом В.Г. Кановеем и В.А. Любецким получены следующие результаты по четырем направлениям.

1. Проведена эффективная классификация объектов в дескриптивной теории множеств.

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

Рассматриваемые в этой связи фактор-структуры могут быть, например, счетными алгебраическими структурами определенного класса с точностью до изоморфизма, орбитами действий тех или иных топологических групп, мерами в пространстве мер и т.д. Общие рамки постановки и решения проблем эффективной сводимости фактор-структур выработаны в эргодической теории и дескриптивной теории множеств в 1990-х годах. Нами за отчетный период получены решения некоторых важных проблем в этой области.

1.1. Построено возрастающее конфинальное семейство борелевских отношений эквивалентности.

1.2. Построены эффективно несводимые друг к другу отношения эквивалентности в модели Соловея.

Модель Соловея, т.е. модель аксиом теории множеств, в которое все эффективно определимые множества измеримы по Лебегу, интересна тем, что в ней понятие эффективности может трактоваться, вероятно, самым широким из известных сейчас способов – как ординальная определимость, т.е. определимость с параметрами, которые могут быть как вещественными числами, так и ординалами. Это включает борелевскую, проективную, и многие другие типы эффективной определимости. Здесь мы можем рассматривать такие эффективные отношения эквивалентности на вещественной прямой, которые в борелевской области не могут быть выражены. Получен следующий пионерский результат в этой области: в модели Соловея определена естественная система отношений эквивалентности, которые попарно несводимы друг к другу даже ординально определенными функциями.

1.3. Получена эффективная сводимость для монадических отношений эквивалентности в области нестандартного натурального ряда.

1.4. Получена эффективная канонизация борелевских отношений эквивалентности.

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

2. Проведена классификация упорядоченных структур Хаусдорфа

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

3. Изучены эффективные свойства регулярности в дескриптивной теории множеств

К свойствам регулярности относятся такие свойства точечных множеств, как свойство совершенного ядра, измеримость, свойство Бэра. Точечные множества, не имеющие совершенного ядра (т.е. просто подмножества, гомеоморфного канторову дисконтинууму), рассматриваются как малые, и со времен основополагающих работ П.С. Новикова принято считать, что при разумных ограничениях эффективно определенное множество этого типа должно допускать эффективное перечисление его точек в виде трансфинитной последовательности. Усиливая ряд предыдущих результатов, В.Г. Кановей и В.А. Любецкий доказали эту гипотезу для множеств второго проективного класса, которые допускают эффективное определение даже с произвольным (сколь угодно большим) счетным ординалом в роли параметра. Для случая, когда такого параметра нет, результат был уже известен с 1970-х годов.

4. Эффективное построение нестандартных расширений математических структур

Одной из центральных проблем в области нестандартного анализа с начала 1980-х годов считалась проблема эффективного построения нестандартных расширений вещественной прямой. Дело в том, что известные до недавнего времени методы построения такого расширения опирались на такие существенно неэффективные объекты как полное упорядочение или нетривиальный ультрафильтр над натуральным рядом, существование которых само доказывалось лишь с помощью крайне неэффективной аксиомы выбора. Решение этой проблемы именно для нестандартных расширений вещественной прямой впервые получено В.Г. Кановеем. Далее в этом направлении показано, что эффективно определенные нестандартные расширения существуют не только для вещественной прямой, но даже для всего теоретико-множественного универсума (В.Г. Кановей, В.А. Любецкий). Получено эффективное построение нестандартных универсумов для некоторых других нестандартных теорий множеств и классов, решив тем самым связанные с ними проблемы непротиворечивости и интерпретируемости (В.Г. Кановей, В.А. Любецкий).

5. Эффективное алгоритмическое описание объектов.

При описании или поиске объектов (в нашем случае объект представлен строкой из нулей и единиц) возможны два способа задания множества, к которому принадлежит искомый объект, что значительно облегчает его поиск:

  1. Прямой путь, когда указывается кластер – множество строк, среди которых находится искомый объект; и
  2. Косвенный путь, когда указывается эффективная стратегия поочерёдного угадывания битов искомой строки такая, которая обеспечивает существенный перевес числа правильных узнаваний битов над числом их ошибочных узнаваний (по условию после каждого узнавания становится известным, было ли оно правильным или ошибочным).

Доказана полиномиальная верхняя оценка на число эффективных стратегий (монотонных правил выбора), хотя бы одна из которых позволяет достичь существенного перевеса числа правильных угадываний битов искомой строки над числом ошибочных угадываний, если известно, что эта строка принадлежит наперед заданному не слишком большому множеству строк известной длины (К.Ю. Горбунов).

Оценка алгоритмической сложности задачи из хорошо известного списка задач является фундаментальной проблемой математической логики. В этом списке находится и задача построения клики в многодольном графе. Доказано, что существование n-клики в n-дольном графе с двумя вершинами в каждой доле эквивалентно непустоте многогранника, стороны которого вычисляются за полиномиальное от n время (А.В. Селиверстов). Предложен алгоритм поиска n-клики в указанном многодольном графе с помощью алгоритма линейного программирования. Размерность соответствующего многогранника позволяет оценить число таких клик сверху. С другой стороны, доказано, что естественные задачи, связанные с поиском в n-дольном графе с двумя вершинами в каждой доле, n-клики с некоторыми естественными свойствами, являются алгоритмически сложными в предположении, что классы NP и coNP различны.

6. Многопараметрическая оптимизация со стохастическими условиями: алгоритмический аспект.

Алгоритмически изучена задача многопараметрической оптимизации, в которой даны две функции, каждая от двух аргументов, и ищется их совместный экстремум (точка равновесия) по Нэшу. Эти две функции существенно включают стохастику, которая естественно возникает в приложениях. Ищутся оптимальные управляющие стратегии, которые образуют точку равновесия по Нэшу, равномерно по состоянию эволюционирующей системы. Такое решение является неподвижной точкой соответствующего отображения.

Построен алгоритм и доказано, что в предположении сходимости, он приводит к решению задачи многопараметрической оптимизации (П.В. Голубцов, В.А. Любецкий). Вопрос о том, когда в строгом смысле этот алгоритм сходится, очень сложен и далек от своего решения, также как и вопрос, когда существует точка равновесия по Нэшу в этой задаче. Эта задача часто возникает в приложениях, в частности, при построении наших биоинформатических алгоритмов (а также – в экономике, задачах управления ресурсами и т.д.). Хотя общих математических результатов по этой задаче не получено обширный счет с помощью нашего алгоритма показал, что для самого широкого выбора данных в этой задаче алгоритм численно сходится к решению. Последнее легко проверить, подставляя полученное решение в исходные функции. Как показало моделирование, решение этой задачи обладает неожиданными свойствами в зависимости от информационной структуры задачи. В качестве примеров информационных структур рассмотрены следующие: отсутствие информации, полная информация; полная информация для оптимизации первой функции и ее отсутствие для второй; симметричная неполная информация; неполная информация для первой функции и ее отсутствие для второй; независимая неполная информация. Например, сделан вывод: увеличение количества доступной информации может приводить к ухудшению результата оптимизации по обеим функциям. « back