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