MUSCLE: метод множественного выравнивания последовательностей с пониженной временной и пространственной сложностью

ВВЕДЕНИЕ: В предыдущей статье мы представили MUSCLE — новую программу для построения множественных выравниваний белковых последовательностей, привели краткое описание алгоритма и показали, что MUSCLE обеспечивает самые высокие из опубликованных на тот момент оценок на четырех тестах точности выравнивания. В настоящей работе мы более подробно рассматриваем алгоритм и описываем несколько ранее не опубликованных методов, повышающих биологическую точность и/или снижающих вычислительную сложность. Мы вводим новую опцию MUSCLE-fast, предназначенную для высокопроизводительных приложений. Кроме того, мы описываем новый протокол оценки целевых функций, используемых для выравнивания двух профилей. РЕЗУЛЬТАТЫ: Мы сравниваем скорость и точность MUSCLE с CLUSTALW, Progressive POA и скриптом FFTNS1 пакета MAFFT — наиболее быстрой из ранее опубликованных программ, известных автору. Точность оценивается с использованием четырех тестов: BAliBASE, PREFAB, SABmark и SMART. Мы исследуем три варианта, обеспечивающие соответственно наивысшую точность (MUSCLE с настройками по умолчанию), наивысшую скорость (MUSCLE-fast) и тщательно выбранный компромисс между ними (MUSCLE-prog). Мы обнаружили, что MUSCLE-fast является самым быстрым алгоритмом на всех наборах тестовых данных, обеспечивая среднюю точность выравнивания, сопоставимую с CLUSTALW, за время, обычно в два–три порядка меньшее. MUSCLE-fast способен выровнять 1 000 последовательностей средней длиной 282 за 21 секунду на современном настольном компьютере. ВЫВОДЫ: MUSCLE предлагает ряд опций, обеспечивающих повышение скорости и/или точности выравнивания по сравнению с доступными в настоящее время программами. MUSCLE доступна бесплатно по адресу http://www.drive5.com/muscle.