13 521
правка
Изменения
м
Теперь представляемИтак, что хотим это ускорить. Для простоты, за расстояние между векторами берём максимум модуля разности, а базис используем тригонометрический (Фурье). Хотим, по сути, уйти от в итоге основная сложность алгоритма складывается из сложности O(N²). Для этого можно применить или создать какую-нибудь индексную структурудвух вещей — получения координат разложения и сравнения их друг с другом.
Нет описания правки
Имеем следующий алгоритм поиска приближённых повторов в ДНК-последовательностях:
* Скользим по последовательности окном размера 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) при сравнении. Для этого можно применить или создать какую-нибудь индексную структуру. Но здесь нас поджидает поджидают две проблемы:
==== Природа спектральных векторов ====