Реферат: Алгоритмы и программный комплекс анализа и предсказания процессов функционирования регуляторной системы в клетке Иностранный партнер

Международные научные связи


В 2009 г. Институт систем информатики имени А.П.Ершова СО РАН осуществлял сотрудничесвто с зарубежными организациями по следующим темам:


Алгоритмы исследования микроРНК

Иностранный партнер: Washington University.

Координатор проекта: Georges St. Laurent (США), Черемушкин Е.С., Нечкин С.С. (Россия)

Сроки: 2007-2009


Реализован алгоритм поиска сайтов связывания с ADAR-ферментами. Для этого разработана модель корреляционной матрицы – аналога весовой матрицы, используемой для поиска сайтов связывания с транскрипционными факторами, но учитывающей корреляцию между различными позициями. Весовая матрица М - это матрица из 4хN элементов, каждый из которых соответствует вероятности встречаемости данного нуклеотида в определенной позиции в выборке известных сайтов (фрагментов ДНК).

Построенная матрица была использована для поиска потенциальных сайтов модификации ADAR-ферментов. С помощью аппарата Helicos по технологии deep sequencing были получены 50 млн. коротких фрагментов РНК (длиной 30-120 б.п.), называемых ридами. Среди этих ридов были выбраны те, которые попали на экзоны известных генов. Были выбраны те риды, в которых произошла замена А на G. Затем, из этих ридов были выбраны только те, межвидовая консервативность которых превышает заданный порог. И, наконец, по базе данных EST были выбраны те последовательности, в которых эта замена A/G имеется в известных EST этих генов. Далее эта выборка была проверена с помощью, построенной по известным ADAR-сайтам, корреляционной матрицы.

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


^ Алгоритмы и программный комплекс анализа и предсказания процессов функционирования регуляторной системы в клетке

Иностранный партнер: Biobase, Wolfenbuttel. (Биобэйс, г. Вольфенбюттель).

^ Координаторы проекта: Александр Кель (Германия), к.ф.-м.н. Валеев Т.Ф. (ИСИ СО РАН)

Сроки: 2004-2009


Реализована новая версия (3.0) программного комплекса ExPlain, автоматизирующего рабочее место исследователя-биоинформатика. Программный комплекс включает в себя набор программ, реализующих алгоритмы поиска и анализа регуляторных процессов на клеточном уровне.

В основном охвачены процессы, связанные с ДНК регуляторными структурами, анализ микрочипов и генных сетей. Программный комплекс распространяется как приложение к базам данных компании Биобэйс.

Продукт реализован на языках Perl, C++, является кросс-платформенным приложением. Разработаны и внедрены алгоритмы для поиска сайтов связывания по шаблону, кластеризации списков генов по значениям экспрессии, новые методы статистической обработки данных. Реализованы интерактивные возможности для управления процессом поиска композиционных регуляторных модулей. Серьёзно переработан пользовательский интерфейс.


^ Алгоритмы и программный комплекс анализа состояния дорожного покрытия и распознавания дорожной разметки, трещин в асфальте и областей, залитых битумом

Иностранный партнер: Pathway Services Inc.

^ Координаторы проекта: Randy Blanco (США), Пальянов А.Ю. (ИСИ СО РАН)

Сроки: 2007-2009


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

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


^ Алгоритмы и программное обеспечение для распознавания текстов низкого качества.

Иностранный партнер: Google (Московское представительство)

Координаторы проекта: Дженнифер Трелевич (США), к.ф.-м.н. Мурзин Ф.А. (ИСИ СО РАН)

Сроки: 2009-2010


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


^ Визуализация данных радиоактивного каротажа и расчёт коэффициента нефтенасыщенности методом «Кросс-плот».

Иностранный партнер: Институт математики, информатики и механики, КН МОН Респ. Казахстан.

^ Координаторы проекта: Байжанов Б.С. (Казахстан), к.ф.-м.н. Мурзин Ф.А. (ИСИ СО РАН)

Сроки: 2009-2011


