4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
В работе Миллера и Майерса [9] рассматривается задача парного выравнивания последовательностей, в которой мера расстояния основана на модели штрафа за | В работе Миллера и Майерса [9] рассматривается задача парного выравнивания последовательностей, в которой мера расстояния основана на модели штрафа за гэп (пропуск в последовательности). Авторы предложили эффективный алгоритм для решения задачи в ситуации, когда штраф за гэп является вогнутой функцией от длины гэпа. | ||
Пусть X и Y – две строки (последовательности) алфавита | Пусть X и Y – две строки (последовательности) алфавита <math>\Sigma</math>. Парное выравнивание <math>\mathcal{A}</math> строк X и Y отображает X, Y на строки X', Y', которые могут содержать пробелы (не являющиеся частью алфавита <math>\Sigma</math>) таким образом, что выполняется следующее: (1) <math>|X'| = |Y'| = \ell</math>; (2) удаление пробелов из X' и Y' превращает их в X и Y, соответственно; (3) для любого <math>1 \le i \le \ell</math> значения позиций X'[i] и Y'[i] не могут одновременно быть пробелами; здесь X'[i] обозначает i-й символ в X'. | ||
Для оценки качества выравнивания предложено множество различных метрик (например, расстояние редактирования, матрица замен [11]). В данной статье рассматривается модель ''штрафа за | Для оценки качества выравнивания было предложено множество различных метрик (например, расстояние редактирования, матрица замен [11]). В данной статье рассматривается модель ''штрафа за гэп''. | ||
''Гэпом'' в выравнивании <math>\mathcal{A}</math> строк X и Y считается максимальная подстрока из смежных пробелов в последовательности X' или Y'. В выравнивании имеются гэпы и выровненные символы (и X'[i], и Y'[i] не являются пробелами). Оценка пары выровненных символов основана на функции расстояния <math>\delta(a, b)</math>, где <math>a, b \in \Sigma</math>. Обычно <math>\delta</math> является метрикой, но в данной статье это предположение не требуется. Штраф за гэп длиной k основывается на неотрицательной функции W(k). Оценка выравнивания представляет собой сумму оценок всех выровненных символов и | ''Гэпом'' в выравнивании <math>\mathcal{A}</math> строк X и Y считается максимальная подстрока из смежных пробелов в последовательности X' или Y'. В выравнивании имеются гэпы и выровненные символы (и X'[i], и Y'[i] не являются пробелами). Оценка пары выровненных символов основана на функции расстояния <math>\delta(a, b)</math>, где <math>a, b \in \Sigma</math>. Обычно <math>\delta</math> является метрикой, но в данной статье это предположение не требуется. Штраф за гэп длиной k основывается на неотрицательной функции W(k). Оценка выравнивания представляет собой сумму оценок всех выровненных символов и гэпов. Выравнивание является ''оптимальным'', если оно имеет минимально возможную оценку. | ||
Строка 18: | Строка 18: | ||
Штрафная функция W(k) является ''аффинной'', если W(k) = a + bk, где a, b – константы. Аффинная функция является частным случаем вогнутой функции. Задача об аффинных штрафах рассматривалась в работах [1, 6] и в одноименной статье. | Штрафная функция W(k) является ''аффинной'', если W(k) = a + bk, где a, b – константы. Аффинная функция является частным случаем вогнутой функции. Задача об аффинных штрафах рассматривалась в работах [1, 6] и в [[Локальное выравнивание (с аффинными штрафами за гэп)|одноименной статье]]. | ||
Строка 26: | Строка 26: | ||
'''Задача''' | '''Задача''' | ||
'''Дано''': Две строки X и Y, функция оценки <math>\delta</math> и функция штрафа за | '''Дано''': Две строки X и Y, функция оценки <math>\delta</math> и функция штрафа за гэп W(k). | ||
'''Требуется''': найти оптимальное выравнивание X и Y. | '''Требуется''': найти оптимальное выравнивание X и Y. | ||
Строка 49: | Строка 49: | ||
== Применение == | == Применение == | ||
Парное выравнивание последовательностей является фундаментальной задачей вычислительной биологии. Из сходства последовательностей обычно следует функциональное и структурное сходство. Таким образом, парное выравнивание может быть использовано для проверки того, имеют ли две заданные последовательности схожие функции или структуры, а также для предсказания функций только что идентифицированной последовательности ДНК. Некоторые примеры важности выравнивания последовательностей можно найти в книге Гасфилда (стр. 212-214 | Парное выравнивание последовательностей является фундаментальной задачей вычислительной биологии. Из сходства последовательностей обычно следует функциональное и структурное сходство. Таким образом, парное выравнивание может быть использовано для проверки того, имеют ли две заданные последовательности схожие функции или структуры, а также для предсказания функций только что идентифицированной последовательности ДНК. Некоторые примеры важности выравнивания последовательностей можно найти в книге Дэна Гасфилда ([7], стр. 212-214). | ||
Строка 55: | Строка 55: | ||
Концептуально оценка выравнивания используется для фиксации эволюционного расстояния между двумя заданными последовательностями. Поскольку гэп величиной в более чем один пробел может быть создан одним мутационным событием, в некоторых случаях может быть более уместным рассматривать гэп длиной k в качестве единичного элемента вместо k различных точечных мутаций. Однако вопрос о том, какую функцию штрафа за открытие гэпа следует использовать, весьма непрост и иногда зависит от конкретного приложения. В большинстве приложений, таких как BLAST, используется аффинная функция штрафа, которая на практике до сих пор является доминирующей моделью. С другой стороны, Беннер и др. [2], а также Гу и Ли [13] предложили в некоторых случаях использовать логарифмическую функцию штрафа. Вопрос о том, имеет ли смысл использовать вогнутую функцию штрафа за открытие гэпа в | Концептуально оценка выравнивания используется для фиксации эволюционного расстояния между двумя заданными последовательностями. Поскольку гэп величиной в более чем один пробел может быть создан одним мутационным событием, в некоторых случаях может быть более уместным рассматривать гэп длиной k в качестве единичного элемента вместо k различных точечных мутаций. Однако вопрос о том, какую функцию штрафа за открытие гэпа следует использовать, весьма непрост и иногда зависит от конкретного приложения. В большинстве приложений, таких как BLAST, используется аффинная функция штрафа, которая на практике до сих пор является доминирующей моделью. С другой стороны, Беннер и др. [2], а также Гу и Ли [13] предложили в некоторых случаях использовать логарифмическую функцию штрафа. Вопрос о том, имеет ли смысл использовать вогнутую функцию штрафа за открытие гэпа в общем случае, остается открытым. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Отметим, что результаты данной статьи были независимо получены Галилом и Джанкарло [5]; | Отметим, что результаты данной статьи были независимо получены Галилом и Джанкарло [5]; в случае аффинного штрафа за открытие гэпа Готох [5] предложил алгоритм для решения задачи выравнивания с временем выполнения <math>O(n^2)</math>. В работе [4] Эппштейн представил более быстрый алгоритм для решения той же задачи выравнивания последовательностей с вогнутой функцией штрафа за открытие гэпа с временем выполнения <math>O(n^2)</math>. Вопрос о том, существует ли субквадратичный алгоритм для решения этой задачи, остается открытым. Следует отметить, что субквадратичные алгоритмы для решения задачи выравнивания последовательностей существуют в случаях, когда метрика не основана на модели штрафа за открытие гэпа и вычисляется как <math>\sum_{i = 1}^{\ell} \delta(X'[i], Y'[i])</math>, основываясь только на функции оценки <math>\delta(a, b)</math>, где <math>a, b \in \Sigma \cup \{ </math> _ <math> \} </math>, где "_" обозначает пробел [3, 8]. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == |
правок