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