Об ускорении поиска повторов ОСАМ-методом
Имеем алгоритм поиска приближённых повторов в ДНК-последовательностях:
- Скользим по последовательности окном размера W и каждую букву заменяем на количество пуринов (A, G, U — аденин, гуанин, урацил) / пиримидинов (C, T — цитозин, тимин) в этом окне (W-окрестности буквы). Полученную числовую последовательность называем «профилем последовательности».
- Дальше, начиная с каждой из (N-A)/S позиций, где N — длина последовательности, A — второе окно, «окно аппроксимации», S — шаг аппроксимации (расстояние между соседними начальными позициями), выцепляем A чисел. Из этих A чисел методом ближайшего соседа выбираем K (K сильно меньше A, например, K=16, A=500), равномерно или в соответствии с сеткой разложения выбранного базиса. Эти K чисел раскладываем по выбранному базису, получаем в каждой из (N-A)/S позиций K коэффициентов, характеризующих часть последовательности длиной A.
- Получаем вместо длинной строки кучу векторов по K коэффициентов. Проделываем это с обеими сравниваемыми последовательностями (или с одной, если сравниваем её саму с собой).
- Сравниваем все вектора попарно и если они ближе, чем на ε, считаем, что в этой области последовательности, похоже, повтор.
Обоснование профиля:
Теперь представляем, что хотим это ускорить. Для простоты, за расстояние между векторами берём максимум модуля разности, а базис используем тригонометрический (Фурье). Хотим, по сути, уйти от сложности O(N²).
И сразу несколько обламываемся из-за природы коэффициентов разложения — распределение похоже на нормальное, и что ещё хуже, первые коэффициенты сильно больше последних по модулю. Сильно — это примерно на 1-2 порядка. Причины две — во-первых, в реальных данных низкочастотные гармоники всегда больше, во-вторых, в нашем случае высокочастотные гармоники приглушены нами же — исходный вектор длины K => разница между двумя соседними значениями в нём по модулю не больше A/K, так как разница между двумя соседними значениями в профиле последовательности либо 0, либо 1, либо −1. Следовательно, максимум i-го коэффициента примерно (K+1-i)*A/K.
Мысли:
- Использовать вместо классических базисов вэйвлетоподобный базис, порождаемый из замены двух чисел на их сумму и разность.
- Но использовать сами вэйвлеты, то есть когда получается не вполне верно
