4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 8 промежуточных версий этого же участника) | |||
Строка 10: | Строка 10: | ||
Дано: набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | Дано: набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | ||
Требуется: найти минимальное значение d и | Требуется: найти минимальное значение d и строку s длины m, находящуюся в пределах расстояния Хэмминга d от каждой строки <math>s_i \in S</math>. | ||
Строка 20: | Строка 20: | ||
Дано: целое число L и набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | Дано: целое число L и набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | ||
Требуется: найти минимальное значение d и | Требуется: найти минимальное значение d и строку s длины L, находящуюся в пределах расстояния Хэмминга d от имеющей длину L подстроки <math>t_i</math> строки <math>s_i</math> для i = 1, 2, ..., n. | ||
== Основные результаты == | == Основные результаты == | ||
Строка 26: | Строка 26: | ||
Теорема 1. Существует схема | '''Теорема 1. Существует аппроксимационная схема с полиномиальным временем выполнения для задачи поиска ближайшей строки.''' | ||
Теорема 2. Существует схема | '''Теорема 2. Существует аппроксимационная схема с полиномиальным временем выполнения для задачи поиска ближайшей подстроки.''' | ||
Строка 34: | Строка 34: | ||
== Применение == | == Применение == | ||
Многие задачи молекулярной биологии включают поиск схожих областей, общих для каждой последовательности, в заданном множестве последовательностей ДНК, РНК или белка. Эти задачи находят применение при локализации сайтов связывания и поиске консервативных областей в невыровненных последовательностях [2, 7, 9, 13, 14], генетической идентификации мишени лекарственного препарата [8], конструировании генетических зондов [8], конструировании универсальных праймеров для ПЦР [4, 8], а помимо вычислительной биологии – в теории кодирования [5, 6]. Подобные задачи могут рассматриваться как различные обобщения задачи поиска общей подстроки, допускающей наличие ошибок. Было предложено несколько метрик для поиска таких областей, общих для всех заданных строк. Популярной и одной из самых фундаментальных метрик является расстояние Хэмминга. Кроме того, в этой сфере используются две известные целевые функции. Одной из них является полная сумма расстояний между | Многие задачи молекулярной биологии включают поиск схожих областей, общих для каждой последовательности, в заданном множестве последовательностей ДНК, РНК или белка. Эти задачи находят применение при локализации сайтов связывания и поиске консервативных областей в невыровненных последовательностях [2, 7, 9, 13, 14], генетической идентификации мишени лекарственного препарата [8], конструировании генетических зондов [8], конструировании универсальных праймеров для ПЦР [4, 8], а помимо вычислительной биологии – в теории кодирования [5, 6]. Подобные задачи могут рассматриваться как различные обобщения задачи поиска общей подстроки, допускающей наличие ошибок. Было предложено несколько метрик для поиска таких областей, общих для всех заданных строк. Популярной и одной из самых фундаментальных метрик является расстояние Хэмминга. Кроме того, в этой сфере используются две известные целевые функции. Одной из них является полная сумма расстояний между центральной строкой (общей подстрокой) и каждой из заданных строк. Второй – максимальное расстояние между центральной строкой и заданной строкой. Более подробное изложение см. в работе [8]. | ||
'''Более общая задача''' | '''Более общая задача''' | ||
Задача выбора различающей подстроки получает на входе два множества строк, B и G. Требуется найти подстроку неуказанной длины (обозначаемой L), такую, что она оказывается близкой к подстрокам каждой строки из B и далекой от любой подстроки длины L строк из G. Впрочем, мы можем пройти все возможные значения L и предположить, что каждая строка в G имеет одну и ту же длину L, поскольку множество G может быть реконструировано с тем, чтобы содержать все подстроки длины L в каждой из хороших строк. | Задача ''выбора различающей подстроки'' получает на входе два множества строк, B и G. Требуется найти подстроку неуказанной длины (обозначаемой L), такую, что она оказывается близкой к подстрокам каждой строки из B и далекой от любой подстроки длины L строк из G. Впрочем, мы можем пройти все возможные значения L и предположить, что каждая строка в G имеет одну и ту же длину L, поскольку множество G может быть реконструировано с тем, чтобы содержать все подстроки длины L в каждой из хороших строк. | ||
Формальное определение задачи выглядит следующим образом. Пусть даны множество | Формальное определение задачи выглядит следующим образом. Пусть даны множество <math>B = \{ s_1, s_2, ..., s_{n_1} \}</math> из <math>n_1</math> (плохих) строк длиной не менее L и множество <math>G = \{ g_1, g_2, ..., g_{n_2} \}</math> из <math>n_2</math> (хороших) строк, длина которых в точности равна L, а также два целых числа <math>d_b</math> и <math>d_g</math> <math>(d_b \le d_g)</math>. Задача выбора различающей подстроки (distinguishing substring selection problem, DSSP) заключается в нахождении строки s, такой, что для каждой строки <math>s_i \in B</math> существует имеющая длину L подстрока <math>t_i</math> строки <math>s_i</math> с <math>d(s, t_i) \le d_b</math>, и для каждой строки <math>g_i \in G</math> имеет место <math>d(s, g_i) \ge d_g</math>. Здесь d(,) обозначает расстояние Хэмминга между двумя строками. Если все строки в множестве B также имеют длину L, задача называется задачей поиска различающей строки (distinguishing string problem, DSP). | ||
Строка 48: | Строка 48: | ||
Теорема 3. Существует схема | '''Теорема 3. Существует аппроксимационная схема с полиномиальным временем выполнения для задачи выбора различающей подстроки. А именно, для любого константного значения <math>\epsilon > 0</math> алгоритм находит строку s длины L, такую, что для каждого <math>s_i \in B</math> существует имеющая длину L подстрока <math>t_i</math> строки <math>s_i</math> с <math>d(t_i, s) \le (1 + \epsilon)d_b</math> и для каждой подстроки <math>u_i</math> длины L каждой строки <math>g_i \in G</math> имеет место <math>d(u_i, s) \ge (1 - \epsilon) d_g</math>, если существует решение для исходной пары <math>(d_b \le d_g)</math>. Поскольку существует полиномиальное количество таких пар <math>(d_b, d_g)</math>, мы можем за полиномиальное время перебрать все возможности и найти наиболее подходящую аппроксимацию для соответствующей конкретной задачи.''' | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Строка 55: | Строка 55: | ||
== См. также == | == См. также == | ||
* [[Нахождение ближайшей подстроки]] | * [[Нахождение ближайшей подстроки]] | ||
* [[Эффективные методы множественного выравнивания последовательностей с гарантированными границами | * [[Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок]] | ||
* [[Разработка алгоритмов для вычислительной биологии]] | * [[Разработка алгоритмов для вычислительной биологии]] | ||
* [[Многолокусная ПЦР для сокращения разрывов (при сборке полного генома)]] | * [[Многолокусная ПЦР для сокращения разрывов (при сборке полного генома)]] | ||
== Литература == | |||
1. Ben-Dor, A., Lancia, G., Perone, J., Ravi, R.: Banishing bias from consensus sequences. In: Proc. 8th Ann. Combinatorial Pattern Matching Conf., pp. 247-261. (1997) | 1. Ben-Dor, A., Lancia, G., Perone, J., Ravi, R.: Banishing bias from consensus sequences. In: Proc. 8th Ann. Combinatorial Pattern Matching Conf., pp. 247-261. (1997) | ||
правок