| RUS ENG |
| Полная версия |
|
|
|
| СЕМИНАРЫ |
|
Межкафедральный семинар МФТИ по дискретной математике
|
|||
|
|
|||
|
Задачи теории графов в сравнительной геномике Н. В. Алексеев |
|||
|
Аннотация: В докладе мы обсудим задачи, которые необходимо решить для определения эволюционного расстояния между геномами различных видов. Под эволюционным расстоянием понимается количество произошедших геномных перестроек - эволюционных событий, которые меняют архитектуру Я расскажу о методах определения минимального количества перестроек, необходимого для трансформации одного генома в другой. Эти методы основанны на изучении структуры так называемого брейкпоинт графа. Мы также рассмотрим вероятностные оценки эволюционного расстояния, базирующиеся на модели случайных графов Эрдеша-Реньи. Кроме того, мы обсудим возникающие в данном контексте задачи перечислительной комбинаторики, например, сколько существует геномов на заданном эволюционном расстоянии от данного. Если позволит время, мы обсудим задачи, связанные с геномами, в которых некоторые гены представлены в нескольких копиях (что часто встречается, например, у растений). В таких случаях задачи об определении расстояния могут быть сформулированы как задачи о трансформации вложенных графов, и решены методами целочисленного программирования. |
|||