Алгоритм Смита-Уотермана

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

Алгоритм Смита-Уотермана выполняет локальное выравнивание последовательностей , то есть для определения схожих областей между двумя строками последовательностей нуклеиновых кислот или последовательностей белков . Вместо того, чтобы рассматривать всю последовательность, алгоритм Смита-Уотермана сравнивает сегменты всех возможных длин и оптимизирует меру сходства .

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

История

В 1970 году Сол Б. Нидлман и Кристиан Д. Вунш предложили эвристический алгоритм гомологии для выравнивания последовательностей, также называемый алгоритмом Нидлмана–Вунша. ^[5] Это алгоритм глобального выравнивания, который требует шагов расчета ( и являются длинами двух выравниваемых последовательностей). Он использует итерационный расчет матрицы для демонстрации глобального выравнивания. В следующем десятилетии Санкофф, ^[6] Райхерт, ^[7] Бейер ^[8] и другие сформулировали альтернативные эвристические алгоритмы для анализа последовательностей генов. Селлерс представил систему для измерения расстояний последовательностей. ^[9] В 1976 году Уотерман и др. добавили концепцию пробелов в исходную систему измерения. ^[10] В 1981 году Смит и Уотерман опубликовали свой алгоритм Смита–Уотермана для расчета локального выравнивания. ${\displaystyle O(mn)}$ ${\displaystyle m}$ ${\displaystyle n}$

Алгоритм Смита-Уотермана довольно требователен к времени: для выравнивания двух последовательностей длиной и требуется время. Гото [ ^2] и Альтшул ^[3] оптимизировали алгоритм до шагов. Сложность пространства была оптимизирована Майерсом и Миллером ^[4] от до (линейно), где — длина более короткой последовательности, для случая, когда требуется только одно из многих возможных оптимальных выравниваний. Позже Чоудхури, Ле и Рамачандран ^[11] оптимизировали производительность кэша алгоритма, сохраняя линейное использование пространства по общей длине входных последовательностей. ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle O(m^{2}n+n^{2}m)}$ ${\displaystyle O(mn)}$ ${\displaystyle O(mn)}$ ${\displaystyle O(n)}$ ${\displaystyle n}$

Мотивация

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

Одной из причин локального выравнивания является сложность получения правильных выравниваний в регионах с низким сходством между отдаленно связанными биологическими последовательностями, поскольку мутации добавили слишком много «шума» за эволюционное время, чтобы позволить провести осмысленное сравнение этих регионов. Локальное выравнивание полностью избегает таких регионов и фокусируется на тех, у которых положительный балл, т. е. на тех, у которых эволюционно сохранен сигнал сходства. Предпосылкой для локального выравнивания является отрицательный балл ожидания. Балл ожидания определяется как средний балл, который система подсчета ( матрица подстановки и штрафы за пропуски ) дала бы для случайной последовательности.

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

Алгоритм

Метод оценки алгоритма Смита-Уотермана

Пусть и — последовательности, которые необходимо выровнять, где и — длины и соответственно. ${\displaystyle A=a_{1}a_{2}...a_{n}}$ ${\displaystyle B=b_{1}b_{2}...b_{m}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle B}$

1. Определите матрицу подстановки и схему штрафа за пропуски.
   • ${\displaystyle s(a,b)}$- Оценка сходства элементов, составляющих две последовательности
   • ${\displaystyle W_{k}}$- Штраф за разрыв, имеющий длину ${\displaystyle k}$
2. Построить матрицу оценок и инициализировать ее первую строку и первый столбец. Размер матрицы оценок равен . Матрица использует индексацию, начинающуюся с 0. ${\displaystyle H}$ ${\displaystyle (n+1)*(m+1)}$

   ${\displaystyle H_{k0}=H_{0l}=0\quad for\quad 0\leq k\leq n\quad and\quad 0\leq l\leq m}$

