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

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

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

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

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

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

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

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

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

Первая проблема — природа коэффициентов разложения. Их распределение похоже на нормальное, и что ещё хуже, первые коэффициенты сильно больше последних по модулю. Сильно — это примерно на 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 дерева делается просто — выбирается медианное значение нужной координаты по всей выборке индексируемых точек. Таким образом строится сбалансированное К-Д дерево.