1313
правок
Приближенное сравнение регулярных выражений: различия между версиями
Перейти к навигации
Перейти к поиску
Приближенное сравнение регулярных выражений (посмотреть исходный код)
Версия от 04:34, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 1 участника) | |||
| Строка 42: | Строка 42: | ||
== Применение == | == Применение == | ||
Эта задача применяется в вычислительной биологии для нахождения определенных типов мотивов в ДНК и последовательностях белка. Подробнее об этом см. обсуждение в работе [1]. В частности, ограниченными регулярными выражениями являются шаблоны PROSITE, достаточно широко применяющиеся при поиске | Эта задача применяется в вычислительной биологии для нахождения определенных типов мотивов в ДНК и последовательностях белка. Подробнее об этом см. обсуждение в работе [1]. В частности, ограниченными регулярными выражениями являются шаблоны PROSITE, достаточно широко применяющиеся при поиске в последовательностях белка. На практике шаблоны PROSITE можно искать при помощи более быстрых алгоритмов [7]. То же происходит и с другими классами сложных шаблонов [6] и сетевых выражений [2]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 54: | Строка 54: | ||
== См. также == | == См. также == | ||
* [[Сравнение регулярных выражений]] – более простой случай, в котором ищется точное совпадение со строками в L(R). | * [[Сравнение регулярных выражений]] – более простой случай, в котором ищется точное совпадение со строками в <math>\mathcal{L}(R)</math>. | ||
* [[Последовательное приближенное сравнение строк]] – упрощение данной задачи; в этом случае связь между графом G и матрицей C должна быть очевидной. | * [[Последовательное приближенное сравнение строк]] – упрощение данной задачи; в этом случае связь между графом <math>\mathcal{G}</math> и матрицей C должна быть очевидной. | ||
== Литература == | == Литература == | ||
| Строка 77: | Строка 77: | ||
10. Wu, S., Manber, U., Myers, E.W.: A subquadratic algorithm for approximate regular expression matching. J. Algorithms 19(3), 346-360(1995) | 10. Wu, S., Manber, U., Myers, E.W.: A subquadratic algorithm for approximate regular expression matching. J. Algorithms 19(3), 346-360(1995) | ||
[[Категория: Совместное определение связанных терминов]] | |||