Комбинаторика и теория графов в биоинформатике

Мотивация

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

Актуальность и цели

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

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

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

Первая статья и международная конференция

По результатам исследования была написана статья, которую было решено послать ее на конференцию RECOMB Comparative Genomics 2012, которая проходила с 17 по 19 октября 2012 года в городе Нитерои, Бразилии. К моей большой радости статья была принята! Благодаря моему научному руководителю, который поверил в мою способность публичных выступлений, чести делать доклад перед аудиторией на международной конференции удостоился я, студент 4-ого курса ИТМО, и по совместительству студент 2-ого года CS Center-а.

Подготовка доклада заняла довольно много времени, но когда все было готово, оставалось решить только материальный вопрос, связанный с этой поездкой. Благодаря финансовой помощи Лаборатории алгоритмической биологии, и этот вопрос был успешно закрыт, и уже 18 числа, в Бразилии, был сделан успешный доклад по результатам, практически годовой научно-исследовательской работы.

Благодарность

Последним по списку, но далеко не по важности, стоит отметить, что CS Center предоставил возможность студенту без какой-либо степени (бакалавр/магистр/кан. наук) провести исследовании интересных проблем в актуальной области науки; а профессиональная и материальная поддержка Лаборатории алгоритмической биологии обеспечила возможность поездки на международную конференцию и проведение доклада перед ведущими учеными в данной области биоинформатики. Такая совокупность обстоятельств вызывала неустанное уважение по отношению к этим двум организациям со стороны всех, кто слышал этот рассказ на RECOMB Comparative Genomics 2012, а также желание организовывать подобные инициативы в самых разных лабораториях и университетах в мире.