Введение

Алгоритм определения схожих областей между двумя молекулярными последовательностями

Алгоритм Смита — Уотермана выполняет локальное выравнивание последовательностей, то есть предназначен для определения схожих областей между двумя строками последовательностей нуклеиновых кислот или белков. Вместо анализа всей последовательности, алгоритм Смита — Уотермана сравнивает сегменты всех возможных длин и оптимизирует меру сходства. Алгоритм был впервые предложен Темплом Ф. Смитом и Майклом С. Уотерменом в 1981 году. Как и алгоритм Нидлмена — Вунша, являясь его модификацией, Смита — Уотермана представляет собой алгоритм динамического программирования. Благодаря этому он обладает важным свойством: гарантированно находит оптимальное локальное выравнивание относительно используемой системы оценок (включающей матрицу подстановок и схему штрафов за пробелы). Основное отличие от алгоритма Нидлмена — Вунша заключается в том, что ячейки матрицы с отрицательным баллом приравниваются к нулю, что позволяет выделить локальные выравнивания с положительным баллом. Процедура обратного прохода начинается с ячейки матрицы с наивысшим баллом и продолжается до тех пор, пока не будет достигнута ячейка с нулевым баллом, что и определяет локальное выравнивание с наивысшим баллом. Из-за кубической временной сложности алгоритм часто оказывается непрактичным для решения крупномасштабных задач и заменяется на более эффективные с вычислительной точки зрения альтернативы, такие как (Gotoh, 1982), (Altschul и Erickson, 1986) и (Myers и Miller, 1988).

История

В 1970 году Соул Б. Нидлман и Кристиан Д. Вунш предложили эвристический алгоритм гомологии для выравнивания последовательностей, также известный как алгоритм Нидлмана — Вунша. Это алгоритм глобального выравнивания, требующий вычислительных шагов (где и — длины двух выравниваемых последовательностей). Он использует итеративное вычисление матрицы для определения глобального выравнивания. В последующее десятилетие Санкофф, Райхерт, Бейер и другие разработали альтернативные эвристические алгоритмы для анализа последовательностей генов. Селлерс представил систему измерения расстояний между последовательностями. В 1976 году Уотерман и соавторы добавили понятие штрафов за пробелы в исходную систему измерений. В 1981 году Смит и Уотерман опубликовали свой алгоритм Смита — Уотермана для вычисления локального выравнивания. Алгоритм Смита — Уотермана достаточно требователен к вычислительным ресурсам: для выравнивания двух последовательностей длины и требуется время . Гото применил этот метод, а позднее было показано, как эффективно использовать кэш алгоритма Гото в линейном пространстве, применяя другую рекурсивную стратегию «разделяй и властвуй», чем у Хиршберга. В результате получившийся алгоритм на практике работает быстрее, чем алгоритм Майерса и Миллера, благодаря лучшей производительности кэша. А также векторизация SSE2, разработанная Фарраром, сделала поиск в базах данных оптимальных последовательностей белков вполне практичным. Библиотека SSW расширяет реализацию Фаррара, возвращая информацию о выравнивании в дополнение к оптимальному результату Смита — Уотермана.

ФПГА

Крей продемонстрировал ускорение алгоритма Смита-Уотермана с использованием реконфигурируемой вычислительной платформы на основе чипов FPGA, при этом результаты показали ускорение до 28 раз по сравнению со стандартными микропроцессорными решениями. Другая версия алгоритма Смита-Уотермана на основе FPGA демонстрирует ускорение до 100x на FPGA (Virtex 4) по сравнению с процессором Opteron 2,2 ГГц. Системы TimeLogic DeCypher и CodeQuest также ускоряют алгоритмы Смита-Уотермана и Framesearch, используя карты PCIe FPGA. В магистерской диссертации 2011 года был проведен анализ ускорения Смита-Уотермана на основе FPGA. В публикации 2016 года представлена высокоэффективная реализация, в которой код OpenCL, скомпилированный с помощью Xilinx SDAccel, ускоряет секвенирование генома, превосходя производительность CPU/GPU на единицу мощности в 12,21 раза. При использовании одной карты PCIe FPGA, оснащенной FPGA Xilinx Virtex 7 2000T, производительность на ватт была в 12,21 раза выше, чем у CPU/GPU.

