СЕКТОР № 1.1

Сектор компьютерной логики в информационных процессах

Заведующий сектором – д.ф.-м.н., проф. Любецкий Василий Александрович

Тел. (095) 299-83-54, (095) 413-46-43; E-mail: lyubetsk@iitp.ru

Ведущие ученые сектора:

д.ф.-м.н.	Верещагин Н. К.	д.ф.-м.н.	Чагров А. В.
д.б.н.	Гельфанд М. С.	к.ф.-м.н.	Вьюгин В. В.
д.ф.-м.н.	Голубцов П. В.	к.ф.-м.н.	Горбунов К. Ю.

Направления исследований:

· построение приемлемой сложности (квадратичных и т.п.) алгоритмов для анализа регуляции на уровне ДНК и РНК: поиск регуляторного сигнала и заданного паттерна в геномной последовательности, поиск консервативных и альтернативных вторичных структур. На этой основе анализ сложно взаимодействующих регуляторных систем;

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

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

Основные результаты

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

Усовершенствован предложенный нами приблизительно линейной сложности алгоритм для нахождения пар шпилек – тех характерных образований (в молекуле РНК), которые участвуют в формировании ее вторичной структуры. На этой основе разработаны компьютерные программы для поиска альтернативных и консервативных вторичных структур.

Усовершенствован предложенный нами алгоритм приблизительно линейной сложности, который по набору деревьев (каждое дерево – родословная какого-то одного современного белка, оно называется эволюционным деревом этого белка) строит наилучшим образом согласующее их все («консенсусное» или усредненное) дерево. Это консенсусное дерево представляет собой родословную тех видов, которые являются носителями соответствующих белков. Рассматриваемая задача построения эволюционного дерева видов (таксонов) на основе набора эволюционных деревьев белков является традиционной в молекулярной биологии. Алгоритм компьютерно реализован и просчитан для нескольких групп видов организмов, а также для групп эволюционных деревьев митохондриальных белков и для комплексов ортологичных генов.

Совместно с фирмой Integrated genomics продолжено исследование конкретных регуляторных систем в геномах бактерий. А именно, проанализированы аргининовый регулон в различных таксономических группах, системы множественной лекарственной устойчивости в энтеробактериях, регуляции синтеза ароматических аминокислот и утилизации пентоз, а также утилизации железа (FUR) и FNR-регулоны в гамма-протеобактериях, SOS-ответа и утилизации пентоз в Грам-положительных бактериях. Во всех случаях найдены новые регулируемые гены, а в некоторых – новые регуляторные сигналы.

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

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

Предсказаны регуляторные вторичные структуры мРНК (T-box сигналы) перед генами, кодирующими аминоацил-тРНК синтетазы и ферменты биосинтеза аминокислот в Грам-положительных бактериях. Семейство регулируемых T-box сигналами генов расширено за счет предсказания регуляции у новых генов.

Исследованы гены метаболизма жирных кислот у E. coli, H. influenza, V. cho-lerae, Y. pestis. Обнаружено, что белок FadR регулирует все стадии окисления длинноцепочечных жирных кислот и частично – биосинтез жирных кислот. Показано, что ген yafH, кодирующий ацил-СоА-дегидрогеназу, совпадает с геном, описанным ранее как fadE, и найдены новые члены FadR-регулона.

Ранее разработанный нами алгоритм поиска регуляторного сигнала показал свою эффективность. В частности, были найдены палиндромный сигнал длины 20 пуринового регулятора в Р. horikoshii, сигнал треголозного регулятора. Были обнаружены непалиндромный сигнал регулятора marx длины 20 в Е. coli и cggr-сигнал в родственных бактериях В. anthracis, В. subtilis, В. hulodurens. Был проведён обсчёт ортологичных рядов по генам организмов, родственных с Е.coli и В.subtilis. Результаты сравнивались с материалами регуляции этих организмов из известных баз данных dpinteract и dbtbs. Найдены кандидаты на новые сайты, которые переданы биологам для экспериментальной проверки.