3. Заполните матрицу оценок, используя приведенное ниже уравнение.

   ${\displaystyle H_{ij}=\max {\begin{cases}H_{i-1,j-1}+s(a_{i},b_{j}),\\\max _{k\geq 1}\{H_{i-k,j}-W_{k}\},\\\max _{l\geq 1}\{H_{i,j-l}-W_{l}\},\\0\end{cases}}\qquad (1\leq i\leq n,1\leq j\leq m)}$

   где

   ${\displaystyle H_{i-1,j-1}+s(a_{i},b_{j})}$это оценка выравнивания и , ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$

   ${\displaystyle H_{i-k,j}-W_{k}}$это оценка, если находится в конце промежутка длины , ${\displaystyle a_{i}}$ ${\displaystyle k}$

   ${\displaystyle H_{i,j-l}-W_{l}}$это оценка, если находится в конце промежутка длины , ${\displaystyle b_{j}}$ ${\displaystyle l}$

   ${\displaystyle 0}$означает, что нет никакого сходства вплоть до и . ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$

4. Traceback. Начиная с наивысшего балла в матрице оценок и заканчивая ячейкой матрицы, имеющей балл 0, трассировка выполняется рекурсивно на основе источника каждого балла для генерации наилучшего локального выравнивания. ${\displaystyle H}$

Объяснение

Алгоритм Смита-Уотермана выравнивает две последовательности по совпадениям/несовпадениям (также известным как замены), вставкам и удалениям. Как вставки, так и удаления являются операциями, которые вводят пробелы, которые представлены тире. Алгоритм Смита-Уотермана состоит из нескольких шагов:

1. Определите матрицу замены и схему штрафа за пропуск . Матрица замены присваивает каждой паре оснований или аминокислот оценку за совпадение или несовпадение. Обычно совпадения получают положительные оценки, тогда как несовпадения получают относительно более низкие оценки. Функция штрафа за пропуск определяет стоимость оценки за открытие или расширение пропусков. Пользователям предлагается выбрать подходящую систему подсчета очков на основе целей. Кроме того, также полезно попробовать различные комбинации матриц замены и штрафов за пропуски.
2. Инициализируйте матрицу подсчета очков . Размеры матрицы подсчета очков равны 1+длина каждой последовательности соответственно. Все элементы первой строки и первого столбца установлены в 0. Дополнительная первая строка и первый столбец позволяют выровнять одну последовательность с другой в любой позиции, а установка их в 0 делает конечный зазор свободным от штрафа.
3. Подсчет очков . Оцените каждый элемент слева направо, сверху вниз в матрице, учитывая результаты замен (диагональные оценки) или добавления пробелов (горизонтальные и вертикальные оценки). Если ни одна из оценок не является положительной, этот элемент получает 0. В противном случае используется наивысшая оценка, и источник этой оценки записывается.
4. Traceback . Начиная с элемента с наивысшим баллом, трассировка на основе источника каждого балла рекурсивно, пока не встретится 0. В этом процессе генерируются сегменты, имеющие наивысший балл сходства на основе заданной системы оценок. Чтобы получить второе лучшее локальное выравнивание, примените процесс трассировки, начиная со второго самого высокого балла за пределами следа наилучшего выравнивания.

Сравнение с алгоритмом Нидлмана–Вунша

Глобальное и локальное выравнивание последовательностей

Алгоритм Смита-Уотермана находит сегменты в двух последовательностях, которые имеют сходства, в то время как алгоритм Нидлмана-Вунша выравнивает две полные последовательности. Таким образом, они служат разным целям. Оба алгоритма используют концепции матрицы подстановки, функции штрафа за пробел, матрицы подсчета очков и процесса трассировки. Три основных различия:

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

Начальная матрица оценок алгоритма Смита–Уотермана позволяет выравнивать любой сегмент одной последовательности в произвольное положение в другой последовательности. Однако в алгоритме Нидлмана–Вунша штраф за конечный зазор также необходимо учитывать для выравнивания полных последовательностей.

Матрица замещения

Каждой замене основания или аминокислоты присваивается оценка. В общем случае совпадениям присваиваются положительные оценки, а несовпадениям присваиваются относительно более низкие оценки. Возьмем в качестве примера последовательность ДНК. Если совпадения получают +1, несовпадения получают -1, то матрица замен имеет вид:

Эту матрицу замещения можно описать следующим образом: ${\displaystyle s(a_{i},b_{j})={\begin{cases}+1,\quad a_{i}=b_{j}\\-1,\quad a_{i}\neq b_{j}\end{cases}}}$

Различные замены оснований или замены аминокислот могут иметь разные оценки. Матрица замены аминокислот обычно сложнее, чем у оснований. См. PAM , BLOSUM .

Штраф за разрыв