ГПУ

Национальная лаборатория Лоуренса Ливермора и Объединенный институт генома Министерства энергетики США реализовали ускоренную версию поиска локального выравнивания последовательностей по алгоритму Смита-Ватермана с использованием графических процессоров (GPU). Предварительные результаты показали двукратное увеличение скорости по сравнению с программными реализациями. Аналогичный метод уже используется в программном обеспечении Biofacet с 1997 года с тем же коэффициентом ускорения. Также доступно несколько GPU-реализаций алгоритма на платформе CUDA C от NVIDIA. При сравнении с лучшей известной CPU-реализацией (использующей SIMD-инструкции на архитектуре x86) от Farrar, тесты производительности данного решения с использованием одной видеокарты NVidia GeForce 8800 GTX показали незначительное увеличение производительности для коротких последовательностей, но незначительное снижение – для длинных. Однако те же тесты, выполненные на двух видеокартах NVidia GeForce 8800 GTX, оказались почти в два раза быстрее реализации Farrar для всех протестированных размеров последовательностей. Сейчас доступна новая GPU CUDA-реализация алгоритма Смита-Ватермана, которая быстрее предыдущих версий и также снимает ограничения на длину запросов. См. CUDASW++. Сообщается об одиннадцати различных реализациях алгоритма Смита-Ватермана на CUDA, три из которых демонстрируют ускорение в 30 раз.

SIMD

В 2000 году в публикации Рогнеса и Сиберга была описана быстрая реализация алгоритма Смита-Уотермана с использованием технологии SIMD (single instruction, multiple data), доступной в процессорах Intel Pentium MMX и аналогичных технологиях. В отличие от подхода Возняка (1997), новая реализация основывалась на векторах, параллельных последовательности запроса, а не на диагональных векторах. Компания Sencel Bioinformatics подала заявку на патент, охватывающий этот подход. Sencel продолжает разрабатывать программное обеспечение и предоставляет исполняемые файлы для академического использования бесплатно. В настоящее время доступна SSE2-векторизация алгоритма (Farrar, 2007), обеспечивающая ускорение в 8–16 раз на процессорах Intel/AMD с расширениями SSE2, распространяемая по лицензии GNU Affero General Public License. Параллельно данное программное обеспечение сравнивает аминокислотные остатки из шестнадцати различных последовательностей базы данных с одним остатком запроса. При использовании запроса длиной в 375 остатков на двухпроцессорной системе Intel Xeon X5650 с шестью ядрами была достигнута скорость 106 миллиардов обновлений ячеек в секунду (GCUPS), что более чем в шесть раз превышает скорость программного обеспечения, основанного на "полосатом" подходе Farrar. Оно быстрее, чем BLAST при использовании матрицы BLOSUM50. Реализация Смита-Уотермана под названием diagonalsw, написанная на C и C++, использует наборы инструкций SIMD (SSE4.1 для платформы x86 и AltiVec для платформы PowerPC) и распространяется под лицензией MIT с открытым исходным кодом.

Мотор для сотовой широкополосной связи

В 2008 году Фаррар описал реализацию алгоритма Striped Smith–Waterman для Cell Broadband Engine и сообщил о достижении производительности 32 и 12 GCUPS на IBM QS20 и Sony PlayStation 3 соответственно.

Ограничения

Быстрый рост объемов генетических данных ставит под сомнение скорость работы современных алгоритмов выравнивания последовательностей ДНК. Насущная необходимость в эффективном и точном методе выявления вариантов ДНК требует инновационных подходов к параллельной обработке данных в реальном времени.