Локальное выравнивание: Смита-Ватермана

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

Локальное выравнивание ищет пару максимально похожих подучастков двух последовательностей. Алгоритм Смита-Ватермана — это Нидлман-Вунш с двумя правками: счёт не уходит ниже нуля, а выравнивание стартует от максимальной клетки.

Часто две последовательности не похожи целиком, но содержат общий домен или мотив. Глобальное выравнивание тут навредит, растягивая несхожие концы. Локальное выравнивание находит именно похожий кусок — и это чаще всего то, что нужно биологу (например, в BLAST).

Две ключевые правки

По сравнению с Нидлманом-Вуншем:

1. Обнуление. Если счёт клетки стал бы отрицательным, ставим 0. Это «забывает» плохое начало и позволяет выравниванию стартовать заново где угодно.
2. Старт трассировки от максимума. Идём не из угла, а из клетки с наибольшим счётом, и останавливаемся, дойдя до нуля.

dp[i][j] = max(
   0,                              # <- ключевая правка: не уходим в минус
   dp[i-1][j-1] + s(A[i], B[j]),
   dp[i-1][j]   + gap,
   dp[i][j-1]   + gap
)

Реализация

def smith_waterman(a, b, match=2, mismatch=-1, gap=-1):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    best, bi, bj = 0, 0, 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            s = match if a[i-1] == b[j-1] else mismatch
            dp[i][j] = max(0, dp[i-1][j-1] + s, dp[i-1][j] + gap, dp[i][j-1] + gap)
            if dp[i][j] > best:
                best, bi, bj = dp[i][j], i, j
    # трассировка от максимума до нуля
    al_a, al_b = '', ''
    i, j = bi, bj
    while i > 0 and j > 0 and dp[i][j] > 0:
        s = match if a[i-1] == b[j-1] else mismatch
        if dp[i][j] == dp[i-1][j-1] + s:
            al_a = a[i-1] + al_a; al_b = b[j-1] + al_b; i -= 1; j -= 1
        elif dp[i][j] == dp[i-1][j] + gap:
            al_a = a[i-1] + al_a; al_b = '-' + al_b; i -= 1
        else:
            al_a = '-' + al_a; al_b = b[j-1] + al_b; j -= 1
    return best, al_a, al_b

score, x, y = smith_waterman('ACACACTA', 'AGCACACA')
print('Лучший локальный счёт:', score)
print(x)
print(''.join('|' if p == q else ' ' for p, q in zip(x, y)))
print(y)

Вывод:

Лучший локальный счёт: 12
A-CACACTA
| ||||| |
AGCACAC-A

Алгоритм нашёл общий участок CACAC (с парой правок), а несхожие концы просто не вошли в выравнивание. Глобальный алгоритм был бы вынужден тянуть всё до конца — локальный аккуратно вырезал похожее ядро.

Глобальное против локального: когда что

Как работает под капотом: почему обнуление меняет всё

Один max(0, ...) кардинально меняет поведение. В глобальном выравнивании плохое начало (много замен) тянет счёт в большой минус, и хорошее продолжение не может это перевесить — алгоритм «помнит» плохой старт. Обнуление стирает память о плохих участках: как только накопленный счёт ушёл бы в минус, мы сбрасываемся в 0 и готовы начать новое локальное выравнивание. Поэтому результат — это лучший непрерывный «остров» сходства, а не компромисс по всей длине. Это ровно то, что нужно для поиска консервативных доменов и работы BLAST.

Частые ошибки

• Забыть про 0 в max. Без обнуления получится глобальное выравнивание, а не локальное.
• Стартовать трассировку из угла. В локальном — из клетки с максимумом, и стоп на нуле.
• Применять локальное там, где нужно глобальное. Для близких по длине последовательностей оно может вырезать лишь кусок и пропустить общую картину.

Итог

• Смит-Ватерман ищет лучший локально похожий участок, а не выравнивание по всей длине.
• Две правки к Нидлману-Вуншу: обнуление (max с 0) и старт трассировки от максимальной клетки.
• Обнуление «забывает» плохие участки, оставляя лучший остров сходства.
• Локальное — для доменов и поиска по базам (BLAST); глобальное — для близких по длине последовательностей.