Усовершенствован ранее разработанный нами алгоритм поиска перекрытий, т.е. структур РНК, состоящих из двух зацепленных между собой шпилек (перекрытия участвуют в образовании альтернативных вторичных структур РНК, служащих для регуляторного переключения в процессах трансляции и транскрипции). При этом учитывались такие особенности как различная частота склеек определенных пар букв и наличие общего для двух шпилек длинного склеенного участка. Разработана новая версия этого алгоритма, основанная на первоначальном составлении списка подходящих шпилек и последующего образования из них перекрытий; проводился отбор шпилек по уровню свободной энергии. Были составлены таблицы распределения начал и концов петель шпилек по позициям в исходной последовательности РНК и обнаружено, что в ряде известных биологических примеров эти позиции с высокой точностью предсказываются нашим алгоритмом. На этой основе начата работа по локализации биологически значимых перекрытий.

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

Разрабатывались методы для анализа эволюционных событий в геномах организмов на основе филогенетических деревьев белков. Предложен алгоритм для выявления генов, подозрительных на горизонтальный перенос в ходе их эволюционной истории. Он основан на анализе рассогласованности между деревьями эволюции генов и видов в сайте, занимаемом этим геном. Компьютерная программа, реализующая этот алгоритм, применялась к геномам 42 микроорганизмов, представленным в 128 комплексах ортологичных групп генов (из базы данных genbank национального центра биотехнологической информации США).

С помощью формально-логических средств описаны свойства понятия «знание». Для этого язык исчисления предикатов расширен операторами k(i,s), интерпретируемыми как «агент i знает утверждение s». Доказано, что многие среди так полученных теорий конечно аксиоматизируются, а их сложность не превосходит сложности классической логики предикатов.

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

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

Развит метод построения оптимальной измерительно-вычислительной системы на базе исходной неточно заданной инвариантной измерительной системы (в случаях непрерывно-дискретного или параметрического задания последней). Исследована проблема оптимальной калибровки такого рода инвариантных измерительных систем.

Продолжено исследование общих свойств категорий преобразователей информации (ПИ). Показано, что категория ПИ является моноидальной категорией специального вида. Многие важные категории ПИ, такие как категории стохастических, нечетких, многозначных ПИ, могут быть снабжены структурой категории Клейсли, при построении которой ключевую роль играет функтор T, переводящий объект A в объект TA всех "распределений на A". В связи с этим исследован вопрос о наделении категории Клейсли структурой моноидальной категории ПИ. Было показано, что для этого достаточно существования естественного преобразования "переводящего" пару "распределений" в "независимое совместное распределение".

Изучалось расширение языка действительных чисел одноместным функциональным символом f в связи с известной проблемой об отделении формулой этого языка двух классов функций (истинность и ложность этой формулы должна определяться тем, функция из какого класса подставляется вместо f). Доказано, что для любого натурального числа i класс функций, имеющих производную i-го порядка, отделим от своего дополнения. Сформулирована гипотеза о неотделимости класса многочленов от класса функций, «склеенных» из бесконечного числа многочленов, и от своего дополнения в классе функций, «склеенных» из конечного числа многочленов. Доказан ряд частных случаев этой гипотезы.

Обнаружено, что многие NP-полные модальные логики, даже не являющиеся локально табличными, после ограничения числа используемых переменных становятся P-полными, т.е. "ведут себя" подобно классической логике высказываний: для них условие выполнимости может проверяться непереборным алгоритмом. Среди таких логик находится важная логика S4.3.

Найдено новое неравенство для шенноновской энтропии дискретных случайных величин (далее перечисляются результаты, полученные в сотрудничестве с рядом математиков МГУ и зарубежных).

Найдено новое доказательство теоремы Гача-Альсведе-Кернера о невыделяемости совпадающей информации из двух зависимых источников в последовательности символов.

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

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

Получено описание всех возможных форм структурной функции А. Н. Колмогорова – ключевого понятия в алгоритмической статистике.

Доказано, что по множеству случайных слов, взятых в качестве оракула, можно за полиномиальное от n время найти случайное слово длины n.

Получены результаты о неустойчивости ряда эргодических теорем в случае отклонений в исходных данных от условий алгоритмической случайности.

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

- Howard Hughes Medical Institute, 2001 Meeting of International Research Scholars (Vancouver, June 2001);

