13 521
правка
Изменения
Нет описания правки
ОСАМ. Мысль простая: разложить сигнал по какому-нибудь классическому ортогональному базису, получить краткое описание, к тому же обладающее различными приятными свойствами. Обработать на основе описания сигнала. Применять можно в широком спектре задач распознавания. Свойства описания — «более важная» информация в первых коэффициентах; отсекая хвост, можно получать приближения сигнала; норма сохраняется; для неточных разложений есть мера точности разложения; и т. п. Т. е. есть хороший, проработанный, мат. аппарат.
Идея: применить ОСАМ к поиску повторов в ДНК, таким образом ускорив его. Как?! Во-первых, <nowiki>построить профиль последовательности, т. е. перевести её в длинный числовой вектор, выбрав w — w — окно профиля, и принимая за каждый элемент последовательности (количество пуринов в w-окрестности элемента) минус (количество пиримидинов в w-окрестности элемента). Далее, выбирая по N значений из полученной последовательности — последовательности — 0..N-1, s..N+s-1, 2s..N+2s-1, … (s — s — шаг аппроксимации) и раскладывая получаемые вектора из N чисел по k коэффициентам некоторого базиса, получить «индекс» последовательности. k << N, потому и «индекс». Далее пробежаться по всем полученным описаниям (по индексу) обеих последовательностей (или одной и той же последовательности) и сравнить попарно все пары описаний (на похожесть). А что такое похожесть? Критериев похожести можно выработать массу, среди них можно найти устойчивые к масштабу и т. п., однако у нас всё довольно просто:</nowiki><math>\frac{|a-b|}{|a|+|b|}</math>, где <math>|x|=\sqrt{\sum {x}_{i}^{2}}</math>. Такое вот «нормированное L<sub>2</sub>-расстояние». Здесь, кстати, можно выиграть от т. н. «принципа дискриминантности», который гласит очевидную вещь: что если <math>\frac{\sqrt{{\sum }_{i=0}^{k}{({a}_{i}-{b}_{i})}^{2}}}{|a|+|b|}> \mathrm{eps}</math><nowiki>уже при k < n, то суммирование можно не продолжать, т. к. меньше сумма квадратов уже не станет. Итак, что мы получим от этого сравнения? Мы получим приближённые «близости» участков ДНК. Крупных или мелких, более или менее точное сравнение — сравнение — это уже как захотим — захотим — для этого можно варьировать параметры. Задаём порог, можем пробежаться по результатам и сразу выявить «подозрительные на повторы» участки. Это есть важно, т. к. больше не нужно всё время искать повторы ВЕЗДЕ: сначала достаточно выявить крупные относительно похожие участки, а потом можно «увеличить масштаб» и выявить (или не выявить) точные координаты повторов. Кстати, единственное, для чего подход почти не подходит - подходит — для выявления «абсолютно точных» координат повторов. Это уже в «подозрительных» областях можно делать стандартными методами. Например, diffоподобным алгоритмом. :-)</nowiki>
Кстати, нужно использовать все современные возможности процессоров. Иначе будет обидно, если такую же программу написать на MATLAB’е и она — опа! — окажется быстрее в 5 раз. То есть нужно не забывать о многопоточности, не забывать об SIMD инструкциях, не забывать об аппаратном ускорении математических функций. Засчёт этого всего выигрываем в скорости ещё больше, реальная разница — в 10-20 раз (Core 2 Duo). Как?! Для многопоточности — голые нити (треды), никаких OpenMP! Так как это костылистая штуковина, приводит либо к сильному ухудшению структуры кода (причём фактическая логика получается аналогична голым тредам), либо к большим накладным расходам на распараллеливание — 5-15 %. Так что треды. Плюс библиотека Intel Integrated Performance Primitives для SIMD и аппаратного ускорения инструкций. А что это — IPP? А это такой векторный ассемблер, только на C. Библиотека, содержащая в себе оптимальные реализации большого спектра векторных операций (есть почти всё, что душе угодно — от сложений, умножений, корней и синусов, до узкоспециализированных функций ускорения декодирования аудио и видео, распознавания речи и т.д и т.п) для процессоров, имеющих различные расширения типа MMX / SSE1/2/3/4/5/+. Выражения над векторами там писать, к несчастью, нельзя, потому и получается код типа: