Об ускорении поиска повторов ОСАМ-методом

Ссылки сюда (1) →

О методах ускорения работы алгоритма поиска приближённых повторов в ДНК-последовательностях.

Алгоритм поиска повторов

Имеем следующий алгоритм поиска приближённых повторов в ДНК-последовательностях:

• Скользим по последовательности окном размера W и каждую букву заменяем на количество пуринов (A, G, U — аденин, гуанин, урацил) / пиримидинов (C, T — цитозин, тимин) в этом окне (W-окрестности буквы). Полученную числовую последовательность называем «профилем последовательности». Здесь могут быть вариации — скажем, можно считать число других пар букв — например, G и C.
• Дальше, начиная с каждой из (N-A)/S позиций, где N — длина последовательности, A — второе окно, «окно аппроксимации», S — шаг аппроксимации (расстояние между соседними начальными позициями), выбираем A чисел. Приняв полученный вектор длины A за функцию дискретного аргумента, осуществляем дискретное спектральное преобразование этой функции в соответствии с одним из классических ортогональных базисов (например, с базисом Фурье), и вычисляем K спектральных коэффициентов. Преобразование может осуществляться как на сетке размера А, так и на сетке меньшего размера. Учитывая то, что каждое значение «включает в себя» информацию о соседних, так как является скользящей суммой — уменьшение сетки влияет на результат очень незначительно. Получаем в каждой из (N-A)/S позиций K коэффициентов, характеризующих часть последовательности длиной A.
• Получаем вместо длинной строки кучу векторов по K коэффициентов. Проделываем это с обеими сравниваемыми последовательностями (или с одной, если сравниваем её саму с собой).
• Сравниваем все вектора попарно с помощью какой-нибудь метрики (например, евклидовой, максимума модуля разности или суммы модулей разностей координат) и если два вектора оказываются ближе друг к другу, чем на заданное число ε, считаем, что куски последовательностей длины A, соответствующие этим векторам, похожи друг на друга.
• Визуально матрица сравнений отображается обычным изображением, в котором точки одного цвета соответствуют «близким» векторам, а точки другого цвета — отсутствию близости.
• Далее можно заметить, что более длинные повторы в последовательностях соответствуют отрезкам, параллельным главной диагонали. Соответственно, найдя все отрезки заданной длины на матрице сравнений, можно найти приблизительные координаты длинных прямых повторов.
• Любопытным свойством алгоритма является то, что на основе уже сгенерированных спектральных векторов мы можем найти также и обратные повторы. Ибо смена знака всех коэффициентов разложения с чётными номерами (если считать с 1) соответствует разложению f(-x), так как чётные коэффициенты — это либо полиномы нечётной степени, либо синусы, а и те, и те являются нечётными функциями. А f(-x) в случае использования сетки от −1 до 1 соответствует обращению строки, из которой сгенерирован раскладываемый вектор. Соответственно, для поиска обратных повторов нужно лишь немного поменять способ вычисления метрики и заметить, что более длинные обратные повторы соответствуют отрезкам, параллельным побочной диагонали матрицы.

Итак, в итоге основная сложность алгоритма складывается из сложности двух вещей — получения координат разложения и сравнения их друг с другом.

Теперь представляем, что алгоритм нужно ускорить. Для простоты, за расстояние между векторами берём максимум модуля разности, а базис используем тригонометрический (Фурье). Например, хотим уйти от сложности O(N²) (или N*M) при сравнении. Для этого можно применить или создать какую-нибудь индексную структуру.

Но здесь нас поджидают две проблемы:

Природа спектральных векторов

