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

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

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

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

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

Совместно с сотрудниками Института генетики и селекции промышленных микроорганизмов, а также МГУ исследован ряд конкретных регуляторных систем: множественной лекарственной устойчивости энтеробактерий, метаболизма ароматических аминокислот и утилизации сахарных кислот гамма-пурпур-ных бактерий, теплового шока (CIRCE-регулон), SOS-ответа и метаболизма аргинина в различных таксономических группах.

Доказана неустойчивость индивидуальной эргодической теоремы Биркгофа. Показано, что утверждение этой теоремы для индивидуальной последовательности может быть неверным, если допустить даже небольшой рост дефекта случайности на фрагментах этой последовательности. Аналогичный результат имеет место для теоремы Шеннона – Макмиллана – Бреймана.

Сформулирована гипотеза о том, что в любом реализаторе множества циркулянтных матриц (т.е. матриц, у которых на каждой из диагоналей, параллельных главной, располагаются одинаковые элементы, и для любых двух из этих диагоналей, отстоящих друг от друга на фиксированное расстояние n, эти элементы совпадают) имеется множество мощности не меньше exp(qn) для некоторого q>0. Доказана более слабая оценка вида exp(n^q) для любого q<1/2.

Получено условие "самоопределимости" структуры вещественных алгебраических чисел, т.е. условие существования фиксированной формулы F(∙) (ее аргументом является новая многоместная предикатная переменная P), для которой F(P) истинна в этой структуре тогда и только тогда, когда предикат P определим в ней.

Показано, что сложность задачи ((a влечет с) и (b влечет d)) не выражается через сложности элементарных задач a, b, c, d, их пар, троек, четверки <a,b,c,d> и их условные сложности относительно друг друга.

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

Доказана теорема о замене для эквивалентных строго импликативных формул в известной модальной логике S3. Обнаружены 29 попарно не эквивалентных в S3 строго импликативных формул с одной фиксированной переменной.

Доказано также, что категория преобразователей информации является моноидальной категорией специального вида. Получены условия, достаточные для того, чтобы категория Клейсли обладала структурой моноидальной категории преобразователей информации. Оно состоит в наличии естественного преобразования, которое переводит пару "распределений" в "независимое совместное распределение".

