Геномные перестройки: от биологических задач к комбинаторным алгоритмам (и обратно)

Недавние исследования геномов показывают, что некоторые классические теории в биологии могут быть неполными или даже неверными.
Я опишу три спорных и вызывающих жаркие дискуссии темы: Whole Genome Duplications (удвоение генома), Random Breakage Model of Chromosome Evolution (модель случайного разрезания хромосом в ходе эволюции), и Mammalian Phylogenomics (Phylogenomics млекопитающих) и три связанные с ними открытые алгоритмические проблемы: Genome Halving Problem (задача деления генома), Breakpoint Re-Use Problem (задача повторного использования точек разрезания), и Ancestral Genome Reconstruction Problem (задача реконструкции геномов вымерших животных).
Далее я опишу “Multi-Break Rearrangements” (“перестройки со многими разрывами”) — комбинаторную конструкцию для анализа тех биологических задач, которые привели к эффективному алгоритмическому решению и обеспечили новое понимание эволюции хромосом. Мы используем эти алгоритмические результаты для того, чтобы обнаружить небольшие участки генома человека, где разрезы хромосом происходили снова и снова, много раз в ходе эволюции. Кроме того, мы продемонстрируем, как это недавнее открытие позволяет предсказать то, каким образом геном человека может изменяться в будущем.
Доклад основан на совместной работе с Максимом Алексеевым.