Предложены усовершенствованные алгоритмы и разработана программная система для определения нефтенасыщенности по методу «Кросс-плот» на основе сопоставления аналитических параметров Ca/Si, C/O и пористости по скважине с соответствующими параметрами для моделей пластов. Дополнительно, для компенсации влияния неучтенных в стандартном варианте метода «Кросс-плот» факторов (наличие обсадной колонны и т.п.) программа производит так называемую калибровку метода – привязку к опорным пластам с известной нефтенасыщенностью.


^ Кластерный анализ средствами CUDA

Иностранный партнер: Институт математики, информатики и механики, КН МОН Респ. Казахстан.

Координаторы проекта: Байжанов Б.С. (Казахстан), к.ф.-м.н. Мурзин Ф.А. (ИСИ СО РАН)

Сроки: 2009-2011


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

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

Произведено тестирование алгоритма на небольших объемах данных (около 500 точек). Проведены подготовительные работа для тестирования на больших объемах (более миллиона) точек с целью определения качества и границ применимости алгоритма.


^ Вычисления над недискретными структурами: модели, семантика и сложность

Иностранный партнер: Университет Зигена, Германия.

Координаторы проекта: Дитер Шпреен (Германия), акад. Ершов Ю.Л. (участник от ИСИ - д.ф.-м.н. В.Л. Селиванов)

Сроки: 2005-2009


Построен полный аналог классической иерархии Вагнера для класса регулярных апериодических омега-языков, играющих важную роль в спецификации и верификации систем с конечным числом состояний. Доказан ``апериодический'' аналог теоремы Бюхи-Ландвебера. Изучена разностная иерархия разбиений и некоторые начальные сегменты сводимости Вэджа в некоторых топологических пространствах, интересных для теоретической информатики.


^ Проект РФФИ и Deutsche Forschungemeinschaft (German Research Foundation) № 09-01-91334-ННИО_а

«Формальные методы построения и анализа распределенных систем реального времени»

^ Иностранные партнеры: Ольденбургский Университет, Университет Бундесвера, г. Мюнхен, Германия

Координаторы проекта: д.ф.-м.н., проф. И. Б. Вирбицкайте (ИСИ СО РАН), проф. Айке Бест (Университет г. Ольденбурга, Германия)

Сроки: 2009-2011


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

На основе симметричной конструкции открытых морфизмов дано унифицированное определение бисимуляции «с шипами» (barbed bisimulation) для временного расширения интерливинговой модели – временных систем переходов с инвариантами, и наследственной сохраняющей историю бисимуляции для «истинно параллельных» геометрических моделей – «безвременных» и временных автоматов высших размерностей. Такая теоретико-категорная унификация эквивалентностей позволяет решить проблему их распознавания для конечных классов моделей.

Предложен оригинальный подход к построению логических спецификаций гибридных систем на основе языка Σ-формул и вычислимого анализа. Исследованы условия, при которых траектории гибридных систем являются вычислимыми функционалами. Предложенная формализация отличается от ранее рассматриваемых тем, что непрерывная и дискретная часть, а также их взаимодействие определяется формулами в рамках одной и той же алгебраической модели. Это позволяет исследовать безопасность гибридных систем на языке Σ-формул.

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


Мурзин Ф.А. (18.11.09 – 21.11.09) – участие в Российской научно-технической выставке в США, Exhibition Center McCormick Place, г. Чикаго, США.

Презентация прикладных исследований в области информационных технологий, ведущихся в Институте систем информатики СО РАН

Малюх В.Н. (02.12.09 – 05.12.09) – участие в выставке EuroMold-2009, Франкфурт, ФРГ. Презентация продукта «RhinoAssembly».


Организация и проведение международных конференций


Седьмая международная конференция памяти академика А.П. Ершова «Перспективы систем информатики»

15-19 июня 2009 г.

Седьмая международная конференция памяти академика А.П. Ершова «Перспективы систем информатики» прошла в Новосибирске с 15 по 19 июля. В работе конференции приняли участие 35 ученых из различных стран мира.