1. Кузнецов Н.А., Любецкий В.А., Чернавский А.В. К вопросу о понятии информационного взаимодействия // Труды 2-й международной конференции "Проблемы управления и моделирования в сложных системах", Самара, 19-24 июня 2000, с. 8-20.
2. Вьюгин В.В., Горбунов К.Ю., Любецкий В.А. Алгоритмы выделения регуляторного сигнала и построения эволюционных деревьев // Труды 2-й международной конференции "Проблемы управления и моделирования в сложных системах", Самара, 19-24 июня 2000, с. 130-137.
3. Горбунов К.Ю., Любецкий В.А. Об алгоритме выявления регуляторного сигнала в наборе последовательностей // Логические исследования, выпуск 7. М.: Наука, 2000, с. 159-163.
4. Верещагин Н.К., Любецкий В.А. Алгоритм определения вторичной структуры РНК // Труды научно-исследовательского семинара логического центра ИФ РАН, выпуск 14. М.: Изд-во РАН, 2000, с. 99-109.
5. Данилова Л.В., Горбунов К.Ю., Гельфанд М.С., Любецкий В.А. Алгоритм выделения регуляторных сигналов в последовательностях ДНК // Молекулярная биология. 2000 (в печати).
6. Любецкий В.А. Основные понятия школьной математики. М.: Гардарики, 2000, 420 с.
7. Вьюгин В.В. О неустойчивости индивидуальной эргодической теоремы // Проблемы передачи информации (в печати).
8. Горбунов К.Ю. Об оценке матричной сложности множества // Труды 2-й международной конференции "Проблемы управления и моделирования в сложных системах", Самара, 2000, с. 138-140.
9. Новичков П.С., Гельфанд М.С., Миронов А.А. Предсказание экзон-интронной структуры сравнением геномных последовательностей // Молекулярная биология. 2000. Т. 34. № 2. С. 230-236.
10. Панина Е.М., Миронов А.А., Гельфанд М.С. Статистический анализ полных бактериальных геномов: палиндромы и системы рестрикции-модификации // Молекулярная биология. 2000. Т. 34. № 2. С. 246-252.
11. Миронов А.А., Винокурова Н.П., Гельфанд М.С. Программное обеспечение анализа бактериальных геномов // Молекулярная биология. 2000. Т. 34. № 2. С. 253-262.
12. Gelfand M.S., Koonin E.V., Mironov A.A. Prediction of transcription regulatory sites in Archaea by a comparative-genomic approach // Nucleic Acids Res. 2000. V. 28. No. 3. P. 695-705.
13. Vitreschak A.G., Gelfand M.S. Comparative approach to analysis of regulation in complete genomes: Attenuators of aromatic amino acid operons of gamma-proteobacteria // Труды 2-й международной конференции "Проблемы управления и моделирования в сложных системах", Самара, 19-24 июня 2000 г., с. 141-142.
14. Ramensky V.E., Makeev V.Ju., Gelfand M.S., Roytberg M.A., Tumanyan V.G. Bayesian approach to DNA segmentation into regions with different average nucleotide composition // Journees Ouvertes Biologie Informatique Mathematiques (JOBIM’2000), Montpellier, France, Mai 2000, p. 241-248.
15. Витрещак А.Г., Гельфанд М.С. Сравнительный подход к анализу регуляции в полных геномах: аттенюаторы ароматических аминокислотных оперонов гамма-протеобактерий // Молекулярная биология. 2000. Т. 34. № 4.
16. Rodionov D.A., Mironov A.A., Rakhmaninova A.B., Gelfand M.S. Transcriptional regulation of transport and utilization systems for hexuronides, hexuronates and hexonates in gamma purple bacteria // Molecular Microbiology. 2000 (in press).
17. Gelfand M.S., Novichkov P.S., Novichkova E.S., Mironov A.A. Comparative analysis of regulatory patterns in bacterial genomes // Briefings in Bioinformatics, 2000. V. 1. No. 4.
18. Mironov A.A., Novichkov P.S., Gelfand M.S. Pro-Frame: similarity-based recognition in eukaryotic DNA sequences with errors // Bioinformatics. 2000, 18 р. (in press).
19. Верещагин Н.К., Шень А. Математическая логика и теория алгоритмов. Вычислимые функции. М.: Московский центр непрерывного математического образования, 1999, 174 с.
20. Верещагин Н.К., Шень А. Математическая логика и теория алгоритмов. Языки и исчисления. М.: Московский центр непрерывного математического образования, 2000, 274 с.
21. Vereshchagin N., Vyugin M. Independent minimum length programs to translate between given strings // Proc. of 15th Annual IEEE Conference on Computational Complexity, Florence, July 2000, р. 138-144.
22. Romashchenko A., Shen A., Vereshchagin N. Combinatorial interpretation of Kolmogorov complexity // Proc. of 15th Annual IEEE Conference on Computational Complexity, Florence, July 2000, р. 131-137.
23. Vereshchagin N., Vyugin M. Independent minimum length programs to translate between given strings // Theoretical Computer Sciences, 2000, 11 p. (in press).
24. Romashchenko A., Shen A., Vereshchagin N. Combinatorial interpretation of Kolmogorov complexity // Theoretical Computer Sciences, 2000, 12 p. (in press).
25. Shen A., Vereshchagin N. Logical operations and Kolmogorov complexity // Theoretical Computer Sciences, 2000, 5 p. (in press).
26. Vereshchagin N. Kolmogorov Complexity Conditional to Large Integers // Theoretical Computer Sciences, 2000, 9 p. (in press).
27. Голубцов П. В., Старикова О.В. Проблема калибровки для инвариантных измерительно-вычислительных систем // Труды 2-й международной конференции "Проблемы управления и моделирования в сложных системах", Самара, 19-24 июня 2000 г., с. 143-148.
28. Голубцов П. В., Сизарёв Д. В. Синтез оптимальных систем формирования изображений с непрерывным полем зрения // Труды 2-й международной конференции "Проблемы управления и моделирования в сложных системах", Самара, 19-24 июня 2000 г., с. 149-154.
29. Голубцов П. В., Старикова О.В. Учет инвариантности в задаче калибровки измерительно-вычислительных систем // Математическое моделирование, 2000, 20 с. (в печати).
30. Чагров А.В. Об интерполяционном свойстве полных по Э. Посту модальных логик // Труды VI Общероссийской научной конференции "Современная логика: проблемы теории, истории и применения в науке", Санкт-Петербург, 22-24 июня 2000 г. Изд-во ЛГУ, 2000, с. 258-259.
31. Чагров А.В. Два замечания о строго импликативных формулах в модальной логике S3 // Логические исследования, выпуск 7. М.: Наука, 2000, с. 84-89.
32. Чагров А.В. Об эффективных теоремах дедукции в нормальных модальных логиках // Логические исследования, выпуск 7. М.: Наука, 2000, с. 209-216.
33. Чагров А.В. Логика, не являющаяся ни конечнозначной, ни бесконечнозначной // Труды научно-исследовательского семинара логического центра ИФ РАН, выпуск 14. М.: Изд-во РАН, 2000, с. 59-67.
34. Рыбаков М.Н., Чагров А.В. Стандарные переводы неклассических формул и относительная разрешимость логик // Труды научно-исследовательского семинара логического центра ИФ РАН, выпуск 14. М.: Изд-во РАН, 2000, с. 81-98.