Штраф за пробел обозначает баллы за вставку или удаление. Простая стратегия штрафа за пробел заключается в использовании фиксированного балла для каждого пробела. Однако в биологии баллы необходимо подсчитывать по-разному по практическим причинам. С одной стороны, частичное сходство между двумя последовательностями является обычным явлением; с другой стороны, одно событие мутации гена может привести к вставке одного длинного пробела. Поэтому соединенные пробелы, образующие длинный пробел, обычно более предпочтительны, чем несколько разбросанных коротких пробелов. Чтобы учесть это различие, в систему подсчета баллов были добавлены концепции открытия пробела и расширения пробела. Балл за открытие пробела обычно выше, чем балл за расширение пробела. Например, параметры по умолчанию в EMBOSS Water следующие: открытие пробела = 10, расширение пробела = 0,5.

Здесь мы обсудим две общие стратегии для штрафа за пробел. Смотрите штраф за пробел для дополнительных стратегий. Пусть будет функцией штрафа за пробел для пробела длиной : ${\displaystyle W_{k}}$ ${\displaystyle k}$

Линейный

Упрощенный алгоритм Смита-Уотермана с использованием линейной функции штрафа за зазор

Линейный штраф за разрыв имеет одинаковые баллы за открытие и расширение разрыва:

${\displaystyle W_{k}=kW_{1}}$,

где - стоимость одного зазора. ${\displaystyle W_{1}}$

Штраф за зазор прямо пропорционален длине зазора. При использовании линейного штрафа за зазор алгоритм Смита-Уотермана можно упростить до:

${\displaystyle H_{ij}=\max {\begin{cases}H_{i-1,j-1}+s(a_{i},b_{j}),\\H_{i-1,j}-W_{1},\\H_{i,j-1}-W_{1},\\0\end{cases}}}$

Упрощенный алгоритм использует шаги. Когда элемент оценивается, необходимо учитывать только штрафы за пробелы от элементов, которые непосредственно примыкают к этому элементу. ${\displaystyle O(mn)}$

Аффинный

Аффинный штраф за разрыв учитывает открытие и расширение разрыва по отдельности:

${\displaystyle W_{k}=uk+v\quad (u>0,v>0)}$,

где — штраф за открытие разрыва, а — штраф за расширение разрыва. Например, штраф за разрыв длиной 2 равен . ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle 2u+v}$

В оригинальной статье по алгоритму Смита-Уотермана использовался произвольный штраф за зазор. Он использует шаги, поэтому требует много времени. Гото оптимизировал шаги для аффинного штрафа за зазор до , ^[2] но оптимизированный алгоритм пытается найти только одно оптимальное выравнивание, и оптимальное выравнивание не гарантируется. ^[3] Альтшуль модифицировал алгоритм Гото, чтобы найти все оптимальные выравнивания, сохраняя при этом вычислительную сложность. ^[3] Позже Майерс и Миллер указали, что алгоритм Гото и Альтшуля можно дополнительно модифицировать на основе метода, опубликованного Хиршбергом в 1975 году, ^[12] и применили этот метод. ^[4] Алгоритм Майерса и Миллера может выровнять две последовательности, используя пространство, причем длина более короткой последовательности будет равна длине более короткой последовательности. Позже Чоудхури, Ле и Рамачандран ^[11] показали, как запустить алгоритм Гото с эффективностью кэширования в линейном пространстве, используя другую рекурсивную стратегию «разделяй и властвуй», чем та, которую использовал Хиршберг. Полученный алгоритм на практике работает быстрее, чем алгоритм Майерса и Миллера, благодаря более высокой производительности кэша. ^[11] ${\displaystyle O(m^{2}n)}$ ${\displaystyle O(mn)}$ ${\displaystyle O(n)}$ ${\displaystyle n}$

Пример штрафа за пробел

Возьмем в качестве примера выравнивание последовательностей TACGGGCCCGCTAC и TAGCCCTATCGGTCA . При использовании линейной функции штрафа за пробелы результат будет следующим (Выравнивания выполнены EMBOSS Water. Матрица подстановки DNAfull (оценка сходства: +5 для совпадающих символов, в противном случае -4). Открытие и расширение пробела равны 0,0 и 1,0 соответственно):

TACGGGCCCGCTA-CTA---G-CC-CTATC

При использовании аффинного штрафа за зазор результат будет следующим (открытие и расширение зазора равны 5,0 и 1,0 соответственно):