^ Семинар с международным участием «Знания и Онтологии *ELSEWHERE* 2009».

(http://www.iis.nsk.su/news/conferences/20090303_elsewhere/index_e.shtml).

27 июля 2009 г.

Семинар прошёл г. в Москве в Высшей Школе Экономики в рамках 17-ой Международной конференции по понятийным структурам (17th International Conference on Conceptual Structures, 26-31 июля 2009г., ICCS-2009, http://iccs09.hse.ru/index.html). Семинар был продолжением семинара «Знания и Онтологии *ELSEWHERE*», который прошел 2 октября 2008 года в городе Дубна в рамках одиннадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-08 (http://www.raai.org/cai-08/).

Первый и второй семинары ELSEWHERE были задуманы организаторами Загорулько Ю.А. и Шиловым Н.В. как рабочие совещания для представления и обсуждения среди российских специалистов подходов и результатов исследований, которые ведутся в ИСИ СО РАН по нескольким проектам: «Исследование и классификация парадигм компьютерных языков» (РФФИ № 08-01-00899), и «Формальные языки и методы спецификации, анализа и синтеза информационных систем» (Проект РАН 2/12). Программный комитет семинара ELSEWHERE-2009 состоял из 4 человек и включал кроме организаторов еще 2 участника, в том числе Prof. Natasha Alechina (School of Computer Science, University of Nottingham, Great Britain). Программный комитет отобрал для представления на семинаре и публикации в Трудах 10 докладов из числа 15 присланных для отбора работ. Кроме работ, прошедших отбор, на семинаре ELSEWHERE-2009 были представлены два приглашенных доклада, в том числе доклад Prof. Jack Stecher (Norwegian School of Economics and Business Administration) «Knowledge and Backward Induction in Repeated Games».

^ Список иностранных специалистов, принятых Институтом

С 15 по 19 июля 2009 года в рамках работы Седьмой международной конференции памяти академика А.П. Ершова «Перспективы систем информатики» ИСИ посетили следующие зарубежные специалисты: Абрамски Самсон (Великобритания); Баар Томас ( Германия ); Бенаисса Назим ( Франция ); Бенаму Фредерик (Франция); Бенэ Жан (Франция); Бьорнер Динес (Дания); Веанс Маргус (США); Воронков Андрей (Швеция); Вюртингер Томас (Австрия); Гамильтон Джеффри (Ирландия); Глюк Роберт (Дания); Гутман Вальтер (Германия); И Кванкын (Республика Корея); Ковач Лаура (Швейцария); Кумар Филипп (Германия); Ларсен Ким (Дания); Миякава Масахиро (Япония); Могенсен Торбен ( Дания ); Мураи Ясуюки (Япония); Невядомски Артур (Польша); Пардини Джованни (Италия); Педрейра Оскар (Испания); Рама Аурелиано (Италия); Руссо Алехандро (Аргентина); Силва Хосеп (Испания); Тиле Лотар (Швейцария); Трелевич Дженнифер (США); Феля Виктор (Румыния); Фенсель Дитер (Австрия); Шерый Ондржей (Чехия); Шоненберг Елена (Нидерланды); Шретер Мацей (Польша); Штудер Томас (Швейцария); Шульте Вольфрам (США); Ясуда Теруо (Япония).


В длительных командировках находятся

Т.М. Яхно, Турция, г. Измир, чтение лекций, научная работа в Университете им. 9 сентября.


Календарь зарубежных командировок по странам


Загорулько Ю.А. (23.09 – 25.09.2009) – участие с докладом в 8-й Международной конференции «SoMeT-2009» (New Trends in Software Methodologies, Tools, and Techniques), г. Прага, Чехия.

Загорулько Г.Б. (23.09 – 25.09.2009) – участие с докладом в 8-й Международной конференции «SoMeT-2009» (New Trends in Software Methodologies, Tools, and Techniques), г. Прага, Чехия.

Ануреев И.С. (27.09-2.10.2009) – участие в 18th International Workshop “Concurrency, Specification and Programming” (CS&P'09), Krakow-Przegorzaly, Польша

Гаранина Н.О. (27.09-2.10.2009) – участие в 18th International Workshop “Concurrency, Specification and Programming” (CS&P'09), Krakow-Przegorzaly, Польша

Грибовская Н.С. (25.09-5.10.2009) – участие в 18th International Workshop “Concurrency, Specification and Programming” (CS&P'09), Krakow-Przegorzaly, Польша.

Дубцов Р.С. (26.08-15.09.2009) – участие в 17th International Symposium "Fundamentals of Computation Theory" (FCT'09), Wroclaw, Польша.

Кудинов О. (2.11-30.11.2009) – научный визит в Университет Бундесвера г. Мюнхена (Германия) в рамках гранта DFG/РФФИ № 09-01-91334-ННИО_а

Марьясов И.В. (03.08.09 - 17.08.09)- участие в 30th International Summer School
« Logics and Languages for Reliability and Security», Marktoberdorf, Germany.

Мурзин Ф.А. (18.11.09 – 21.11.09) – участие в Российской научно-технической выставке в США, Exhibition Center McCormick Place, г. Чикаго, США.

Нечкин С.С. (02.05.09 – 03.10.09) – научная командировка в Washington University, США.

Ошевская Е.С. (26.08-15.09.2009) – участие в 17th International Symposium "Fundamentals of Computation Theory" (FCT'09), Wroclaw, Poland.

Селиванов В.Л. (16.09.09 – 08.10.09) – научный визит в Университет Зигена, Германия и Исследовательский центр им. К. Гёделя, Австрия.

Селиванов В.Л. (27.11.09 – 19.12.09) – научный визит в Университет Бундесвера, Мюнхен, Германия, в рамках гранта DFG/РФФИ № 09-01-91334-ННИО_а

Селиванов В.Л. (29.06.09 – 25.07.09) – доклады на конференциях «Развитие в теории языков» (Штутгарт), «Вычислимость в Европе» (Хайдельберг) и «Непрерывность, сложность, конструктивность» (Кёльн).

Тарасюк И.В. (27.09-2.10.2009) – участие в 18th International Workshop “Concurrency, Specification and Programming” (CS&P'09), Krakow-Przegorzaly, Польша.

Шилов Н.В. - с 28.05.09 по 09.06.09 – научный визит в Университет Аахена (Германия)

Шилов Н.В. с 31.05.09 по 06.06.09 -- участие в Весенней школе по теории игр и верификации в Берниторо (Италия).

Малюх В.Н. (16.04.0 – 19.04.09) – участие в конференции COFES-2009, Скоттсдейл, Аризона, США.

Малюх В.Н. (02.12.09 – 05.12.09) – участие в выставке EuroMold-2009, Франкфурт, ФРГ. Презентация продукта «RhinoAssembly».


Членство в национальных и международных научных организациях



Европейская ассоциация искусственного интеллекта – к.т.н. Ю.А.Загорулько,

К.ф.- м.н. О.И.Боровикова.

Российская ассоциация искусственного интеллекта – к.т.н. Ю.А. Загорулько, к.ф.- м.н. О.И.Боровикова

Ассоциация по вычислительной технике (ACM) – к.ф.-м.н. М.А.Бульонков.

Институт инженеров по электронике и электротехнике (IEEE) – к.ф.-м.н. М.А.Бульонков.

Российская академия естественных наук – член-корр. В.Н.Касьянов.

Американское математическое общество (AMS) – проф. В.Н. Касьянов,

проф. В.Л. Селиванов, к.ф.-м.н. Ф.А. Мурзин.

Европейская ассоциация по теоретической информатике (EATCS) –проф. В.Н.Касьянов, к.ф.-м.н. В.А.Непомнящий.

Общество по индустриальной и прикладной математике (SIAM) – проф. В.Н.Касьянов.

Европейская ассоциация по компьютерной логике (EACSL) – к.ф.-м.н.

В.А. Непомнящий.

Международная академия информатизации – академик А.А. Берс.