[ЗАСТАВКА]
[ЗАСТАВКА] Здравствуйте.
Сегодня мы поговорим о строковых алгоритмах, применяемых в информатике.
И для начала введём определение, что такое алфавит.
Алфавит — это набор некоторых символов, из которых складываются строки.
Алфавит может быть разный.
Может быть из букв а, б, в, г, д, и так далее, вплоть до я,
это алфавит символов из кириллицы, может быть алфавит a, b,
c, d, e, и так далее, вплоть до z, может быть алфавит,
с которым мы чаще всего и будем работать, состоящий из букв A, C, G и T.
Это алфавит из четырёх букв, соответствующих нуклеотидам в геноме.
И геном или любая геномная последовательность — это
слово в этом алфавите, которое составлено из букв этого алфавита.
Бывают алфавиты и другие.
Например, в лингвистике, часто используется алфавит из слов.
И тогда слово — это предложение.
И некоторые поисковые системы, и поисковые алгоритмы, которые работуют на
текстах ищут не по отдельным буквам, а по целым словам, и тогда алфавит — это слова.
В нашем случае часто используется алфавит именно из букв A, C, G и T.
Также важно понимать различия между понятием
«подстрока» и «подпоследовательность».
Для начала также важно понимать,
что строка и последовательность обозначают одно и то же, и я буду
часто называть строки последовательностями и последовательности строками.
Но подстрока и подпоследовательность — это разные математические термины.
Подстрока — это когда некоторый...
некоторое слово полностью содержится в тексте, в какой-то позиции этого текста.
Подпоследовательность — это когда буквы из нашего слова
встречаются в тексте в этом порядке.
Например, если наш текст или геном — это
ACGT ACGT, то, например,
GTA является подстрокой этого текста, потому что
она полностью встречается последовательно в некоторой позиции этого текста.
Но GTC не является подстрокой, с другой стороны,
оно является подпоследовательностью, потому что буквы G, T и C встречаются
именно в той же последовательности, как и специфицировано в нашей строке.
Теперь рассмотрим задачу о нахождении подстроки в строке,
которую вкратце мы обсуждали и в прошлый раз,
но сейчас мы рассмотрим более эффективные алгоритмы для решения этой задачи.
Напомню, что нам дан некоторый текст, например, геном,
и дан некоторый паттерн,
например, рид, который мы хотим найти в этом геноме,
то есть мы хотим найти такую позицию в этом геноме, где встречается наш рид.
Что мы можем сделать?
Мы можем прикладывать этот рид в каждой позиции, начиная с первой,
и проверять точное совпадение.
Допустим у нас текст длины M и рид длины K,
тогда, чтобы найти приложение этого рида к геному,
нам нужно совершить O от M на K операций,
то есть каждую позицию рида сравнить с каждой позицией генома.
Но можно сделать это и чуть более эффективно.
Один из способов находить более эффективные подстроки в строке —
это использовать хэширование.
Это достаточно распространённая техника,
которая применяется активно в строковых алгоритмах и на практике хорошо работает.
И часто с помощью хэширования, с помощь применения Hash функции
можно решить очень многие строковые алгоритмы достаточно эффективно,
даже несмотря на то, что в худшем случае они бы работали дольше,
но в среднем и на практике они работают очень хорошо.
Для этого введём определение Hash функции.
Hash функция — это некоторая функция,
которая берёт объект из множества a и
переводит его в объект из множества b, при этом важно,
что множество b более маленькое, более компактное, чем a.
Например, в данном случае мы можем ввести функцию Hash
от строки, которая переводит строку в не которое число,
например, складывает коды всех букв и это является числом.
Понятно, что у разных строк может быть одинаковое значение Hash функции.
Например, если мы просто складываем значения целочисленных букв,
то Hash функция от строки AC будет равно Hash функции от строки CA.
Но главное, что если Hash функция совпадает,
то потенциально эти строки могут быть одинаковыми.
И, в частности,
именно Hash функция от строк в число чаще всего применяется в геномике.
Как это можно использовать для нахождения подстроки в строке?
Мы можем посчитать Hash функцию от нашего рида, то есть,
допустим, Hash функция от рида нам известна,
это некоторое целое число, которое мы посчитаем.
Теперь мы можем считать Hash функцию от каждой подстроки в нашем
геноме и сравнивать не целые строки, а значения Hash функций.
И, если значения Hash функций равны, то после этого уже сравнивать сами строки.
Вроде бы никакого ускорения в данном случае не получается,
потому что, чтобы вычислить Hash функцию от каждой подстроки,
нам нужно совершить те же K операций, умножить на M,
и получается та же самая оценка O (M * K).
Но Hash функцию можно вычислять более эффективно.
Например, если у нас есть геном ACGT, ACGT,
и мы знаем Hash функцию от некоторой подстроки этого генома ACG,
то следующую Hash функцию от CGT мы можем вычислить быстро,
не складывая все эти буквы, а, например,
вычтя значение буквы A и прибавив значение буквы T.
Таким образом пересчёт Hash функции по геному, когда мы идём,
он будет происходить за O(1), то есть за одну, ну в данном случае две операции,
одно вычитание и другое сложение, но это всё O(1), то есть это константа.
И пересчитывая Hash функцию по геному мы можем быстро
сравнивать потенциальное вхождение рида в этом месте генома.
И если Hash функции равны, после этого уже сравнивать риды целиком.
Конечно, у нас будут некоторые ложные срабатывания вот такого алгоритма,
потому что, как я говорил ранее, значение Hash функции может совпадать случайно.
Но это редкое событие и мы в любом случае проверяем потом точные вхождения.
В частности, если мы вычислили Hash функцию в начале генома,
потом во второй позиции генома, в третьей, и так далее,
и в каком-то месте она совпала, мы после этого сравниваем всю
последовательность рида с этим участком, если он не равен, мы двигаемся дальше.
Допустим, Hash функция по значению совпала с нашим ридом здесь,
и мы сравниваем снова полностью последовательность
рида с этим частком в геноме, и если он равен, то это нужный нам ответ.
Такой алгоритм в среднем работает за O(M + K),
то есть нам нужно вычислить один раз Hash функцию от рида
и начала генома, и потом M раз передвинуть эту Hash функцию,
то есть пересчитывать для каждой следующей позиции за единичку, то есть 1*M.
И такой алгоритм работает быстрее,
и в среднем на практике он очень хорошо работает и хорошо применим.
[ЗАСТАВКА]
Alla L LapidusProfessor, Department of Cytology and Histology
Николай Вяххи
Павел ДобрынинМладший научный сотрудник
Михаил РайкоПостдок
Екатерина ЧерняеваПостдок