TACGGGCCCGCTATA---GCC--CTA

Этот пример показывает, что аффинный штраф за зазоры может помочь избежать разрозненных небольших зазоров.

Матрица оценок

Функция матрицы оценок заключается в проведении сравнений один к одному между всеми компонентами в двух последовательностях и записи результатов оптимального выравнивания. Процесс оценки отражает концепцию динамического программирования. Окончательное оптимальное выравнивание находится путем итеративного расширения растущего оптимального выравнивания. Другими словами, текущее оптимальное выравнивание генерируется путем решения того, какой путь (совпадение/несовпадение или вставка пробела) дает наивысшую оценку по сравнению с предыдущим оптимальным выравниванием. Размер матрицы равен длине одной последовательности плюс 1 на длину другой последовательности плюс 1. Дополнительная первая строка и первый столбец служат для выравнивания одной последовательности с любыми позициями в другой последовательности. И первая строка, и первый столбец устанавливаются на 0, чтобы конечный пробел не штрафовался. Первоначальная матрица оценок имеет вид:

Пример

Возьмем в качестве примера выравнивание последовательностей ДНК TGTTACGG и GGTTGACTA . Используйте следующую схему:

• Матрица замещения: ${\displaystyle s(a_{i},b_{j})={\begin{cases}+3,\quad a_{i}=b_{j}\\-3,\quad a_{i}\neq b_{j}\end{cases}}}$
• Штраф за зазор: (линейный штраф за зазор ) ${\displaystyle W_{k}=2k}$ ${\displaystyle W_{1}=2}$

Инициализируйте и заполните матрицу подсчета очков, как показано ниже. На этом рисунке показан процесс подсчета очков первых трех элементов. Желтый цвет обозначает рассматриваемые основания. Красный цвет обозначает максимально возможный балл для оцениваемой ячейки.

Инициализация матрицы оценок (слева 1) и процесс оценки первых трех элементов (слева 2–4)

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

Результат выравнивания:

GTT - AC GTTGAC 

Выполнение

Реализация алгоритма Смита-Уотермана, SSEARCH, доступна в пакете анализа последовательностей FASTA из UVA FASTA Downloads. Эта реализация включает ускоренный код Altivec для процессоров PowerPC G4 и G5, который ускоряет сравнение в 10–20 раз, используя модификацию подхода Возняка, 1997, ^[13] и векторизацию SSE2, разработанную Фарраром ^{[14], что делает поиск оптимальной} базы данных последовательностей белков вполне практичным. Библиотека, SSW, расширяет реализацию Фаррара, чтобы возвращать информацию о выравнивании в дополнение к оптимальной оценке Смита-Уотермана. ^[15]

Ускоренные версии

ПЛИС

Cray продемонстрировал ускорение алгоритма Смита-Уотермана с использованием реконфигурируемой вычислительной платформы на основе чипов FPGA , с результатами, показывающими до 28-кратного ускорения по сравнению со стандартными решениями на основе микропроцессоров. Другая версия алгоритма Смита-Уотермана на основе FPGA показывает ускорение FPGA (Virtex-4) до 100 раз ^[16] по сравнению с процессором Opteron 2,2 ГГц. ^[17] Системы TimeLogic DeCypher и CodeQuest также ускоряют Smith-Waterman и Framesearch с использованием карт PCIe FPGA.

Магистерская диссертация 2011 года ^[18] включает анализ ускорения Смита-Уотермана на базе ПЛИС.

В публикации 2016 года OpenCL-код, скомпилированный с помощью Xilinx SDAccel, ускоряет геномное секвенирование, превосходит производительность CPU/GPU/Вт в 12-21 раз, была представлена ​​очень эффективная реализация. При использовании одной карты PCIe FPGA, оснащенной Xilinx Virtex-7 2000T FPGA, уровень производительности на ватт был лучше, чем CPU/GPU в 12-21 раз.

ГПУ

Национальная лаборатория Лоуренса в Ливерморе и Объединенный институт генома Министерства энергетики США реализовали ускоренную версию локального поиска выравнивания последовательностей Смита-Уотермана с использованием графических процессоров (GPU) с предварительными результатами, показывающими 2-кратное ускорение по сравнению с программными реализациями. ^[19] Подобный метод уже был реализован в программном обеспечении Biofacet с 1997 года с тем же коэффициентом ускорения. ^[20]