- NATO advanced studies institute, Artificial intelligence and heuristic methods for bioinformatics (San Miniato, Italy, October 2001);

- III международная конференция «Проблемы управления и моделирования в сложных системах» (Самара, 2001);

- III международная конференция «Cмирновские чтения» (Москва, 2001);

- VI общероссийская научная конференция «Современная логика: проблемы теории, истории и применения в науке» (Санкт-Петербург, 22-24 июня 2001);

- XVI ежегодная конференция по сложности вычислений (Чикаго, июнь 2001);

- XVIII ежегодный симпозиум по теоретическим вопросам информатики (Дрезден, февраль 2001);

- Международная конференция, посвященная столетию академика П. С. Новикова. (Москва, 27-31 августа 2001).

Сотрудники сектора командировались для чтения лекций и совместной научной работы в ряд университетов и научных центров (Lawrence Berkeley Laboratory, University of California-San Diego, университеты Монтаны, Марселя, Амстердама, Вены, Афин и др.).

Публикации в 2001 г.

Статьи

1. Данилова Л.В., Горбунов К.Ю., Гельфанд М.С., Любецкий В.А. Алгоритм выделения регуляторных сигналов в последовательностях ДНК (1) // Электронный научный журнал «Информационные процессы» (http://www.jip.ru/). 2001, т. 1, № 1, с. 56-63.

2. Гельфанд М.С., Вьюгин В.В., Любецкий В.А. Об одном способе построения деревьев эволюции видов по множественным генетическим данным // Электронный научный журнал «Информационные процессы» (http://www.jip.ru/). 2001, т. 1, № 1, с. 64-77.

3. Данилова Л.В., Горбунов К.Ю., Гельфанд М.С., Любецкий В.А. Алгоритм выделения регуляторных сигналов в последовательностях ДНК (2) // Молекулярная биология. 2001, т. 35, № 6, с. 987-995.

4. Вьюгин В.В., Любецкий В.А. Об одном алгоритме поиска горизонтального переноса гена на основе филогенетических деревьев белков // Электронный научный журнал «Информационные процессы» (http://www.jip.ru/). 2001, т. 1, № 2, с. 167-177.

5. Любецкий В.А., Селиверстов А.В. Об одном вероятностном алгоритме решения NP-полной проблемы // Труды III международной конференции «Смирновские чтения», РАН, Москва, 2001, с. 47-49.

6. Данилова Л.В., Любецкий В.А. Алгоритм выделения регуляторных сигналов: тестирование и биологические применения // Труды III международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 2001, с. 632-634.

7. Кузнецов Н.А., Любецкий В.А., Чернавский А.В. К вопросу о понятии информационного взаимодействия, 2: доречевой интеллект // Труды III международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 2001, с. 25-42.

8. Витрещак А.Г., Гельфанд М.С. Предсказание вторичной структуры РНК. Программа RNApattern – поиск вторичной структуры по паттерну // Труды III международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 2001, с. 623-625.

9. Горбунов И.А., Рыбаков М.Н. Выразительность операторов знания и возможность эффективного описания логик знания // Труды III международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 2001, с. 617-622.

10. Голубцов П.В., Старикова О.В. Инвариантность и калибровка измерительно-вычислительных систем в непрерывно-дискретном случае // Труды III международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 2001, с. 635-641.

11. Чагров А.В. К логическим проблемам семантических аспектов информационного взаимодействия // Труды III международной конференции «Проблемы управления и моделирования в сложных системах», Самара, РАН, 2001, с. 611-616.

12. Горбунов К.Ю, Любецкая Е.В, Любецкий В.А. О двух алгоритмах поиска альтернативной вторичной структуры РНК // Электронный научный журнал «Информационные процессы» (http://www.jip.ru/). 2001, т. 1, № 2, с. 178-187.

13. Mironov A.A, Novichkov P.S., Gelfand M.S. Pro-Frame: similarity-based gene recognition in eukaryotic DNA sequences with errors // Bioinformatics. 2001, vol. 17, no. 1, pp. 13-15.

