Быстрый алгоритм бутстрепа для веб-серверов RAxML

Несмотря на недавние достижения, обусловленные применением методов высокопроизводительных вычислений и новых алгоритмических подходов в программах вывода на основе метода максимального правдоподобия (ML), основным вычислительным узким местом по-прежнему остается вычисление значений бутстреп-поддержки. Проведение, вероятно, недостаточного числа из 100 бутстреп-анализов (BS) с использованием современных программ ML на больших наборах данных — как по числу таксонов, так и по числу пар оснований — может легко потребовать месяца вычислений. Поэтому мы разработали, реализовали и тщательно протестировали быстрые эвристические методы бутстрепа в RAxML (Randomized Axelerated Maximum Likelihood), которые более чем на порядок превосходят по скорости современные алгоритмы. Эти новые эвристические методы способны устранить вычислительное узкое место и усовершенствовать современную методологию филогенетического анализа. Вычислительные эксперименты по оценке производительности и относительной точности этих эвристик были проведены на 22 разнообразных реальных выравниваниях ДНК и аминокислотных последовательностей (AA), включавших отдельные гены и наборы генов и содержащих от 125 до 7764 последовательностей. Значения стандартного BS (SBS) и быстрого BS (RBS), рассчитанные на дереве максимального правдоподобия с наилучшим показателем, имели высокую корреляцию и почти идентичные средние значения поддержки. Взвешенное расстояние RF (Robinson–Foulds) между консенсусными деревьями, основанными на SBS и RBS, во всех случаях было менее 6% (в среднем 4%). Что еще важнее, выводы RBS выполнялись в 8–20 раз быстрее (в среднем в 14,73 раза), чем анализы SBS в RAxML, и в 18–495 раз быстрее, чем анализы BS в конкурирующих программах, таких как PHYML или GARLI. Кроме того, это преимущество в производительности увеличивалось с размером выравнивания. Наконец, мы создали два свободно доступных веб-сервера для этой значительно усовершенствованной версии RAxML, обеспечивающих доступ к кластеру Vital-IT из 200 процессоров Швейцарского института биоинформатики и к кластеру проекта CIPRES из 128 процессоров в San Diego Supercomputer Center. Эти веб-серверы предоставляют возможность проводить la…