Также доступны несколько реализаций алгоритма на GPU в платформе CUDA C от NVIDIA . ^[21] По сравнению с самой известной реализацией на CPU (использующей инструкции SIMD на архитектуре x86) от Farrar, тесты производительности этого решения с использованием одной карты NVidia GeForce 8800 GTX показывают небольшое увеличение производительности для меньших последовательностей, но небольшое снижение производительности для больших. Однако те же тесты, запущенные на двух картах NVidia GeForce 8800 GTX, почти в два раза быстрее, чем реализация Farrar для всех протестированных размеров последовательностей.

Теперь доступна более новая реализация SW на GPU CUDA, которая быстрее предыдущих версий, а также снимает ограничения на длину запросов. См. CUDASW++.

Было сообщено об одиннадцати различных реализациях ПО на базе CUDA, три из которых сообщают об ускорении в 30 раз. ^[22]

Наконец, другие реализации алгоритма Смита-Уотермана с ускорением на GPU можно найти в NVIDIA Parabricks , программном пакете NVIDIA для анализа генома. ^[23]

SIMD

В 2000 году быстрая реализация алгоритма Смита-Уотермана с использованием технологии SIMD (одна инструкция, несколько данных ) , доступной в процессорах Intel Pentium MMX и аналогичной технологии, была описана в публикации Рогнеса и Сиберга. ^[24] В отличие от подхода Возняка (1997), новая реализация была основана на векторах, параллельных последовательности запросов, а не на диагональных векторах. Компания Sencel Bioinformatics подала заявку на патент, охватывающий этот подход. Sencel продолжает развивать программное обеспечение и предоставляет исполняемые файлы для академического использования бесплатно.

Векторизация алгоритма SSE2 (Farrar, 2007) теперь доступна, обеспечивая 8-16-кратное ускорение на процессорах Intel/AMD с расширениями SSE2. ^[14] При запуске на процессоре Intel с использованием микроархитектуры Core реализация SSE2 достигает 20-кратного увеличения. Реализация SSE2 Фаррара доступна как программа SSEARCH в пакете сравнения последовательностей FASTA . SSEARCH включена в набор программ поиска сходства Европейского института биоинформатики .

Датская биоинформатическая компания CLC bio достигла ускорения почти в 200 раз по сравнению со стандартными программными реализациями с SSE2 на процессоре Intel Core 2 Duo с тактовой частотой 2,17 ГГц, согласно общедоступному документу.

Ускоренная версия алгоритма Смита-Уотермана на серверах Linux на базе Intel и Advanced Micro Devices (AMD) поддерживается пакетом GenCore 6, предлагаемым Biocceleration. Тесты производительности этого программного пакета показывают ускорение скорости до 10 раз по сравнению со стандартной реализацией программного обеспечения на том же процессоре.

В настоящее время CLC bio является единственной компанией в области биоинформатики, предлагающей решения как SSE, так и FPGA, ускоряющие алгоритм Смита-Уотермана. Компания достигла ускорения более чем в 110 раз по сравнению со стандартными программными реализациями с помощью CLC Bioinformatics Cube. ^{[ необходима цитата ]}

Самую быструю реализацию алгоритма на процессорах с SSSE3 можно найти в программном обеспечении SWIPE (Rognes, 2011), ^[25] , которое доступно по лицензии GNU Affero General Public License . Параллельно это программное обеспечение сравнивает остатки из шестнадцати различных последовательностей базы данных с одним остатком запроса. Используя последовательность запроса из 375 остатков, была достигнута скорость 106 миллиардов обновлений ячеек в секунду (GCUPS) на двухъядерной процессорной системе Intel Xeon X5650, что более чем в шесть раз быстрее, чем программное обеспечение, основанное на «полосатом» подходе Фаррара. Оно быстрее, чем BLAST при использовании матрицы BLOSUM50.

Реализация Smith–Waterman под названием dialogsw на языках C и C++ использует наборы инструкций SIMD ( SSE4.1 для платформы x86 и AltiVec для платформы PowerPC). Она выпущена под лицензией MIT с открытым исходным кодом .

Ячейка широкополосной связи

В 2008 году Фаррар ^[26] описал портирование Striped Smith–Waterman ^[14] на Cell Broadband Engine и сообщил о скоростях 32 и 12 GCUPS на блейд-сервере IBM QS20 и Sony PlayStation 3 соответственно.

Ограничения

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

Смотрите также

• Биоинформатика
• Выравнивание последовательности
• Последовательная добыча
• Алгоритм Нидлмана–Вунша
• Расстояние Левенштейна
• ВЗРЫВ
• ФАСТ

Ссылки

1. Смит, Темпл Ф. и Уотерман, Майкл С. (1981). «Идентификация общих молекулярных подпоследовательностей» (PDF) . Журнал молекулярной биологии . 147 (1): 195–197. CiteSeerX  10.1.1.63.2897 . doi :10.1016/0022-2836(81)90087-5. PMID  7265238.
2. Osamu Gotoh (1982). «Улучшенный алгоритм сопоставления биологических последовательностей». Журнал молекулярной биологии . 162 (3): 705–708. CiteSeerX 10.1.1.204.203 . doi :10.1016/0022-2836(82)90398-9. PMID  7166760. 
3. Стивен Ф. Альтшул и Брюс В. Эриксон (1986). «Оптимальное выравнивание последовательностей с использованием аффинных затрат зазоров». Бюллетень математической биологии . 48 (5–6): 603–616. doi :10.1007/BF02462326. PMID  3580642. S2CID  189889143.
4. Миллер, Уэбб; Майерс, Юджин (1988). «Оптимальные выравнивания в линейном пространстве». Биоинформатика . 4 (1): 11–17. CiteSeerX 10.1.1.107.6989 . doi :10.1093/bioinformatics/4.1.11. PMID  3382986. 
5. Сол Б. Нидлман; Кристиан Д. Вунш (1970). «Общий метод, применимый к поиску сходств в аминокислотной последовательности двух белков». Журнал молекулярной биологии . 48 (3): 443–453. doi :10.1016/0022-2836(70)90057-4. PMID  5420325.
6. Санкофф Д. (1972). «Сопоставление последовательностей при ограничениях удаления/вставки». Труды Национальной академии наук Соединенных Штатов Америки . 69 (1): 4–6. Bibcode : 1972PNAS...69....4S. doi : 10.1073/pnas.69.1.4 . PMC 427531. PMID  4500555. 
7. Томас А. Райхерт; Дональд Н. Коэн; Эндрю К. С. Вонг (1973). «Применение теории информации к генетическим мутациям и сопоставлению полипептидных последовательностей». Журнал теоретической биологии . 42 (2): 245–261. Bibcode : 1973JThBi..42..245R. doi : 10.1016/0022-5193(73)90088-X. PMID  4762954.
8. Уильям А. Бейер, Майрон Л. Стайн, Темпл Ф. Смит и Станислав М. Улам (1974). «Молекулярная метрика последовательности и эволюционные деревья». Mathematical Biosciences . 19 (1–2): 9–25. doi :10.1016/0025-5564(74)90028-5.{{cite journal}}: CS1 maint: multiple names: authors list (link)
9. Питер Х. Селлерс (1974). «О теории и вычислении эволюционных расстояний». Журнал SIAM по прикладной математике . 26 (4): 787–793. doi :10.1137/0126070.
10. MS Waterman; TF Smith; WA Beyer (1976). «Некоторые метрики биологической последовательности». Advances in Mathematics . 20 (3): 367–387. doi : 10.1016/0001-8708(76)90202-4 .
11. Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (июль 2010 г.). «Динамическое программирование без учета кэша для биоинформатики». IEEE/ACM Transactions on Computational Biology and Bioinformatics . 7 (3): 495–510. doi :10.1109/TCBB.2008.94. PMID  20671320. S2CID  2532039.
12. DS Hirschberg (1975). "Линейный пространственный алгоритм для вычисления максимальных общих подпоследовательностей". Сообщения ACM . 18 (6): 341–343. CiteSeerX 10.1.1.348.4774 . doi :10.1145/360825.360861. S2CID  207694727. 
13. Возняк, Анджей (1997). «Использование видеоориентированных инструкций для ускорения сравнения последовательностей». Computer Applications in the Biosciences . 13 (2): 145–50. doi : 10.1093/bioinformatics/13.2.145 . PMID  9146961.
14. Farrar, Michael S. (2007). «Полосатый Smith–Waterman ускоряет поиск в базе данных в шесть раз по сравнению с другими реализациями SIMD». Биоинформатика . 23 (2): 156–161. doi : 10.1093/bioinformatics/btl582 . PMID  17110365.
15. Чжао, Мэнъяо; Ли, Вань-Пин; Гаррисон, Эрик П; Март, Габор Т (4 декабря 2013 г.). "Библиотека SSW: библиотека SIMD Smith-Waterman C/C++ для использования в геномных приложениях". PLOS ONE . ​​8 (12): e82138. arXiv : 1208.6350 . Bibcode :2013PLoSO...882138Z. doi : 10.1371/journal.pone.0082138 . PMC 3852983 . PMID  24324759. 
16. FPGA 100x Papers: "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2008-07-05 . Получено 2007-10-17 .{{cite web}}: CS1 maint: archived copy as title (link), "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2008-07-05 . Получено 2007-10-17 .{{cite web}}: CS1 maint: archived copy as title (link), и "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2011-07-20 . Получено 2007-10-17 .{{cite web}}: CS1 maint: archived copy as title (link)
17. Progeniq Pte. Ltd., «Белая книга — Ускорение ресурсоемких приложений в 10–50 раз для устранения узких мест в вычислительных рабочих процессах».
18. Вермий, Эрик (2011). Генетическое выравнивание последовательностей на суперкомпьютерной платформе (PDF) (диссертация на степень магистра наук). Делфтский технический университет. Архивировано из оригинала (PDF) 2011-09-30 . Получено 2011-08-17 .
19. Лю, Ян; Хуан, Уэйн; Джонсон, Джон; Вайдья, Шейла (2006). "GPU Accelerated Smith-Waterman". Computational Science – ICCS 2006. Lecture Notes in Computer Science. Vol. 3994. Springer. pp. 188–195. doi :10.1007/11758549_29. ISBN 978-3-540-34385-1.
20. "Bioinformatics High Throughput Sequence Search and Analysis (white paper)". GenomeQuest. Архивировано из оригинала 13 мая 2008 г. Получено 09.05.2008 .
21. Manavski, Svetlin A. & Valle, Giorgio (2008). «CUDA-совместимые графические карты как эффективные аппаратные ускорители для выравнивания последовательностей Смита–Уотермана». BMC Bioinformatics . 9 (Suppl 2:S10): S10. doi : 10.1186/1471-2105-9-S2-S10 . PMC 2323659 . PMID  18387198. 
22. "CUDA Zone". Nvidia . Получено 2010-02-25 .
23. "NVIDIA Parabricks". NVIDIA . Получено 2024-07-11 .
24. Рогнес, Торбьёрн; Сиберг, Эрлинг (2000). «Шестикратное ускорение поиска в базе данных последовательностей Смита–Уотермана с использованием параллельной обработки на обычных микропроцессорах». Биоинформатика . 16 (8): 699–706. doi : 10.1093/bioinformatics/16.8.699 . PMID  11099256.
25. Рогнес, Торбьёрн (2011). «Быстрый поиск в базе данных Смита–Уотермана с межпоследовательным SIMD-параллелизмом». BMC Bioinformatics . 12 : 221. doi : 10.1186 /1471-2105-12-221 . PMC 3120707. PMID  21631914. 
26. Фаррар, Майкл С. (2008). «Оптимизация Смита–Уотермана для Cell Broadband Engine». Архивировано из оригинала 2012-02-12. {{cite journal}}: Цитировать журнал требует |journal=( помощь )

Внешние ссылки

• JAligner — реализация алгоритма Смита-Уотермана на Java с открытым исходным кодом
• BABA — апплет (с исходниками), наглядно поясняющий алгоритм
• FASTA/SSEARCH — страница услуг на EBI
• Плагин UGENE Smith–Waterman — реализация алгоритма с открытым исходным кодом, совместимая с SSEARCH, с графическим интерфейсом, написанная на C++
• OPAL — библиотека SIMD C/C++ для массового оптимального выравнивания последовательностей
• dialogsw — реализация C/C++ с открытым исходным кодом и наборами инструкций SIMD (в частности, SSE4.1) под лицензией MIT
• SSW — библиотека C++ с открытым исходным кодом, предоставляющая API для реализации SIMD алгоритма Смита-Уотермана по лицензии MIT
• выравнивание мелодической последовательности — реализация javascript для выравнивания мелодической последовательности
• DRAGMAP Порт C++ реализации Illumina DRAGEN FPGA