Алгоритм Смита – Ватермана

редактировать
КлассВыравнивание последовательности
Худший случай производительность O (mn) {\ displaystyle O (mn)}O (mn)
Наихудший случай сложность пространства O (mn) {\ displaystyle O (mn)}O (mn)
Анимированный пример для постепенного отображения шагов. Подробные инструкции см. В здесь.

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

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

Содержание

  • 1 История
  • 2 Мотивация
  • 3 Алгоритм
  • 4 Пояснение
    • 4.1 Сравнение с алгоритмом Нидлмана – Вунша
    • 4.2 Матрица замещения
    • 4.3 Штраф за пропуск
      • 4.3.1 Линейный
      • 4.3.2 Аффинный
      • 4.3.3 Пример штрафа за пропуск
    • 4.4 Матрица оценки
  • 5 Пример
  • 6 Реализация
  • 7 Ускорено версии
    • 7.1 FPGA
    • 7.2 GPU
    • 7.3 SIMD
    • 7.4 Cell Broadband Engine
  • 8 Ограничения
  • 9 См. также
  • 10 Ссылки
  • 11 Внешние ссылки

История

В 1970 году Сол Б. Нидлман и Кристиан Д. Вунш предложили эвристический алгоритм гомологии для выравнивания последовательностей, также известный как алгоритм Нидлмана – Вунша. Это алгоритм глобального выравнивания, для которого требуются шаги вычисления O (mn) {\ displaystyle O (mn)}O (mn) (m {\ displaystyle m}m и n {\ displaystyle n}n - длины двух выравниваемых последовательностей). Он использует итеративное вычисление матрицы для демонстрации глобального выравнивания. В следующем десятилетии Санкофф, Райхерт, Бейер и другие сформулировали альтернативные эвристические алгоритмы для анализа последовательностей генов. Продавцы представили систему измерения расстояний последовательности. В 1976 году Waterman et al. добавили концепцию зазоров в исходную систему измерения. В 1981 году Смит и Уотерман опубликовали свой алгоритм Смита – Уотермана для расчета локального выравнивания.

Алгоритм Смита – Уотермана довольно требователен ко времени: выровнять две последовательности длиной m {\ displaystyle m}m и n {\ displaystyle n}n , O (mn) {\ displaystyle O (mn)}O (mn) требуется время. Гото и Альтшул оптимизировали алгоритм до O (m n) {\ displaystyle O (mn)}O (mn) шагов. Сложность пространства была оптимизирована Майерсом и Миллером с O (mn) {\ displaystyle O (mn)}O (mn) до O (n) {\ displaystyle O (n)}О (п) (линейный), где n {\ displaystyle n}n - длина более короткой последовательности для случая, когда требуется только одно из множества возможных оптимальных выравниваний.

Мотивация

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

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

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