Первая проблема — природа коэффициентов разложения. Их распределение похоже на нормальное, и что ещё хуже, первые коэффициенты сильно больше последних по модулю. Сильно — это примерно на 1-2 порядка. Причины две — во-первых, в реальных данных низкочастотные гармоники всегда больше, во-вторых, в нашем случае высокочастотные гармоники приглушены нами же — исходный вектор длины K => разница между двумя соседними значениями в нём по модулю не больше A/K, так как разница между двумя соседними значениями в профиле последовательности либо 0, либо 1, либо −1. Следовательно, максимум i-го коэффициента примерно (K+1-i)*A/K. И всё это — распределено околонормально. Таким образом, разбиение пространства на какие-то области (построение индекса) уже становится проблемой — «полезных» измерений с большим относительно размера окрестности поиска диапазоном мало (3-5), бОльшая часть спектральных векторов распределена в центре всей области, центр маленький. То есть, при поиске приходится просматривать довольно много лишних векторов.

Простота линейного поиска

Линейный поиск очень прост по сравнению с поиском по индексу — сложность одного шага поиска по индексу сама по себе гораздо больше сложности одного шага «тупого» поиска, так как, скорее всего, включает ветвления, переходы по дереву, запоминание списка найденных элементов и тому подобные операции. Поэтому, даже выигрывая в числе шагов, мы получим меньшее ускорение, чем хотели бы.

Кроме того, с очевидной оптимизацией линейный поиск становится ещё проще. При попарном сравнении всех векторов не нужно делать их сравнивать полностью! Их достаточно сравнивать с искомой окрестностью последовательно от первой координаты к последней K-ой. Учитывая природу коэффициентов разложения — это примерно соответствует порядку убывания абсолютных значений коэффициентов, а значит, в среднем и разности.

То есть, большая часть неподходящих нам векторов отсекается вообще по 1-ой координате. Относительно мало — по второй, ещё меньше — по третьей, и т. п. В реальности получается, что по коэффициентам дальше 6-го не отсекается почти ничего, а дальше 9-го — совсем ничего. В то же время, для полной проверки подходящего вектора нужно сделать в точности K сравнений и не меньше.

Например, при K=16 все неподходящие вектора (а их 90 %) дают вклад в сложность, примерно равный (а то и меньший) полной проверке оставшихся 10 %. Соответственно, даже если мы изобретём индекс, который позволит нам сразу отсечь почти все 90 % — мы убьём максимум половину сложности, а в реальности — ещё меньше, потому что многомерный индекс никогда не работает точно.

То есть, индекс никогда не отсечёт сразу всё ненужное, а отсечёт, скажем, 85 % и останется 15 %, которые нужно проверить полностью, сложность их проверки будет в 1.5 раза выше половины изначальной. Соответственно, если даже мы сделаем оптимальный неточный индекс, максимум ускорения, получаемого с его помощью, будет зависеть только от процента подходящих векторов и размерности. Чем больше потенциально подходит — тем хуже, чем больше размерность — тем хуже. Например, в случае 85 %, отсечённых мгновенно (сложность = 0), выигрыш будет всего лишь 25 % = (1 — 0.5*1.5).

Из-за того, что по высшим гармоникам фильтрации почти не происходит, целесообразно оказывается использовать 3, максимум 5 коэффициентов разложения. В простейшем случае эти 3 коэффициента — среднее, проекция на синус, проекция на косинус.

K-D-N дерево

В простейшей реализации алгоритма поиска повторов все сгенерированные вектора спектральных координат сравниваются друг с другом попарно, что сильно ухудшает производительность. Порядок сложности такого алгоритма — O(N²). Чтобы его ускорить, нужно применять индексные структуры, позволяющие уменьшить сложность поиска.

Обычное K-D (от K-Dimensional) дерево представляет собой вид BSP-дерева (BSP = Binary Space Partitioning, разбиение пространства на две части), в котором все разбиения осуществляются гиперплоскостями, перпендикулярными одной из осей координат. Каждый узел K-D дерева характеризуется номером координаты и пороговым значением. Если значение выбранной координаты в точке меньше или равно этого порогового значения, точка относится к левому подпространству, а если больше — к правому.

Выбор разделяющих плоскостей в простейшей и наиболее часто используемой реализации K-D дерева делается просто — выбирается медианное значение нужной координаты по всей выборке индексируемых точек. Таким образом строится сбалансированное К-Д дерево.