Локальное выравнивание (с аффинными штрафами за гэп)

Ключевые слова и синонимы

Парное локальное выравнивание с аффинными штрафами за гэп

Постановка задачи

Задача парного локального выравнивания связана с определением пары похожих подстрок в двух молекулярных последовательностях. В компьютерных науках эта задача изучалась более сорока лет. Однако до 1974 года большинство моделей задачи, как правило, не были удовлетворительными с биологической точки зрения либо не поддавались интерпретации. В 1974 году Питер Селлерс разработал метрическую меру сходства между молекулярными последовательностями. Уотермен и др. (1976) обобщили эту метрику, включив в нее вставки (инсерции) и удаления (делеции) произвольной длины, которые представляют собой минимальное количество мутационных событий, необходимых для преобразования одной последовательности в другую.

Пусть даны две последовательности, S и T. Парное выравнивание представляет собой способ вставки символов пробелов '_' в S и T для формирования последовательностей S' и T', соответственно, с той же длиной. Выравнивание двух последовательностей может производиться различными способами. Оценка выравнивания измеряется метрикой [math]\displaystyle{ \delta(x, y) }[/math]. В каждой позиции i, где x и y не являются пробелами, сходство между S'[i] и T'[i] измеряется значением [math]\displaystyle{ \delta(S'[i], T'[j]) }[/math]. Обычно [math]\displaystyle{ \delta(x, y) }[/math] положительно, когда x и y одинаковы, и отрицательно, когда x и y различны. Для позиций с последовательными символами пробела оценки выравнивания символов пробела не рассматриваются независимо; это связано с тем, что вставка или удаление длинного участка в молекулярных последовательностях более вероятна, чем вставка или удаление нескольких коротких участков. Смит и Уотермен используют аффинный штраф за гэп для моделирования сходства в позициях с символами пробелов. Они определяют последовательную подстроку с пробелами в S' или T' как гэп. Для каждого гэпа длиной [math]\displaystyle{ l }[/math] они назначают линейный штраф [math]\displaystyle{ W_k = W_s + l \times W_p }[/math], где [math]\displaystyle{ W_s }[/math] и [math]\displaystyle{ W_p }[/math] – некоторые заранее определенные положительные константы. Оценка выравнивания представляет собой сумму оценок в каждой позиции i минус штрафы за каждый гэп. Например, оценка следующего выравнивания равна [math]\displaystyle{ \delta(G, G) + \delta(C, C) + \delta(C, C) + \delta(U, C) + \delta(G, G) - (W_s + 2 \times W_p) }[/math].

S: GCCAUUG

T: GCC__CG

Оптимальное глобальное выравнивание последовательностей S и T – это выравнивание S и T с максимальной оценкой выравнивания.

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

Задача парного локального выравнивания

Дано: две последовательности S[1..n] и T[1..m].

Требуется: найти подстроку U в S и подстроку V в T, такие, что оптимальное глобальное выравнивание U и V максимально.

Основные результаты

Задача попарного локального выравнивания может быть решена за время O(mn) с использованием O(mn) памяти при помощи динамического программирования. Алгоритм должен заполнить четыре таблицы [math]\displaystyle{ H, H_N, H_S, H_T }[/math] размером m x n, где на каждую запись требуется константное время. Эти таблицы содержат следующие значения.

[math]\displaystyle{ H(i, j) }[/math]: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j].

[math]\displaystyle{ H_N(i, j) }[/math]: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j], с ограничением, согласно которому S[i] и T[j] должны быть выровнены.

[math]\displaystyle{ H_S(i, j) }[/math]: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j], где S[j] выровнен с символом пробела.

[math]\displaystyle{ H_T(i, j) }[/math]: максимальная оценка глобального выравнивания U и V над всеми суффиксами U в S[1..i] и всеми суффиксами V в T[1..j], где T[j] выровнен с символом пробела.

Оценка оптимального локального выравнивания S и T будет равна max{H(i, j)}, а локальное выравнивание S и T может быть найдено путем обратного обхода таблицы H.

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

Базовый шаг:

[math]\displaystyle{ H(i, 0) = H(0, j) = 0, 0 \le i \le n, 0 \le j \le m }[/math]

[math]\displaystyle{ H_N(i, 0) = H_N(0, j) = - \infty, 0 \le i \le n, 0 \le j \le m }[/math]

[math]\displaystyle{ H_S(i, 0) = H_T(0, j) = W_s + W_p, 0 \le i \le n, 0 \le j \le m }[/math]

[math]\displaystyle{ H_S(0, j) = H_T(i, 0) = - \infty, 0 \le i \le n, 0 \le j \le m }[/math]

Шаг рекурсии:

[math]\displaystyle{ H(i, j) = max \{H_N(i, j), H_S(i, j), H_T(i, j), 0 \}, 1 \le i \le n, 1 \le j \le m }[/math]

[math]\displaystyle{ H_N(i, j) = H(i - 1, j - 1) + \delta(s[i], T[j]), 1 \le i \le n, 1 \le j \le m }[/math]

[math]\displaystyle{ H_S(i, j) = max \{ H(i - 1, j) - (W_s + W_p), H_S(i - 1, j) - W_p \}, 1 \le i \le n, 1 \le j \le m }[/math]

[math]\displaystyle{ H_T(i, j) = max \{ H(i, j - 1) - (W_s + W_p), H_T(i, j - 1) - W_p \}, 1 \le i \le n, 1 \le j \le m }[/math]

Применение

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

Ссылка на код

http://bioweb.pasteur.fr/seqanal/interfaces/water.html

См. также

• Эффективные методы множественного выравнивания последовательностей с гарантированными границами погрешности
• Локальное выравнивание (с вогнутыми штрафами за гэп)

Литература

1. Allgower, E.L., Schmidt, P.H.: An Algorithm for Piecewise-Linear Approximation of an Implicitly Defined Manifold. SI AM J. Num. Anal. 22, 322-346(1985)

2. Altschul, S.F.,Gish,W., Miller,W., Myers, E.W., Lipman, D.J.: Basic Local Alignment Search Tool. J. Mol. Biol. 215,403-410 (1990)

3. Chao, K.M., Miller, W.: Linear-space algorithms that build local alignments from fragments. Algorithmica 13,106-134 (1995)

4. Myers, E.W., Miller, W.: Optimal Alignments in Linear Space. Bioinformatics 4,11 -17 (1988)

5. Gusfield,D.: Algorithms on Strings, Trees and Sequences. Cambridge University Press, Cambridge (1999). ISBN 052158519

6. Ma, B., Tromp, J., Li, M.: PatternHunter: Faster and More Sensitive Homology Search. Bioinformatics 18,440-445 (2002)

7. Needleman, S.B., Wunsch, C.D.: A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins. J. Mol. Biol. 48,443^53 (1970)

8. Pearson, W.R., Lipman, D.J.: Improved Tools for Biological Sequence Comparison. Proc. Natl. Acad. Sci. USA 85, 2444-2448 (1988)

9. Sellers, P.H.: On the Theory and Computation of Evolutionary Distances. SIAM J. Appl. Math. 26, 787-793 (1974)

10. Smith, T.F., Waterman, M.S.: Identification of Common Molecular Subsequences. J. Mol. Biol. 147,195-197 (1981)