Алгоритм

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

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

  1. Определите матрицу замещения и схему штрафа за пропуск.
    • s (a, b) {\ displaystyle s (a, b)}s (a, b) - Оценка сходства элементов, составляющих две последовательности
    • W k {\ displaystyle W_ {k}}W_ {k} - Штраф за пробел длиной k {\ displaystyle k}к
  2. Построить оценочную матрицу H {\ displaystyle H}H и инициализировать ее первую строку. и первый столбец. Размер оценочной матрицы составляет (n + 1) ∗ (m + 1) {\ displaystyle (n + 1) * (m + 1)}{\ displaystyle (n + 1) * (m + 1)} . В матрице используется индексирование на основе 0.
    ЧАС К 0 знак равно ЧАС 0 L знак равно 0 для 0 ≤ К ≤ n и 0 ≤ l ≤ м {\ Displaystyle H_ {k0} = H_ {0l} = 0 \ quad для \ quad 0 \ leq k \ leq n \ quad и \ quad 0 \ leq l \ leq m}{\ displaystyle H_ {k0} = H_ {0l} = 0 \ quad для \ quad 0 \ leq k \ leq n \ quad и \ quad 0 \ Leq l \ Leq m}
  3. Заполните оценочную матрицу, используя приведенное ниже уравнение.
    H ij = max {H i - 1, j - 1 + s (ai, bj), max k ≥ 1 {H i - k, j - W k}, max l ≥ 1 {H i, j - l - W l}, 0 (1 ≤ i ≤ n, 1 ≤ j ≤ m) {\ displaystyle H_ {ij} = \ max {\ begin {cases} H_ {i-1, j-1} + s (a_ {i}, b_ {j}), \\\ max _ {k \ geq 1} \ {H_ {ik, j} -W_ {k} \}, \\\ max _ {l \ geq 1} \ { H_ {i, jl} -W_ {l} \}, \\ 0 \ end {cases}} \ qquad (1 \ leq i \ leq n, 1 \ leq j \ leq m)}{\ displaystyle H_ {ij} = \ max {\ begin {case} H_ {i-1, j-1} + s (a_ {i}, b_ {j}), \\\ max _ {k \ geq 1 } \ {H_ {ik, j} -W_ {k} \}, \\\ max _ {l \ geq 1} \ {H_ {i, jl} -W_ {l} \}, \\ 0 \ end { случаях}} \ qquad (1 \ Leq я \ Leq N, 1 \ Leq J \ Leq m)}
    где
    H i - 1, j - 1 + s (ai, bj) {\ displaystyle H_ {i-1, j-1} + s (a_ {i}, b_ {j})}{\ displaystyle H_ {i-1, j-1} + s (a_ {i}, b_ {j})} - это оценка выравнивания ai {\ displaystyle a_ {i}}a_ {i} и bj {\ displaystyle b_ {j}}b_ {j} ,
    H i - k, j - W k {\ displaystyle H_ {ik, j} -W_ {k}}{\ displaystyle H_ {ik, j} -W_ {k}} - это оценка, если ai {\ displaystyle a_ {i}}a_ {i} находится в конце промежутка длиной k {\ displaystyle k}к ,
    H i, j - l - W l {\ displaystyle H_ {i, jl} -W_ {l}}{\ displaystyle H_ {i, jl} -W_ {l}} - оценка, если bj {\ displaystyle b_ {j}}b_ {j} находится в конце промежутка длиной l {\ displaystyle l}l ,
    0 {\ displaystyle 0}{\ displaystyle 0} означает, что сходства нет до ai {\ displaystyl e a_ {i}}a_ {i} и b j {\ displaystyle b_ {j}}b_ {j} .
  4. Прослеживание. Начиная с наивысшей оценки в матрице оценок H {\ displaystyle H}H и заканчивая ячейкой матрицы, которая имеет оценку 0, обратная трассировка на основе источника каждой оценки рекурсивно для создания наилучшего локальное выравнивание.

Объяснение

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

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

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

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

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

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

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

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

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

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

AGCT
A1-1-1-1
G-11-1-1
C-1-11-1
T-1-1-11

Эту матрицу подстановки можно описать как: s (ai, bj) = {+ 1, ai = bj - 1, ai ≠ bj {\ displaystyle s (a_ {i}, b_ {j}) = {\ begin {cases} +1, \ quad a_ {i} = b_ { j} \\ - 1, \ quad a_ {i} \ neq b_ {j} \ end {cases}}}{\ 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.

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

Линейный

Упрощенный метод Смита – Уотермана. алгоритм, когда используется функция штрафа за линейный зазор

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

W k = k W 1 {\ displaystyle W_ {k} = kW_ {1}}{\ displaystyle W_ {k} = кВт_ {1}} ,

где W 1 {\ displaystyle W_ {1}}W_1 - стоимость одного пробела.

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

H ij = max {H i - 1, j - 1 + s (ai, bj), H i - 1, j - W 1, H i, j - 1 - W 1, 0 {\ 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 H_ {ij} = \ max {\ begin {case} H_ {i-1, j-1} + s (a_ {i}, b_ {j}), \\ H_ {i-1, j} -W_ {1}, \\ H_ { я, j-1} -W_ {1}, \\ 0 \ end {cases}}}

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

Аффинный

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

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

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

An в исходной статье алгоритма Смита – Уотермана использовался произвольный штраф за пробелы. Он использует O (m 2 n) {\ displaystyle O (m ^ {2} n)}{\ displaystyle O (m ^ {2} n)} шагов, поэтому требует больших затрат времени. Гото оптимизировал шаги для штрафа за аффинный пробел до O (mn) {\ displaystyle O (mn)}O (mn) , но оптимизированный алгоритм пытается найти только одно оптимальное выравнивание, а оптимальное выравнивание не гарантируется. Altschul модифицировал алгоритм Гото для поиска всех оптимальных выравниваний при сохранении вычислительной сложности. Позже Майерс и Миллер указали, что алгоритм Гото и Альтшула может быть дополнительно модифицирован на основе метода, опубликованного Хиршбергом в 1975 году, и применили этот метод. Алгоритм Майерса и Миллера может выровнять две последовательности, используя O (n) {\ displaystyle O (n)}О (п) пробел, где n {\ displaystyle n}n является длина более короткой последовательности.

Пример штрафа за разрыв

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

TACGGGCCCGCTA-C|| | || ||| |TA --- G-CC-CTATC

Если используется штраф за аффинный пробел, результат будет (открытие пробела и расширение равны 5,0 и 1,0 соответственно):

TACGGGCCCGCTA|| ||| |||TA --- GCC - CTA

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

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

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

b1bjbm
0000
a10
ai0
an0

Пример

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

  • Матрица подстановки: s (ai, bj) = {+ 3, ai = bj - 3, ai ≠ bj {\ displaystyle s (a_ {i}, b_ {j}) = {\ begin {cases} +3, \ quad a_ {i} = b_ {j} \\ - 3, \ quad a_ {i} \ neq b_ {j} \ end {cases}}}{\ displaystyle s (a_ {i}, b_ {j}) = {\ begin {cases} +3, \ quad a_ {i} = b_ {j} \\ - 3, \ четырехъядерный a_ {я} \ neq b_ {j} \ end {case}}}
  • Штраф за разрыв: W k = 2 k {\ displaystyle W_ {k} = 2k}{ \ displaystyle W_ {k} = 2k} (штраф за линейный разрыв W 1 = 2 {\ displaystyle W_ {1} = 2}{\ displaystyle W_ {1} = 2} )

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

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

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

Smith-Waterman-Algorithm-Example-Step2.png Smith-Waterman-Algorithm-Example-Step3.png
Завершенная матрица оценок (наивысшая оценка выделена синим)Процесс отслеживания и результат выравнивания

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

G T T - A C| | | | |GTTGAC

Реализация

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

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

FPGA

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

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

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

GPU

Ливерморская национальная лаборатория Лоуренса и Объединенный институт генома Министерства энергетики США (США) реализовали ускоренную версию поиска локального выравнивания последовательностей Смита – Уотермана с использованием графические процессоры (графические процессоры); предварительные результаты показывают двукратное ускорение по сравнению с программными реализациями. Похожий метод уже реализован в программном обеспечении Biofacet с 1997 года с тем же коэффициентом ускорения.

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

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

Сообщалось об одиннадцати различных реализациях программного обеспечения на CUDA, три из которых сообщают об ускорении в 30 раз.

SIMD

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

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

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

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

В настоящее время единственная компания в области биоинформатики, предлагающая решения как SSE, так и FPGA, ускоряющие Smith – Waterman, CLC bio добилась ускорения более чем в 110 раз по сравнению со стандартными программными реализациями с CLC Куб биоинформатики

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

Также существует diagonalsw, реализация алгоритма Смита – Уотермана на языках C и C ++ с наборами инструкций SIMD (SSE4.1 для платформы x86 и AltiVec для платформы PowerPC). Он находится под лицензией MIT с открытым исходным кодом.

Cell Broadband Engine

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

Ограничения

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

См. Также

Ссылки

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

  • JAligner - Java-реализация алгоритма Смита – Ватермана с открытым исходным кодом
  • BABA - апплет (с исходным кодом), который наглядно объясняет алгоритм
  • FASTA / SSEARCH - страница услуг на EBI
  • UGENE Smith – Waterman plugin - реализация SSEARCH-совместимой реализации с открытым исходным кодом алгоритм с графическим интерфейсом, написанный на C ++
  • OPAL - библиотека SIMD C / C ++ для массового оптимального выравнивания последовательностей
  • diagonalsw - реализация C / C ++ с открытым исходным кодом с наборами инструкций SIMD (особенно SSE4. 1) под лицензией MIT
  • SSW - библиотека C ++ с открытым исходным кодом, предоставляющая API для реализации SIMD алгоритма Смита – Уотермана под лицензией MIT
  • melod ic sequence alignment - реализация javascript для выравнивания мелодических последовательностей
Последняя правка сделана 2021-06-08 06:52:05
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте