[ИГРАЕТ_МУЗЫКА] Теперь рассмотрим
задачу нахождения подстроки в строке с ошибками, потому что в информатике,
как вам уже наверное известно, все данные содержат ошибки,
и нам часто неинтересно находить положение рида в геноме
с учетом того, что в риде нет ошибок, потому что на самом деле ошибки есть.
Допустим, если вам дан геном и все тот же рид,
и вы хотите найти, где он встречается в геноме с всего одной ошибкой.
Что можно сделать?
Можно опять-таки пробежаться по всему геному из О(М*К), сравнить все
буквы рида со всеми буквами генома и найти такое вхождение, но это очень медленно.
Хеш-функция уже неприменима,
потому что если в риде где-то посередине есть ошибка,
то хеш-функция уже не будет совпадать по значению с хеш-функцией
того участка в геноме, в котором рид входит с этой ошибкой.
Есть достаточно простая техника,
которая позволяет свести эту задачу к задаче точного поиска подстроки в строке.
Рассмотрим наш рид в увеличенном масштабе.
Допустим, в нем 100 букв.
И мы знаем, что мы допускаем одну ошибку при
нахождении этой подстроки в геноме, то есть мы разрешаем,
чтобы он, этот рид входил, находился в геноме с одной ошибкой.
Мы можем разделить его пополам, по 50 букв,
и можно заметить, что эта одна ошибка, она может встречаться либо в левой половине,
либо в правой, но не может встречаться и в той и в той половине сразу,
потому что ошибка может быть всего одна.
И в данном случае мы можем точно найти 50 букв,
которые соответствуют префиксу рида,
а также точно найти 50 букв, которые соответствуют суффиксу нашего рида
в геноме с помощью алгоритмов точного поиска подстроки в строке.
И если мы нашли, например, 50 первых букв,
то мы можем продолжить их на следующие 50 букв и проверить,
есть ли там суффикс с ошибками, ну и наоборот.
Таким образом, рид длины К мы можем разбить на два фрагмента
длины К/2 и найти из них каждый с помощью точного алгоритма.
Если мы ищем рид не с одной ошибкой, а например, с двумя,
то с таким же успехом можно разбить его на три фрагмента,
каждый длины К/3,
и можно заметить, что если у нас есть рид, разбитый на три фрагмента,
и всего две ошибки, то какая-то из этих третей должна входить в геном точно.
И если мы будем искать все трети нашего рида точно и потом их расширять вперед,
назад или в обе стороны, в зависимости от того, какой мы фрагмент нашли,
то мы можем вначале определить быстро нахождение
вот этого фрагмента точного, а потом расширить и найти уже неточный.
Похоже, работает всем известный алгоритм BLAST.
Он вначале находит точное вхождение небольшого SIDа и после
этого расширяет вправо и влево выравнивание до того момента,
пока оно похоже на ту подстроку, которую мы ищем.
Таким образом, сама строка не обязана входить точно в наш текст, но какой-то
маленький фрагмент этой строки должен быть, должен точно находиться в тексте.
[ИГРАЕТ_МУЗЫКА]
