В предыдущих материалах мы рассказали об открытом инструменте для сравнительного анализа метагеномных данных и обсудили его развитие в контексте еще одного проекта и задачи поиска генов устойчивости к антибиотикам. На этот раз представляем вам другую разработку МНЦ «Компьютерные технологии» Университета ИТМО. Она называется GADMA, подробнее — под катом.

Автор: Екатерина Носкова. Из документации gadma.readthedocs.io
Автор: Екатерина Носкова. Из документации gadma.readthedocs.io

Проблема и решение

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

Genetic Algorithm for Demographic Model Analysis или GADMA от МНЦ «Компьютерные технологии» Университета ИТМО — это новый фреймворк для вывода демографической истории популяций. Он разделяет понятия симулятора и оптимизатора. Пользователь сам выбирает, какой метод стоит использовать для симуляций, а какой — в качестве алгоритма оптимизации. Помимо этого — команда проекта реализовала новый метод оптимизации, основанный на генетическом алгоритме, который снимает ряд ограничений существующих решений.

С помощью GADMA биологи и биоинформатики могут проводить исследования геномов или генетических данных популяций. Еще GADMA можно использовать для других задач оптимизации, находящихся вне сферы популяционной генетики.

Основным алгоритмом оптимизации GADMA является генетический алгоритм — один из наиболее популярных и эффективных эволюционных алгоритмов. Плюс — фреймворк включает реализации алгоритмов локального поиска из классических методов вывода демографических историй. В первой версии GADMA разработчики добавили два симулятора для вычисления схожести между демографической историей, предложенной оптимизацией, и реальными данными.

Что дальше

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

Автор: Екатерина Носкова. Из документации gadma.readthedocs.io
Автор: Екатерина Носкова. Из документации gadma.readthedocs.io

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

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

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


Другие открытые проекты Университета ИТМО:


Комментарии (0)