Изменения

<big>Или '''Применение «Применение обобщенного спектрально-аналитического метода в задаче анализа биологических данных — План презентацииданных»'''</big>.

Ключевая задача анализа геномных последовательностей: поиск повторов. Прямых, обратных, симметричных. Что есть геномная последовательность? По сути, длинная строка в алфавите A, T, G, C (аденин, тимин, гуанин, цитозин, цитозин — привет, биология, за 10-й класс). T и C близки, это «пиримидины»«[[rupedia:Пиримидин|пиримидиновые]] основания». G и A тоже близки, это «пурины»«[[rupedia:Пурин|пуриновые]] основания». Методов куча, но есть и '''Проблема: последовательности очень длинныеПоследовательности Очень Длинные''', анализ долгий. Если искать точные повторы, ещё более-менее, но как только переходим к поиску неточных повторов, всё сразу всё сильно замедляется. По поводу «обычных» методов — например, можно посмотреть программу UniPro DPView — творение неких Новосибирских коллег. Ещё есть довольно адские и адовые проекты [http://www.bioperl.org/ BioPerl], BioPython — [http://www.biopython.org/ BioPython] — большие сборники всяких различных методов и библиотек по поводу решения биологических задач, задач — в частности, и методов поиска повторов, на скриптовых языках.

'''ОСАМ. ''' Мысль простаяпроста: разложить сигнал по какому-нибудь классическому ортогональному базису, получить краткое описание, к тому же обладающее различными приятными свойствами. Обработать на основе описания сигнала. Применять можно в широком спектре задач распознавания. Свойства описания — «более важная» информация в первых коэффициентах(норма сохраняется; отсекая хвост, можно получать получаем приближения сигнала; норма сохраняется; для неточных разложений есть мера точности разложения; ) и т.&nbsp;п. Т.&nbsp;е. есть хорошийобработать не сигнал, проработанный, мата описание. аппаратПрименим в широком спектре задач распознавания.

Идея: Идея — применить ОСАМ к поиску повторов в ДНК, таким образом ускорив его. Как?! Во-первых, <nowiki>построить профиль последовательности, т.&nbsp;е. перевести её в длинный числовой вектор, выбрав 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, потому и «индекс». Далее пробежаться по всем полученным описаниям (по индексу) индексам обеих последовательностей (или одной и той же последовательности) и сравнить попарно все пары описаний (на похожесть). А что такое похожесть? Критериев похожести можно выработать массу, среди них можно найти устойчивые к масштабу и т.&nbsp;п., однако у нас всё довольно просто:</nowiki><mathm>\frac{|a-b|}{|a|+|b|}</mathm>, где <mathm>|x|=\sqrt{\sum {x}_{i}^{2}}</mathm>. Такое вот «нормированное Типа «нормированного L₂-расстояние»расстояния». Здесь, кстати, можно выиграть от т.&nbsp;н. «принципа дискриминантности», который гласит очевидную вещь: что если <mathm>\frac{\sqrt{{\sum }_{i=0}^{k}{({a}_{i}-{b}_{i})}^{2}}}{|a|+|b|}> \mathrm{eps}varepsilon</math><nowikim>уже при k < n, то суммирование можно не продолжать, т.&nbsp;к. ''меньше '' сумма квадратов уже не станет. Итак, что мы получим от этого сравнения? Мы получим приближённые «близости» участков ДНК. Крупных или мелких, более или менее точное сравнение — это уже как захотим — для этого можно варьировать параметры. Задаём порог, можем пробежаться по результатам и сразу выявить «подозрительные на повторы» участки. Это есть важно, т.&nbsp;к. больше не нужно всё время искать повторы ВЕЗДЕ: сначала достаточно выявить крупные относительно похожие участки, а потом можно «увеличить масштаб» и выявить (или не выявить) точные координаты повторов. Кстати, единственное, для чего подход почти не подходит - для выявления «абсолютно точных» координат повторов. Это уже в «подозрительных» областях можно делать стандартными методами. Например, diffоподобным алгоритмом. :-)</nowiki>

КстатиИтак, от этого сравнения мы получим оценку «подобия» участков ДНК. Крупных или мелких, более или менее точное сравнение — это уже как захотим — для этого можно варьировать параметры. Задаём порог, можем пробежаться по результатам и сразу выявить участки, «подозрительные на повторы». То есть больше не нужно использовать все современные возможности процессороввсё время искать повторы «''везде''»: сначала достаточно выявить крупные относительно похожие участки, а потом можно «увеличить масштаб» и выявить (или не выявить) точные координаты повторов. Иначе будет обидноЕдинственное, если такую же программу написать для чего подход почти не подходит — для выявления «абсолютно точных» координат повторов. Это уже в «подозрительных» областях можно делать стандартными методами. Например, diff'оподобными алгоритмами. == Часть статьи == Для реализации программы поиска повторов с помощью ОСАМ был выбран язык C++. Такой выбор обусловлен сущностью процесса разложения функций, позволяющей с помощью объектно-ориентированного подхода разделить функционал на MATLAB’е общий и она — опа! — окажется быстрее зависящий от конкретного ортогонального базиса. Общий функционал — это функции подсчёта весовых коэффициентов, подсчёта интеграла на сетке Гаусса, подсчёта матрицы Грама заданного базиса, нормирования заданного базиса, интерполяции сигнала на заданную сетку, и воссоздания изначального сигнала по коэффициентам разложения. К базисо-зависимому функционалу относятся функции подсчёта сетки, весовых коэффициентов, и самих значений функции. Также такой подход, кроме всего прочего, даёт возможность оптимизировать части функционала отдельно друг от друга. === «Наивный» алгоритм === В целом основная задача программного обеспечения поиска повторов на основе ОСАМ — построение спектральной матрицы гомологии последовательности, в 5 разобщем случае — двух последовательностей. При сравнении двух последовательностей каждый элемент спектральной матрицы гомологии отражает оценку подобия соответствующих участков последовательностей. Также последовательность можно сравнивать с самой собой. Простейший «наивный» вариант алгоритма построения матрицы гомологии: * Загрузить входные файлы последовательностей.* По всем подпоследовательностям 1-ой последовательности:** Подсчитать коэффициенты разложения подпоследовательности по выбранному ОНБ.** Вычислить норму вектора коэффициентов.** По всем подпоследовательностям 2-ой последовательности:*** Подсчитать коэффициенты разложения подпоследовательности 2-ой последовательности по выбранному ОНБ.*** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.*** Подсчитать L₂-расстояние между векторами коэффициентов разложения подпоследовательностей.*** Поделить подсчитанное расстояние на сумму норм векторов коэффициентов.*** Сохранить подсчитанное значение как (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₂-расстояние между векторами коэффициентов разложения подпоследовательностей.*** Поделить подсчитанное расстояние на сумму норм векторов коэффициентов.*** Сохранить подсчитанное значение как (не спрашивайте какая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-ой последовательности по выбранному ОНБ.&nbsp;к**** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.**** Подсчитать L₂-расстояние между векторами коэффициентов разложения подпоследовательностей. они оба работают **** Поделить подсчитанное расстояние на бесконечном интервале либо сумму норм векторов коэффициентов.**** Сохранить подсчитанное значение как (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₁ и s₂ — нормы векторов.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>

[[Категория:УчёбаСтатьи]][[Категория:Биоинформатика]]