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

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

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

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

Задача парного локального выравнивания связана с определением пары похожих подстрок в двух молекулярных последовательностях. В компьютерных науках эта задача изучалась более сорока лет. Однако до 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) памяти при помощи динамического программирования. Алгоритм должен заполнить четыре таблицы H, HN, HS и HT размером m x n, где на каждую запись требуется константное время. Эти таблицы содержат следующие значения.

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

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

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

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

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

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

Базовый шаг:

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

Применение

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

Ссылка на код

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)