Изменения

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

* Сравниваем все вектора попарно с помощью какой-нибудь метрики (например, евклидовой, максимума модуля разности или суммы модулей разностей координат) и если они два вектора оказываются ближедруг к другу, чем на заданное число ε, считаем, что в этой области последовательностипоследовательностей, соответствующие этим векторам, похожи друг на друга. Теперь представляем, что хотим это ускорить. Для простоты, за расстояние между векторами берём максимум модуля разности, а базис используем тригонометрический (Фурье). Хотим, по сути, уйти от сложности 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 % — мы убьём максимум половину сложности, а в реальности — ещё меньше, потому что многомерный индекс никогда не работает точно.

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

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

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

Второй: при линейном поиске и сравнении мы же не сравниваем вектора целиком. Мы их сравниваем последовательно Обычное K-D (от 1-ой координаты к K-ойDimensional) дерево представляет собой вид BSP-дерева (BSP = Binary Space Partitioning, то есть в порядке убывания абсолютных значений коэффициентов, а значитразбиение пространства на две части), в среднем и разности. То есть большая часть неподходящих нам векторов отсекается вообще по 1-ой координате. Мало — по второйкотором все разбиения осуществляются гиперплоскостями, ещё меньше — по третьей, и тперпендикулярными одной из осей координат. п. В реале получается, что по 8-16-ым не отсекается вообще почти ничего, а по где-то 7Каждый узел K-D дерева характеризуется номером координаты и из них — совсем ничегопороговым значением. В то же время для полной проверки ''подходящего'' вектора нужно сделать точно K сравнений. То естьЕсли значение выбранной координаты в точке меньше или равно этого порогового значения, 90 % неподходящих векторов дают часть сложности, сравнимую с полной проверкой оставшихся 10 %. Соответственно, даже если мы изобретём индекс, который позволит нам сразу отсечь почти все 90 % — мы убьём только примерно половину сложности. Потому что индекс никогда не выдаст сразу точно 10 %точка относится к левому подпространству, а выдаст, скажем, 15 %, которые ещё нужно проверить и ещё 5 % отсечь. Соответственно если даже мы сделаем оптимальный неточный индекс, максимум ускорения с его помощью зависит только от процента подходящих векторов и размерности. Чем больше потенциально подходит — тем хуже, чем больше размерность — тем хужебольше — к правому.

Мысли:* Разбить последовательность на слова Выбор разделяющих плоскостей в простейшей и проиндексировать их с учётом возможных сдвиговнаиболее часто используемой реализации K-D дерева делается просто — выбирается медианное значение нужной координаты по всей выборке индексируемых точек.* Использовать вместо классических базисов целочисленный вэйвлетоподобный базис, порождаемый из замены двух чисел на их сумму и разность.* Но использовать сами вэйвлеты, то есть когда разности не раскладываются повторно, не совсем верноТаким образом строится сбалансированное К-Д дерево.