4551
правка
Последовательное приближенное сравнение строк: различия между версиями
Материал из WEGA
Последовательное приближенное сравнение строк (посмотреть исходный код)
Версия от 16:32, 29 марта 2019
, 29 марта 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 79: | Строка 79: | ||
== Применение == | == Применение == | ||
Эта задача широко применяется в вычислительной биологии (для сравнения последовательностей ДНК и белков, восстановления после ошибок экспериментов, а также для выявления точек мутаций или прогнозирования сходства в структуре или функции), для текстового информационного поиска (для восстановления после ошибок транскрипции, набора, typing или автоматического распознавания), обработки сигналов (для восстановления после ошибок при передаче и искажений) и в некоторых других областях. Подробнее об этом см. обсуждение в работе [11]. | |||
Существует немало расширений задачи ASM, особенно в вычислительной биологии. К примеру, можно заменить полные подстроки другими (обобщенное расстояние редактирования), поменять символы в строке (сравнение строк с заменами или транспозициями), выполнить обращение подстрок (расстояние обращений), присвоить разную стоимость операциям вставки и удаления в случае их группировки (сходство со штрафами за пропуски) или искать любую пару подстрок обеих строк, обладающую достаточным сходством (локальное сходство). Примеры можно найти в книге Гусфилда [7], где рассматривается множество родственных задач. | |||
== Открытые вопросы == | |||
