Локальное выравнивание (с вогнутыми штрафами за гэп)
Ключевые слова и синонимы
Выравнивание последовательностей; парное локальное выравнивание
Постановка задачи
В работе Миллера и Майерса [9] рассматривается задача парного выравнивания последовательностей, в которой мера расстояния основана на модели штрафа за гэп (пропуск в последовательности). Авторы предложили эффективный алгоритм для решения задачи в ситуации, когда штраф за гэп является вогнутой функцией от длины гэпа.
Пусть X и Y – две строки (последовательности) алфавита [math]\displaystyle{ \Sigma }[/math]. Парное выравнивание [math]\displaystyle{ \mathcal{A} }[/math] строк X и Y отображает X, Y на строки X', Y', которые могут содержать пробелы (не являющиеся частью алфавита [math]\displaystyle{ \Sigma }[/math]) таким образом, что выполняется следующее: (1) [math]\displaystyle{ |X'| = |Y'| = \ell }[/math]; (2) удаление пробелов из X' и Y' превращает их в X и Y, соответственно; (3) для любого [math]\displaystyle{ 1 \le i \le \ell }[/math] значения позиций X'[i] и Y'[i] не могут одновременно быть пробелами; здесь X'[i] обозначает i-й символ в X'.
Для оценки качества выравнивания было предложено множество различных метрик (например, расстояние редактирования, матрица замен [11]). В данной статье рассматривается модель штрафа за гэп.
Гэпом в выравнивании [math]\displaystyle{ \mathcal{A} }[/math] строк X и Y считается максимальная подстрока из смежных пробелов в последовательности X' или Y'. В выравнивании имеются гэпы и выровненные символы (и X'[i], и Y'[i] не являются пробелами). Оценка пары выровненных символов основана на функции расстояния [math]\displaystyle{ \delta(a, b) }[/math], где [math]\displaystyle{ a, b \in \Sigma }[/math]. Обычно [math]\displaystyle{ \delta }[/math] является метрикой, но в данной статье это предположение не требуется. Штраф за гэп длиной k основывается на неотрицательной функции W(k). Оценка выравнивания представляет собой сумму оценок всех выровненных символов и гэпов. Выравнивание является оптимальным, если оно имеет минимально возможную оценку.
Штрафная функция W(k) является вогнутой, если [math]\displaystyle{ \bigtriangleup W(k) \ge \bigtriangleup W(k + 1) }[/math] для всех [math]\displaystyle{ k \ge 1 }[/math], где [math]\displaystyle{ \bigtriangleup W(k) = W(k + 1) - W(k) }[/math].
Штрафная функция W(k) является аффинной, если W(k) = a + bk, где a, b – константы. Аффинная функция является частным случаем вогнутой функции. Задача об аффинных штрафах рассматривалась в работах [1, 6] и в одноименной статье.
Штрафная функция W(k) является P-кусочной аффинной кривой, если область W можно разбить на P интервалов, [math]\displaystyle{ (\tau_1 = 1, \chi_1), (\tau_2, \chi_2), ..., (\tau_p, \chi_p = \infty) }[/math], где [math]\displaystyle{ \tau_i = \chi_{i - 1} + 1 }[/math] для всех [math]\displaystyle{ 1 \lt i \le p }[/math], такое, что для каждого интервала значения W описываются аффинной функцией. Более точно, для любого [math]\displaystyle{ k \in (\tau_i, \chi_i), W(k) = a_i + b_i k }[/math] для некоторых констант [math]\displaystyle{ a_i, b_i }[/math].
Задача
Дано: Две строки X и Y, функция оценки [math]\displaystyle{ \delta }[/math] и функция штрафа за гэп W(k).
Требуется: найти оптимальное выравнивание X и Y.
Основные результаты
Теорема 1. Если функция W(k) является вогнутой, это дает нам алгоритм для вычисления оптимального выравнивания, который выполняется за время [math]\displaystyle{ O(n^2 \; log \; n) }[/math], где n – длина каждой строки, и использует O(n) ожидаемой памяти.
Следствие 1. Если W(k) является аффинной функцией, этот же алгоритм выполняется за время [math]\displaystyle{ O(n^2) }[/math].
Теорема 2. Для некоторых специальных типов штрафных функций алгоритм может быть модифицирован для более быстрого выполнения.
• Если W(k) является P-кусочной аффинной кривой, то алгоритм можно модифицировать таким образом, что он будет выполняться за время [math]\displaystyle{ O(n^2 \; log \; P) }[/math].
• Для логарифмической штрафной функции, W(k) = a + b log k, алгоритм может быть модифицирован так, чтобы выполняться за [math]\displaystyle{ O(n^2) }[/math] времени.
• Если W(k) является вогнутой функцией при k > K, алгоритм может быть модифицирован для выполнения за время [math]\displaystyle{ O(K + n^2 \; log \; n) }[/math].
Применение
Парное выравнивание последовательностей является фундаментальной задачей вычислительной биологии. Из сходства последовательностей обычно следует функциональное и структурное сходство. Таким образом, парное выравнивание может быть использовано для проверки того, имеют ли две заданные последовательности схожие функции или структуры, а также для предсказания функций только что идентифицированной последовательности ДНК. Некоторые примеры важности выравнивания последовательностей можно найти в книге Дэна Гасфилда ([7], стр. 212-214).
Задача выравнивания может быть далее разделена на глобальную и локальную задачи. В данной статье рассматривается глобальная задача выравнивания, в которой все входные строки должны быть выровнены друг с другом. При локальном выравнивании основной интерес заключается в вычленении подстроки из каждой входной строки таким образом, чтобы оценка выравнивания двух подстрок была минимальной среди всех возможных подстрок. Локальное выравнивание полезно при выравнивании последовательностей, которые не похожи друг на друга, но содержат область, являющуюся высококонсервативной (похожей). Обычно эта область является функциональной частью (доменом) последовательностей. Локальное выравнивание особенно эффективно при сравнении белков. Белки одного семейства от разных видов обычно имеют некоторые высококонсервативные функциональные домены, в то время как другие части этих белков совсем не похожи друг на друга. Примером могут служить гены гомеобокса [10], для которых последовательности белков у каждого вида совершенно разные, за исключением функционального домена под названием «гомеодомен».
Концептуально оценка выравнивания используется для фиксации эволюционного расстояния между двумя заданными последовательностями. Поскольку гэп величиной в более чем один пробел может быть создан одним мутационным событием, в некоторых случаях может быть более уместным рассматривать гэп длиной k в качестве единичного элемента вместо k различных точечных мутаций. Однако вопрос о том, какую функцию штрафа за открытие гэпа следует использовать, весьма непрост и иногда зависит от конкретного приложения. В большинстве приложений, таких как BLAST, используется аффинная функция штрафа, которая на практике до сих пор является доминирующей моделью. С другой стороны, Беннер и др. [2], а также Гу и Ли [13] предложили в некоторых случаях использовать логарифмическую функцию штрафа. Вопрос о том, имеет ли смысл использовать вогнутую функцию штрафа за открытие гэпа в общем случае, остается открытым.
Открытые вопросы
Отметим, что результаты данной статьи были независимо получены Галилом и Джанкарло [5]; в случае аффинного штрафа за открытие гэпа Готох [5] предложил алгоритм для решения задачи выравнивания с временем выполнения [math]\displaystyle{ O(n^2) }[/math]. В работе [4] Эппштейн представил более быстрый алгоритм для решения той же задачи выравнивания последовательностей с вогнутой функцией штрафа за открытие гэпа с временем выполнения [math]\displaystyle{ O(n^2) }[/math]. Вопрос о том, существует ли субквадратичный алгоритм для решения этой задачи, остается открытым. Следует отметить, что субквадратичные алгоритмы для решения задачи выравнивания последовательностей существуют в случаях, когда метрика не основана на модели штрафа за открытие гэпа и вычисляется как [math]\displaystyle{ \sum_{i = 1}^{\ell} \delta(X'[i], Y'[i]) }[/math], основываясь только на функции оценки [math]\displaystyle{ \delta(a, b) }[/math], где [math]\displaystyle{ a, b \in \Sigma \cup \{ }[/math] _ [math]\displaystyle{ \} }[/math], где "_" обозначает пробел [3, 8].
Экспериментальные результаты
Миллер и Майерс провели некоторые эксперименты для сравнения своего алгоритма с алгоритмом Ватермана (Уотермана) с временем выполнения [math]\displaystyle{ O(n^3) }[/math] [12] на ряде различных вогнутых штрафных функций. Для этих экспериментов были сгенерированы искусственные последовательности. Результаты экспериментов привели к предположению, что метод Ватермана выполняется за время [math]\displaystyle{ O(n^3) }[/math], когда две заданные строки очень похожи или оценка за различающиеся символы мала, тогда как алгоритму Миллера и Майера требуется время [math]\displaystyle{ O(n^2) }[/math], если диапазон функции W(k) функционально не зависит от n.
См. также
Литература
1. Altschul, S.F., Erickson, B.W.: Optimal sequence alignment using affine gap costs. Bull. Math. Biol. 48,603-616 (1986)
2. Benner, S.A., Cohen, M.A., Gonnet, G.H.: Empirical and structural models for insertions and deletions in the divergent evolution of proteins. J. Mol. Biol. 229,1065-1082 (1993)
3. Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM J. Comput. 32(6), 1654-1673 (2003)
4. Eppstein, D.: Sequence comparison with mixed convex and concave costs. J. Algorithms 11(1), 85-101 (1990)
5. Galil, Z., Giancarlo, R.: Speeding up dynamic programming with applications to molecular biology. Theor. Comput. Sci. 64, 107-118(1989)
6. Gotoh, O.: An improved algorithm for matching biological sequences. J. Mol. Biol. 162,705-708 (1982)
7. Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)
8. Masek, W.J., Paterson, M.S.: A fater algorithm for computing string edit distances. J. Comput. Syst. Sci. 20,18-31 (1980)
9. Miller, W., Myers, E.W.: Sequence comparison with concave weighting functions. Bull. Math. Biol. 50(2), 97-120 (1988)
10. De Roberts, E., Oliver, G., Wright, C.: Homeobox genes and the vertibratebody plan, pp. 46-52. Scientific American (1990)
11. Sankoff, D., Kruskal, J.B.: Time Warps, Strings Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley(1983)
12. Waterman, M.S.: Efficient sequence alignment algorithms. J. Theor. Biol. 108, 333-337 (1984)
13. Li, W.-H., Gu, X.: The size distribution of insertions and deletions in human and rodent pseudogenes suggests the logarithmic gap penalty for sequence alignment. J. Mol. Evol. 40,464-473 (1995)