13 521
правка
Изменения
м
<big>Или '''Применение «Применение обобщенного спектрально-аналитического метода в задаче анализа биологических данных — План презентацииданных»'''</big>.
Идея: Идея — применить ОСАМ к поиску повторов в ДНК, таким образом ускорив его. Как?! Во-первых, <nowiki>построить профиль последовательности, т. е. перевести её в длинный числовой вектор, выбрав w — w — окно профиля, и принимая за каждый элемент последовательности ''(количество пуринов в w-окрестности элемента) минус (количество пиримидинов в w-окрестности элемента)''. Далее, выбирая по N значений из полученной последовательности — последовательности — <m>(0..\ldots N-1), (s..\ldots N+s-1), (2s..\ldots N+2s-1), … \ldots</m> (s — s — шаг аппроксимации) и раскладывая получаемые вектора из N чисел по k коэффициентам некоторого базиса, получить «индекс» последовательности. k << N, потому и «индекс». Далее пробежаться по всем полученным описаниям (по индексу) индексам обеих последовательностей (или одной и той же последовательности) и сравнить попарно все пары описаний (на похожесть). А что такое похожесть? Критериев похожести можно выработать массу, среди них можно найти устойчивые к масштабу и т. п., однако у нас всё довольно просто:</nowiki><mathm>\frac{|a-b|}{|a|+|b|}</mathm>, где <mathm>|x|=\sqrt{\sum {x}_{i}^{2}}</mathm>. Такое вот «нормированное Типа «нормированного L<sub>2</sub>-расстояние»расстояния». Здесь, кстати, можно выиграть от т. н. «принципа дискриминантности», который гласит очевидную вещь: что если <mathm>\frac{\sqrt{{\sum }_{i=0}^{k}{({a}_{i}-{b}_{i})}^{2}}}{|a|+|b|}> \mathrm{eps}varepsilon</math><nowikim>уже при k < n, то суммирование можно не продолжать, т. к. ''меньше '' сумма квадратов уже не станет. Итак, что мы получим от этого сравнения? Мы получим приближённые «близости» участков ДНК. Крупных или мелких, более или менее точное сравнение — это уже как захотим — для этого можно варьировать параметры. Задаём порог, можем пробежаться по результатам и сразу выявить «подозрительные на повторы» участки. Это есть важно, т. к. больше не нужно всё время искать повторы ВЕЗДЕ: сначала достаточно выявить крупные относительно похожие участки, а потом можно «увеличить масштаб» и выявить (или не выявить) точные координаты повторов. Кстати, единственное, для чего подход почти не подходит - для выявления «абсолютно точных» координат повторов. Это уже в «подозрительных» областях можно делать стандартными методами. Например, diffоподобным алгоритмом. :-)</nowiki>
КстатиИтак, от этого сравнения мы получим оценку «подобия» участков ДНК. Крупных или мелких, более или менее точное сравнение — это уже как захотим — для этого можно варьировать параметры. Задаём порог, можем пробежаться по результатам и сразу выявить участки, «подозрительные на повторы». То есть больше не нужно использовать все современные возможности процессороввсё время искать повторы «''везде''»: сначала достаточно выявить крупные относительно похожие участки, а потом можно «увеличить масштаб» и выявить (или не выявить) точные координаты повторов. Иначе будет обидноЕдинственное, если такую же программу написать для чего подход почти не подходит — для выявления «абсолютно точных» координат повторов. Это уже в «подозрительных» областях можно делать стандартными методами. Например, diff'оподобными алгоритмами. == Часть статьи == Для реализации программы поиска повторов с помощью ОСАМ был выбран язык C++. Такой выбор обусловлен сущностью процесса разложения функций, позволяющей с помощью объектно-ориентированного подхода разделить функционал на MATLAB’е общий и она — опа! — окажется быстрее зависящий от конкретного ортогонального базиса. Общий функционал — это функции подсчёта весовых коэффициентов, подсчёта интеграла на сетке Гаусса, подсчёта матрицы Грама заданного базиса, нормирования заданного базиса, интерполяции сигнала на заданную сетку, и воссоздания изначального сигнала по коэффициентам разложения. К базисо-зависимому функционалу относятся функции подсчёта сетки, весовых коэффициентов, и самих значений функции. Также такой подход, кроме всего прочего, даёт возможность оптимизировать части функционала отдельно друг от друга. === «Наивный» алгоритм === В целом основная задача программного обеспечения поиска повторов на основе ОСАМ — построение спектральной матрицы гомологии последовательности, в 5 разобщем случае — двух последовательностей. При сравнении двух последовательностей каждый элемент спектральной матрицы гомологии отражает оценку подобия соответствующих участков последовательностей. Также последовательность можно сравнивать с самой собой. Простейший «наивный» вариант алгоритма построения матрицы гомологии: * Загрузить входные файлы последовательностей.* По всем подпоследовательностям 1-ой последовательности:** Подсчитать коэффициенты разложения подпоследовательности по выбранному ОНБ.** Вычислить норму вектора коэффициентов.** По всем подпоследовательностям 2-ой последовательности:*** Подсчитать коэффициенты разложения подпоследовательности 2-ой последовательности по выбранному ОНБ.*** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.*** Подсчитать L<sub>2</sub>-расстояние между векторами коэффициентов разложения подпоследовательностей.*** Поделить подсчитанное расстояние на сумму норм векторов коэффициентов.*** Сохранить подсчитанное значение как (i, j)-ый элемент матрицы гомологии.* Записать матрицу гомологии в выходной файл. Подготовительный этап: * Подсчитать сетку Гаусса (то есть, корни n+1-ой функции базиса).* Подсчитать весовые и нормировочные коэффициенты. === Алгоритм разложения === «Наивный» вариант алгоритма разложения: * Интерполировать выбранную подпоследовательность длины N > n на подсчитанную сетку алгоритмом «ближайшего соседа».: То есть нужно , по сути, не забывать о многопоточностиинтерполировать её никак. Практика показала, что любая предварительная интерполяция никак не забывать об улучшает разложение по причине большой плотности точек в исходном сигнале и маленькой — в раскладываемом массиве.* Подсчитать в цикле <m>c_j = \sum_{i=1}^{n} y_i \cdot w_i \cdot f_j(x_i) \cdot r_j, j=1 \ldots n</m>, где:: <m>c_j</m> — j-ый коэффициент разложения сигнала <m>y_i</m>.: <m>w_i</m> — i-ый весовой коэффициент.: <m>f_j(x_i)</m> — значение j-ой функции базиса в i-ой точке сетки.: <m>r_j</m> — j-ый нормировочный коэффициент. Оптимизированный для рекуррентных соотношений алгоритм разложения: * Интерполировать выбранную подпоследовательность длины N > n на подсчитанную сетку алгоритмом «ближайшего соседа».* В цикле по ''i = 1..n'':** <m>c_i = 0</m>* В цикле по ''i = 1..n'':** Вычислить и сохранить в памяти все значения <m>f_j(x_i), j = 1 \ldots n</m> с помощью рекуррентных соотношений.** В цикле по ''j = 1..n'':*** <m>c_j = c_j + y_i \cdot f_j(x_i) \cdot r_j \cdot w_i</m> Псевдокод оптимизированного с учётом векторных операций алгоритма разложения здесь не приведён по причине его объёма. Кратко можно описать два момента: во-первых, циклы сменены местами — внешний цикл идёт по коэффициентам разложения, а не по функциям базиса, и во-вторых, на всех этапах используются векторные операции — сложения, умножения, возведения в квадрат и т. п. === Оптимизация === При реализации системы поиска повторов в виде программы учитывалась необходимость использования всех современных возможностей процессоров — ведь нужно понимать, что в наше время процессоры уже давно не i386, все суперскалярные, поддерживающие многопоточность, SIMD инструкциях-инструкции (Single Instruction, Multiple Data) — инструкции, позволяющие за один такт выполнить несколько одинаковых операций сразу, аппаратно ускоренные математические функции и другие возможности поднятия производительности. Также не следует забывать об аппаратном ускорении , что большинство из этих возможностей успешно используется математическими пакетами вроде Matlab и Maple, популярными при тестировании и исследованиях математических функцийметодов. Засчёт этого всего выигрываем Поэтому, если забыть об этих возможностях в программе, можно испытать разочарование от скорости ещё большеработы по сравнению с той же программой, реальная разница — реализованной с помощью математического пакета. К счастью, общий алгоритм разложения дискретизированных сигналов по классическим ортогональным базисам, являющийся просто алгоритмом вычисления соответствующего интеграла Гаусса, весьма прост и допускает оптимизацию также с помощью простых методов. Кроме того, ОСАМ позволяет и производить практически идеальное распараллеливание алгоритма по причине небольшого объёма необходимой памяти в случае, если не используется т. н. «индексация последовательности» — такой подход может быть полезен при вычислениях с массовым параллелизмом. ''Индексацией'' называется процесс предварительного разложения сравниваемой последовательности по выбранному ортогональному базису и сохранения в памяти всех векторов коэффициентов разложения для последующего использования. Достоинство индексации — отсутствие необходимости производить большой объём вычислений во вложенном цикле; её недостаток — существенное увеличение объёма используемой оперативной памяти и увеличение требований к пропускной способности памяти. Последнее особенно важно при массивно-параллельных вычислениях — отдельные процессоры, ядра или узлы кластера могут вообще не иметь общего доступа ко всей оперативной памяти системы, не говоря уже о существенном замедлении обмена данных между вычислителями и памятью в случае конкуретной работы с большой области памяти. Такая проблема присутствует даже на многоядерных стандартных настольных компьютерах и серверах нижнего класса — оперативная память обычно работает приблизительно со скоростью, равной четверти скорости процессоров и, начиная с определённого количества ядер/процессоров, индексация становится менее выгодной, чем могла бы быть, так как чипсет и оперативная память не могут обеспечить требуемую скорость обмена. Тем не менее, на обычных ПК и серверах нижнего класса наличие индексации хотя бы одной последовательности всё равно выгодно, поэтому при реализации был выбран следующий подход: индексация одной последовательности и разложение второй на лету. Соответственно, в любом случае — как в случае сравнения последовательности с самой собой, так и в случае сравнения двух последовательностей — вычисления коэффициентов разложения последовательностей происходят только 1 раз: первой при индексации, а второй во внешнем цикле. Реальный выигрыш в производительности засчёт чисто программной оптимизации достигает 10-20 раз (на стандартных двухъядерных процессорах архитектуры Core 2 Duo). Как?! Для многопоточности — голые нити Очевидными вариантами достижения параллелизма в алгоритме поиска повторов являются библиотека OpenMP и ручная реализация распараллеливания на основе потоков — в UNIX-среде pthreads (тредыPOSIX threads — потоки POSIX), никаких а в Windows-среде функций WINAPI. Можно было бы предположить, что использование библиотеки OpenMP! Так упростит переносимость программы, однако, при переопределении всего лишь двух функций — создания потока и ожидания завершения потока (т. н. «join») — ручной подход достигает в точности такой же идеальной переносимости программы. Собственно говоря, функции создания потока и ожидания завершения потока являются настолько базовыми в любой библиотеке работы с потоками на любой платформе, поддерживающей потоки, что при реализации можно не бояться их потенциального отсутствия, тем более, когда на дворе 2009-ый год. Вместе с тем как это костылистая штуковинараз реализация OpenMP потенциально существует не для всех ОС. Главным же минусом библиотеки OpenMP является то, приводит что её работа построена на директивах компилятора, и в итоге транслируется обычно в код, постоянно создающий и завершающий вычислительные потоки, для каждой итерации распараллеливаемого цикла. Таким образом при использовании OpenMP либо к сильному ухудшению структуры кода приходится учитывать такое поведение, распараллеливая циклы с небольшими (причём фактическая логика получается аналогична голым тредампо крайней мере, относительно)количествами итераций, либо ухудшая структуру кода и фактически сводя его логику к большим накладным расходам логике ручного распараллеливания, либо мириться с накладными расходами на распараллеливание — распараллеливание, в нашем случае достигавшими 5-15 %. Так что треды Таким образом, для параллелизма использовалось ручное разделение задачи на подзадачи и ручное управление вычислительными потоками. Плюс Для использования аппаратно-ускоренных и векторных (SIMD) инструкций использовалась библиотека Intel ''Integrated Performance Primitives для SIMD и аппаратного ускорения инструкций. А что это — '' (IPP? А это такой векторный ассемблер, только на C). БиблиотекаБлижайшая сравнение IPP — «векторный язык ассемблера», содержащая в себе оптимальные реализации большого спектра векторных операций (есть почти всёсодержащий простые ''векторные'' «инструкции», что душе угодно — а точнее оптимизированные функции-обёртки, для весьма широкого спектра задач — от сложений, умножений, корней и синусов, до узкоспециализированных функций ускорения декодирования аудио и видео, распознавания речи и ти т.д и т п.п) для Библиотека IPP даёт преимущества при использовании любых x86-процессоров, имеющих различные расширения типа наборов команд MMX / SSE1/2/3/4/5/+, SSE, SSE2, SSE3 и т. Выражения п. Нужно отметить, что IPP сравнима в первую очередь действительно с языком ассемлера, так как не поддерживает трансляцию выражений над векторами там писать, к несчастьюа только сами операции, нельзяреализованные в виде функций (аналог инструкций). Это, потому и получается код типак сожалению, приводит к неочевидному «ассемблерному» коду следующего вида:
Вот где-то примерно это всё и было реализованоИ последний важный момент — принцип «дискриминантности». Есть относительно простая программаНапомним, есть относительно хорошая библиотека для абстрагирования от деталей реализации конкретных базисовчто расстояние между двумя векторами коэффициентов разложения определяется как <m>\frac{|a-b|}{|a|+|b|}</m>, есть сами базисы — Чебышева 1 и где <m>|x|=\sqrt{\sum {x}_{i}^{2 рода}}</m> Принцип «дискриминантности» же гласит очевидную вещь: если <m>\frac{\sqrt{{\sum }_{i=0}^{k}{({a}_{i}-{b}_{i})}^{2}}}{|a|+|b|}> \varepsilon</m> уже при k < n, Якобисуммирование можно не продолжать, Лежандра, Лагерра, Эрмита, Фурье, ДКП, ДСПт. Она работает и рисует красивые картинкик. [показать пару картинок и закончить]''меньше'' ε сумма квадратов уже не станет. КстатиЭта идея также использовалась при оптимизации алгоритма. Однако здесь возникает определённое препятствие: суммирование с постоянными условными проверками не векторизуется, по поводу того, а какой же базис лучше? Вообще они все дают очень похожие результаты… Пока что «лучше» всех Чебышев 1-го родат. А что вообще такое «лучше»? «Лучше» — чисто умозрительно это «больше соотношение сигнал/шум» (в результатах)е. Как измерить? Ну, например, при одинаковых параметрах окон и глубине разложения подобрать eps такоеподсчёте нормы с учётом принципа "дискриминантности" IPP использовать мы уже не можем. Но так как IPP даёт весьма неплохой прирост производительности, чтобы общее количество «похожих» участков было примерно равноможно применить следующий нетривиальный ход: сначала суммировать до ''k = d'', и посчитатьгде d - делитель n, напримербольший 1, среднюю длину повторов. Можно и медиану тоже. Чем больше, тем лучше — мы ведь хотим найти как можно более длинные повторы. Начинали реализовывать с Чебышева 1-го родаиспользованием векторных операций, потом пробовали Лежандрапроверять, не превышен ли порог, потом думалидо ''k = 2d'', что Чебышев 2-го рода произведёт революцию и всё будет гораздо лучшепотом до ''k = 3d'', и т.к весовая функция выпуклая, центр отрезка учитывается сильнее, края меньшед. Революции не произошло, результаты сильно похожие на === Алгоритм с учётом индексации === С учётом выбранного подхода — индексации одной последовательности и разложения другой «на лету» — алгоритм принимает следующий вид: * Загрузить входные файлы последовательностей.* ''Подсчитать и сохранить в памяти коэффициенты разложения всех подпоследовательностей 1-го рода, местами получше, местами похужеой последовательности по выбранному ОНБ. Формально — похуже''* ''Подсчитать и сохранить в памяти нормы всех векторов коэффициентов разложения этих подпоследовательностей. Дальше есть табличка с «попугаями» ''* По всем ''сохранённым коэффициентам разложения подпоследовательностей'' 1-ой последовательности:** По всем подпоследовательностям 2-ой последовательности:*** Подсчитать коэффициенты разложения подпоследовательности 2-ой последовательности по разным базисамвыбранному ОНБ. Тестовые данные — часть генома мыши *** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.*** Подсчитать L<sub>2</sub>-расстояние между векторами коэффициентов разложения подпоследовательностей.*** Поделить подсчитанное расстояние на сумму норм векторов коэффициентов.*** Сохранить подсчитанное значение как (не спрашивайте какаяi, я не знаюj) длиной 1-ый элемент матрицы гомологии.5 млн нуклеотидов* Записать матрицу гомологии в выходной файл. Сравнение приводилось при примерно одинаковых количествах найденных участков, «подозрительных» === Алгоритм с учётом параллелизма === Изменения с учётом параллелизма тривиальны: наиболее внешние циклы разделяются на повтор — в районе 5000''M'' частей и для обработки каждой части работы создаётся собственный поток. При выбранных настройках минимальная длина участкаДалее главный поток приложения ожидает завершения всех созданных, подозрительного на повтор — 3500 нуклеотидовт. Какие выводы? Лидирует Чебышев 1 родае. Базисы ДКП, ДСП и Фурье дают до жути похожие на негоожидает окончания очередного этапа работы. * Загрузить входные файлы последовательностей.* ''Создать требуемое число M вычислительных потоков, практически идентичныедалее, результатыдля каждого из них:''** ''Подсчитать и сохранить в памяти коэффициенты разложения своей <m>\frac{1}{M}</m>-ой части подпоследовательностей 1-ой последовательности по выбранному ОНБ. С небольшим отставанием за ними следует Лежандр''** ''Подсчитать и сохранить в памяти нормы своей <m>\frac{1}{M}</m>-ой части векторов коэффициентов разложения этих подпоследовательностей.''* ''Создать требуемое число M вычислительных потоков, за ним — Чебышев 2 родадалее, а базисы Эрмита и Лагерра не подходят для поиска повторов каждого из них:''вообще — ** ''что есть логичный факт, тПо своей <m>\frac{1}{M}</m>-ой части сохранённых коэффициентов разложения подпоследовательностей 1-ой последовательности'':*** По всем подпоследовательностям 2-ой последовательности:**** Подсчитать коэффициенты разложения подпоследовательности 2-ой последовательности по выбранному ОНБ. к**** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.**** Подсчитать L<sub>2</sub>-расстояние между векторами коэффициентов разложения подпоследовательностей. они оба работают **** Поделить подсчитанное расстояние на бесконечном интервале либо сумму норм векторов коэффициентов.**** Сохранить подсчитанное значение как (0i, +бесконечностьj), либо от — до + бесконечности-ый элемент матрицы гомологии. Вариантов значения медианной длины было всего 2: 3500 (минимально возможная) или 10000, она отражает, фактически, чистое количество шума — мелких отрезков, и гласит, что приемлемый уровень шума дают… Ясно кто* Записать матрицу гомологии в выходной файл.
{| style="border-spacing:0;"| style="border-top:0.002cm solid #000000;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"|| style="border-top:0.002cm solid #000000;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| Eps| styleСравнение векторов с учётом векторных операций и дискриминантности =="border-top:0.002cm solid #000000;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| Среднее| style="border:0.002cm solid #000000;padding:0.097cm;"| Медиана
|-| style* Вычислить относительный порог <m>l ="border-top:none;border-bottom:0(\varepsilon \cdot (s_1 + s_2))²</m>, где s<sub>1</sub> и s<sub>2</sub> — нормы векторов.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| Чебышева 1 рода| style* Начальное значение ''f ="border-top:none;border-bottom:0''.002cm solid #000000;border-left* В цикле:0.002cm solid #000000;border-right:none;padding:0.097cm;"| .025| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| ** С помощью функции IPP <code>ippsNormDiffL2_64f</code> (или 32f, в зависимости от требуемой точности) вычислить норму разности очередных участков длины ''d'3978'сравниваемых векторов.** Добавить к ''| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:0.002cm solid #000000;padding:0.097cm;"| f''квадрат полученного значения.** Если '10000'f > l'', принять, что вектора «не подобны».* Если цикл завершился без принятия того, что вектора «не подобны», принять, что вектора подобны.
|-| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| Чебышева 2 рода| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| .0285| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| 3882| styleСравнение ОНБ ==="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:0.002cm solid #000000;padding:0.097cm;"| 3500
|-| style="border-topУчитывая, что поиск повторов может осуществляться по выбору с использованием любого из ортогональных базисов, и что в библиотеке функций разложения их было реализовано 9 различных — базис Чебышева 1 рода, базис Чебышева 2 рода, дискретные косинусное и синусное преобразования, базис Фурье, базис Лежандра, базис Лагерра, базис Якоби и базис Эрмита — очевидным образом встаёт вопрос:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| ДКП| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| .025| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| '''3978'''| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:0.002cm solid #000000;padding:0.097cm;"| '''10000'''а какой же из них «лучше» в задаче поиска повторов в последовательностях? А кроме того, каковы в целом критерии качества, по которым требуется производить сравнение базисов?
|-| style="border-top:none;border-bottom:0Очевидным подходом к данному вопросу является критерий «максимум соотношения сигнал/шум в найденных в итоге повторах».002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| ДСП| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| .021| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| 3975| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:0.002cm solid #000000;padding:0.097cm;"| '''10000'''
|-| style="border-top:none;border-bottom:0Другой вариант — максимум средней длины найденных подобных участков, так как цель поиска повторов заключается в том, чтобы найти как можно более длинные подобные участки.002cm solid #000000;border-left:0Как можно оценить эту длину? Опишем простейший подход.002cm solid #000000;borderВо-right:none;padding:0.097cm;"| Фурье| style="borderпервых, нужно выбрать ширину скользящих окон и глубину разложения и выбрать некоторые тестовые данные, содержащие широкий спектр различных повторов — здесь хорошо подходит часть реальной ДНК-top:none;border-bottom:0последовательности.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| .025| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| '''3978'''| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:0Далее, используя различные базисы и подбирая порог сравнения (<m>\varepsilon</m>) такой, чтобы общее число найденных подобных участков было приблизительно равно, подсчитывать среднюю длину найденных подобных участков.002cm solid #000000;padding:0Как вариант — можно вычислять медианное значение.097cm;"| '''10000'''
|В процессе реализации программы вначале был выбран базис Чебышева 1-| style="border-top:noneго рода;border-bottom:0потом пробовали базис Лежандра.002cm solid #000000;borderПотом было высказано предположение о том, что базис Чебышева 2-left:0.002cm solid #000000;borderго рода произведёт «революцию» по той причине, что имеет выпуклую весовую функцию и сильнее учитывает центр сравниваемого отрезка, чем края, но революции не произошло, результаты базиса Чебышева 2-right:none;padding:0.097cm;"| Эрмита| style="borderго рода сильно похожи на базис Чебышева 1-top:none;border-bottom:0го рода, и даже немного хуже, в том числе и по средней длине найденных повторов.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| .0015| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| 3502| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:0.002cm solid #000000;padding:0.097cm;"| 3500
|-| style="border-top:none;border-bottom:0Ниже приводится табличка с замерами средней длины найденных повторов на различных базисах и части генома мыши длиной 1.002cm solid #000000;border-left:05 млн нуклеотидов в качестве тестовых данных.002cm solid #000000;border-right:none;padding:0Сравнение производилось при приблизительно равных количествах найденных «подобных» участков — 5000.097cm;"| Лагерра| style="border-top:none;border-bottom:0При выбранных настройках минимально возможная найденная длина подобного участка — 3500 нуклеотидов.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| .0063| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;"| 3505| style="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:0.002cm solid #000000;padding:0.097cm;"| 3500
|-| style<tab sep="tab"border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;="| Лежандра| style1" class="border-top:none;border-bottom:0.002cm solid #000000;border-left:0.002cm solid #000000;border-right:none;padding:0.097cm;simpletable"| .0225| stylehead="bordertopleft">-top:none;border-bottom:0Eps Среднее МедианаЧебышева 1 рода .002cm solid #000000;border-left:0025 '''3978''' '''10000'''Чебышева 2 рода .002cm solid #000000;border-right:none;padding:00285 3882 3500ДКП .097cm;"| 3966025 '''3978''' '''10000'''| style="border-top:none;border-bottom:0ДСП .002cm solid #000000;border-left:0021 3975 '''10000'''Фурье .002cm solid #000000;border-right:0025 '''3978''' '''10000'''Эрмита .002cm solid #000000;padding:00015 3502 3500Лагерра .097cm;"| 0063 3505 3500Лежандра .0225 3966 '''10000'''</tab>
|}Каковы выводы? По средней длине повтора лидирует базис Чебышев 1 рода, а базисы ДКП, ДСП и Фурье дают чрезвычайно похожие на него, практически идентичные, результаты. С небольшим отставанием следует базис Лежандра, далее — базис Чебышева 2 рода, а базисы Эрмита и Лагерра для поиска подобных участков не подходят вообще, чему есть простое математическое обоснование — оба они действуют на бесконечной полупрямой — либо <m>(0, +\inf)</m>, либо <m>(-\inf, +\inf)</m>. Вариантов значения медианной длины при этом было всего 2: 3500 (минимально возможная) или 10000. Медианная длина в данном случае отражает, фактически, «чистое» количество шума — мелких отрезков, и гласит, что приемлемый уровень шума дают базисы Чебышева 1 рода, ДКП, ДСП, Фурье и Лежандра.
Нет описания правки
Ключевая задача анализа геномных последовательностей: поиск повторов. Прямых, обратных, симметричных. Что есть геномная последовательность? По сути, длинная строка в алфавите A, T, G, C (аденин, тимин, гуанин, цитозин, цитозин — привет, биология, за 10-й класс). T и C близки, это «пиримидины»«[[rupedia:Пиримидин|пиримидиновые]] основания». G и A тоже близки, это «пурины»«[[rupedia:Пурин|пуриновые]] основания». Методов куча, но есть и '''Проблема: последовательности очень длинныеПоследовательности Очень Длинные''', анализ долгий. Если искать точные повторы, ещё более-менее, но как только переходим к поиску неточных повторов, всё сразу всё сильно замедляется. По поводу «обычных» методов — например, можно посмотреть программу UniPro DPView — творение неких Новосибирских коллег. Ещё есть довольно адские и адовые проекты [http://www.bioperl.org/ BioPerl], BioPython — [http://www.biopython.org/ BioPython] — большие сборники всяких различных методов и библиотек по поводу решения биологических задач, задач — в частности, и методов поиска повторов, на скриптовых языках.
'''ОСАМ. ''' Мысль простаяпроста: разложить сигнал по какому-нибудь классическому ортогональному базису, получить краткое описание, к тому же обладающее различными приятными свойствами. Обработать на основе описания сигнала. Применять можно в широком спектре задач распознавания. Свойства описания — «более важная» информация в первых коэффициентах(норма сохраняется; отсекая хвост, можно получать получаем приближения сигнала; норма сохраняется; для неточных разложений есть мера точности разложения; ) и т. п. Т. е. есть хорошийобработать не сигнал, проработанный, мата описание. аппаратПрименим в широком спектре задач распознавания.
ippsCopy_64f(xn, wn, n);
ippsSqrt_64f_I(tn, n);
[[Категория:УчёбаСтатьи]][[Категория:Биоинформатика]]