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

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