Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Модели и алгоритмы в биоинформатике (В. А. Любецкий)

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

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

Примеры таких задач.

  1. Даны n натуральных чисел. Можно ли разбить их множество на две части с одинаковыми суммами чисел из каждой части?
  2. Даны два графа a и b и список естественных операций над графами. Какова кратчайшая последовательность этих операций, преобразующая a в b?
  3. Как определить/вычислить расстояние между графами?
  4. Что такое средний граф для данного набора графов?
  5. Описать смену режимов в функционировании динамических систем определённых типов (важных в биологии).

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

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