14. Rodionov D.A., Gelfand M.S., Mironov A.A., Rakhmaninova A.B. Comparative approach to analysis of regulation in complete genomes: multidrug resistance systems in gamma-proteobacteria // Journal of Molecular Microbiology and Biotechnology. 2001, vol. 3, no. 2, pp. 319-324.

15. Makarova K.S., Mironov A.A., Gelfand M.S. Conservation of the arginine repressor DNA binding signal in all bacterial lineages // Genome Biology. 2001, vol. 2, no. 4, pp. research 0013.1-0013.8.

16. Panina E.M., Vitreschak A.G., Mironov A.A., Gelfand M.S. Regulation of aromatic amino acid biosynthesis in gamma-proteobacteria // Journal of Molecular Microbiology and Biotechnology. 2001, vol. 3, no. 4, pp. 529-543.

17. Brudno M., Gelfand M.S., Spengler S., Zorn M., Dubchak I., Conboy J.G. Computational analysis of candidate intron regulatory elements for tissue-specific alternative pre-mRNA splicing // Nucleic Acids Research, 2001, vol. 29, no. 11, pp. 2338-2348.

18. Боринская С.А., Гельфанд М.С., Миронов А.А. Компьютерная геномика: в поисках генов // Химия и жизнь. 2001, № 2, с. 36-40.

19. Гельфанд М.С. Биология in silico // Компьютерра. 2001, № 36(413), с. 20-22.

20. Гельфанд М.С. Аннотация геномов – от последовательности к функции // Компьютерра. 2001, № 36(413), с. 22-25.

21. Горбунов К.Ю. Об одной модели информационной зависимости в алгебраической геометрии // Электронный научный журнал «Информационные процессы» (http://www.jip.ru/). 2001, т. 1, № 2, с. 147-149.

22. Голубцов П.В., Старикова О.В. Калибровка инвариантных преобразователей информации // Электронный научный журнал «Информационные процессы» (http://www.jip.ru/). 2001, т. 1, № 1, с. 78-88.

23. Голубцов П.В., Старикова О.В. Редукция параметрически заданных инвариантных измерительно-вычислительных систем // Вестник Московского Университета, Сер. 3 "Физика и астрономия". 2001, № 6, с. 3-6.

24. Вьюгин В.В. О неустойчивости индивидуальной эргодической теоремы // Проблемы передачи информации. 2001, т. 37, № 2, с. 27-39.

25. V'yugin V.V. Most sequences are stochastic // Information and Computation. 2001, vol. 169, pp. 252-263.

26. Рыбаков М.Н. Операторы всеобщего и распределенного знания: дополнительные выразительные средства в логиках знания // Электронный научный журнал «Информационные процессы» (http://www.jip.ru/). 2001, т. 1, № 1, с. 89-98.

27. Chagrov A.V. All tabular generally post-complete extensions of k4 have interpolation property // Information Processes (http://www.jip.ru/). 2001, т. 1, № 1, с. 50-55.

28. Zakharyaschev M., Wolter F., Chagrov A. Advanced modal logic. – In Gabbay D.M., Guenthner F. (eds.). Handbook of philosophical logic, 2nd edition, vol. 3, Kluver academic publishers, 2001, pp. 83-266.

29. Shen A., Vereshchagin N. Logical operations and kolmogorov complexity // Electronical colloquium on computational complexity. 2001, 5 pp., Ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1002/tr01-088.

30. Vereshchagin N. Kolmogorov complexity conditional to large integers // Electronical colloquium on computational complexity. 2001, 11 pp., Ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1002/tr01-086.

31. Vereshchagin N. An enumerable undecidable set with low prefix complexity: a simplified proof /. Electronical colloquium on computational complexity. 2001, 4 pp., Ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1002/tr01-083

Сданы в печать

1. Вьюгин В.В., Гельфанд М.С., Любецкий В.А. Согласование деревьев: реконструкция эволюции видов по филогенетическим деревьям генов // Молекулярная биология, 25 с.

2. Novichkov P.S., Gelfand M.S., Mironov A.A. Gene recognition in eukaryotic DNA by comparison of genomic sequences // Bioinformatics.

3. Rodionov D.A., Mironov A.A, Gelfand M.S. Transcriptional regulation of pentose utilization systems in the Bacillus/Clostridium group of bacteria // FEMS Microbiol. Lett.

4. Laikova O.N., Mironov A.A., Gelfand M.S. Transcriptional regulation of pentose utilization systems in gamma-proteobacteria // FEMS Microbiol. Lett.

5. Panina E.M., Mironov A.A., Gelfand M.S. Comparative analysis of FUR regulons in gamma-proteobacteria // Nucleic Acids Res. 2001, vol. 29, no. 23.

6. Ponomarenko J.V., Orlova G.V., Frolov A.S, Ponomarenko M.P., Gelfand M.S. SELEX_DB, a database on in vitro selected oligomers adapted for recognizing natural sites and for analyzing both SNPs and site-directed mutagenesis data // Nucleic Acids Res. 2002, vol. 30, no. 1.

7. Permina E.A., Mironov A.A., Gelfand M.S. Damage-repair error-prone polymerase of bacteria: association with mobile genome elements // Gene. 2001 (accepted).

8. Герасимова А.В., Родионов Д.А., Миронов А.А., Гельфанд М.С. Компьютерный анализ регуляторных сигналов в бактериальных геномах. Участки связывания Fnr. Молекулярная биология, 2001, в печати.

9. Голубцов П.В, Старикова О.В. Учет инвариантности в задаче калибровки инвариантных измерительно-вычислительных систем. Математическое моделирование (в печати, выход февраль-март 2002 г.).

10. Садовская Н.С, Лайкова О.Н., Миронов А.А., Гельфанд М.С. Изучение регуляции метаболизма длинноцепочечных жирных кислот с использованием компьютерного анализа полных бактериальных геномов. Молекулярная биология, 2001 (в печати).

Тезисы докладов

1. Vitreschak A.A. Computer analysis of regulation of genes, encoding aminoacyltRNA synthetases and amino acid biosynthetic proteins in Gram positive bacteria: T-box RNA regulatory element. Prediction of regulation of new genes, including amino acid transporters. – In the abstracts of International School «Artifical Intelligence and Heuristic Methods for Bioinformatics», Italy, San-Miniato, October 1-11, 2001, p. 63.

2. Gelfand M.S., Laikova O., Mironov A.A., Novichkov P.S., Panina E.M., Rodionov D.A., Vitreschak A.G. Comparative analysis of bacterial patterns. – In the abstracts of Meeting of HHMI International Research Scholars, Vancouver, Canada, June 20-23, 2001, p. 75.

3. Голубцов П.В., Старикова О.В. Оптимальная калибровка инвариантных измерительно-вычислительных систем в случае параметрической информации о схеме измерения // VII конференция «Обратные и некорректно поставленные задачи», Москва, 2001, с. 19.

4. Golubtsov P.V, Starikova O.V. Invariance Considerations in Problems of Synthesis and Optimal Calibration of Measurement Computer System // First SIAM-EMS Conference Applied Mathematics in our Changing World, Berlin 2001, Collection of Abstracts, p. 66.

5. Чагров А.В. Логика, не являющаяся ни конечно-значной, ни бесконечно- значной // Труды научно-исследовательского семинара логического центра института философии РАН, вып. XIV, Москва, 2000, с. 59-67.

6. Рыбаков М.В., Чагров А.В. Стандартные переводы неклассических формул и относительная разрешимость логик // Труды научно-исследовательского семинара логического центра института философии РАН, вып. XIV, Москва, 2000, c. 81-98.

7. Чагров А.В. Алгоритмическая проблематика в неклассических пропозициональных логиках // Смирновские чтения, III международная конференция, Москва, ИФ РАН, 2001, с. 69-71.

8. Чагров А.В., Чагрова Л.А. Первопорядковая определимость интуиционистских формул на конечных шкалах крипке: алгоритмический аспект // Смирновские чтения, III международная конференция, Москва, ИФ РАН, 2001, с. 71-75.

9. Muchnik An., Vereshchagin N. Logical operations and Kolmogorov complexity // Proc. of 16th annual IEEE conference on computational complexity, Chicago, June 2001, pp. 256-265.