Изменения

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

Ключевая задача анализа геномных последовательностей: поиск Идея — применить ОСАМ к поиску повторов. Прямых, обратныхв ДНК, симметричныхтаким образом ускорив его. Что есть геномная последовательностьКак? По сути! Во-первых, длинная строка построить профиль последовательности, т.&nbsp;е. перевести её в алфавите Aдлинный числовой вектор, Tвыбрав w — окно профиля, Gи принимая за каждый элемент последовательности ''(количество пуринов в w-окрестности элемента) минус (количество пиримидинов в w-окрестности элемента)''. Далее, C выбирая по N значений из полученной последовательности — <m>(аденин0 \ldots N-1), тимин(s \ldots N+s-1), гуанин, цитозин, привет, биология, 10(2s \ldots N+2s-й класс1). T и C близки, это «пиримидины». G \ldots</m> (s — шаг аппроксимации) и A тоже близкираскладывая получаемые вектора из N чисел по k коэффициентам некоторого базиса, это «пурины»получить «индекс» последовательности. Методов кучаk << N, но есть потому «индекс». Далее пробежаться по индексам обеих последовательностей (или одной и Проблема: той же последовательности очень длинные, анализ долгий) и сравнить попарно все пары описаний на похожесть. Если искать точные повторыА что такое похожесть? Критериев похожести можно выработать массу, ещё более-менее, но как только переходим среди них можно найти устойчивые к поиску неточных повторовмасштабу и т.&nbsp;п., однако у нас всё сразу сильно замедляется. По поводу «обычных» методов — напримердовольно просто: <m>\frac{|a-b|}{|a|+|b|}</m>, где <m>|x|=\sqrt{\sum {x}_{i}^{2}}</m>. Типа «нормированного L₂-расстояния». Здесь можно посмотреть программу UniPro DPView — творение неких Новосибирских коллегвыиграть от т. Ещё есть довольно адские проекты BioPerl&nbsp;н. «принципа дискриминантности», BioPython — большие сборники всяких методов и библиотек по поводу биологических задачкоторый гласит очевидную вещь: если <m>\frac{\sqrt{{\sum }_{i=0}^{k}{({a}_{i}-{b}_{i})}^{2}}}{|a|+|b|}> \varepsilon</m> уже при k < n, в частностисуммирование можно не продолжать, и методов поиска повторов, на скриптовых языкахт.&nbsp;к. ''меньше'' сумма квадратов уже не станет.

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

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

Вот где-то примерно это всё и было реализовано. Есть относительно простая программа, есть относительно хорошая библиотека для абстрагирования от деталей Для реализации конкретных базисов, есть сами базисы — Чебышева 1 и 2 рода, Якоби, Лежандра, Лагерра, Эрмита, Фурье, ДКП, ДСПпрограммы поиска повторов с помощью ОСАМ был выбран язык C++. Она работает и рисует красивые картинки. [показать пару картинок и закончить]. Кстати, по поводу того, а какой же базис лучше? Вообще они все дают очень похожие результаты… Пока что «лучше» всех Чебышев 1-го рода. А что вообще такое «лучше»? «Лучше» — чисто умозрительно это «больше соотношение сигнал/шум» (в результатах). Как измерить? Ну, например, при одинаковых параметрах окон и глубине Такой выбор обусловлен сущностью процесса разложения подобрать eps такоефункций, чтобы общее количество «похожих» участков было примерно равно, и посчитать, например, среднюю длину повторов. Можно и медиану тоже. Чем больше, тем лучше — мы ведь хотим найти как можно более длинные повторы. Начинали реализовывать позволяющей с Чебышева 1помощью объектно-го рода, потом пробовали Лежандра, потом думали, что Чебышев 2-го рода произведёт революцию ориентированного подхода разделить функционал на общий и всё будет гораздо лучше, тзависящий от конкретного ортогонального базиса.к весовая функция выпуклая, центр отрезка учитывается сильнее, края меньше. Революции не произошлоОбщий функционал — это функции подсчёта весовых коэффициентов, результаты сильно похожие подсчёта интеграла на 1-го родасетке Гаусса, местами получшеподсчёта матрицы Грама заданного базиса, местами похуже. Формально — похуже. Дальше есть табличка с «попугаями» по разным базисам. Тестовые данные — часть генома мыши (не спрашивайте какаянормирования заданного базиса, я не знаю) длиной 1.5 млн нуклеотидов. Сравнение приводилось при примерно одинаковых количествах найденных участков, «подозрительных» интерполяции сигнала на повтор — в районе 5000. При выбранных настройках минимальная длина участказаданную сетку, подозрительного на повтор — 3500 нуклеотидов. Какие выводы? Лидирует Чебышев 1 рода. Базисы ДКП, ДСП и Фурье дают до жути похожие на него, практически идентичные, результатывоссоздания изначального сигнала по коэффициентам разложения. С небольшим отставанием за ними следует ЛежандрК базисо-зависимому функционалу относятся функции подсчёта сетки, за ним — Чебышев 2 родавесовых коэффициентов, а базисы Эрмита и Лагерра не подходят для поиска повторов ''вообще — ''что есть логичный факт, тсамих значений функции.&nbsp;к. они оба работают на бесконечном интервале либо (0Также такой подход, +бесконечность), либо от — до + бесконечности. Вариантов значения медианной длины было кроме всего 2: 3500 (минимально возможная) или 10000прочего, она отражает, фактически, чистое количество шума — мелких отрезков, и гласит, что приемлемый уровень шума дают… Ясно ктодаёт возможность оптимизировать части функционала отдельно друг от друга.

<tab sep="tab" border="1">- Eps Среднее МедианаЧебышева 1 рода .025 '''3978''' '''10000'''Чебышева 2 рода .0285 3882 3500ДКП .025 '''3978''' '''10000'''ДСП .021 3975 '''10000'''Фурье .025 '''3978''' '''10000'''Эрмита .0015 3502 3500Лагерра .0063 3505 3500Лежандра .0225 3966 '''10000'''</tab>= «Наивный» алгоритм ===

Для реализации программы В целом основная задача программного обеспечения поиска повторов с помощью ОСАМ был выбран язык C++. Такой выбор обусловлен сущностью процесса разложения функций, позволяющей с помощью объектно-ориентированного подхода разделить функционал на общий и зависящий от конкретного ортогонального базиса. Общий функционал — это функции подсчёта весовых коэффициентов, подсчёта интеграла на сетке Гаусса, подсчёта основе ОСАМ — построение спектральной матрицы Грама заданного базисагомологии последовательности, нормирования заданного базиса, интерполяции сигнала на заданную сетку, и воссоздания изначального сигнала по коэффициентам разложенияв общем случае — двух последовательностей. К базисо-зависимому функционалу относятся функции подсчёта сетки, весовых коэффициентов, и самих значений функцииПри сравнении двух последовательностей каждый элемент спектральной матрицы гомологии отражает оценку подобия соответствующих участков последовательностей. Также такой подход, кроме всего прочего, даёт возможность оптимизировать части функционала отдельнопоследовательность можно сравнивать с самой собой.

Простейший «наивный» вариант алгоритма построения матрицы гомологии: * Загрузить входные файлы последовательностей.* По всем подпоследовательностям 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 раз: первой при индексации, а второй во внешнем цикле.

Главным же минусом библиотеки OpenMP является то, что её работа построена на директивах компилятора, и в итоге транслируется обычно в код, постоянно создающий и завершающий вычислительные потоки, для каждой итерации распараллеливаемого цикла. Таким образом при использовании OpenMP либо приходится учитывать такое поведенияповедение, распараллеливая циклы с небольшими (по крайней мере, относительно) количествами итераций, ухудшая структуру кода и фактически сводя его логику к логике ручного распараллеливания, либо мириться с накладными расходами на распараллеливание, в нашем случае достигавшими 5-15 %.

И последний важный момент — принцип «дискриминантности». Напомним, что расстояние между двумя векторами коэффициентов разложения определяется как <m>\frac{|a-b|}{|a|+|b|}</m>, где <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, суммирование можно не продолжать, т.к. ''меньше'' ε сумма квадратов уже не станет. Эта идея также использовалась при оптимизации алгоритма. Однако здесь возникает определённое препятствие: суммирование с постоянными условными проверками не векторизуется, т.е., при подсчёте нормы с учётом принципа "дискриминантности" IPP использовать мы уже не можем. Но так как IPP даёт весьма неплохой прирост производительности, можно применить следующий нетривиальный ход: сначала суммировать до ''k = d'', где d - делитель n, больший 1, с использованием векторных операций, потом проверять, не превышен ли порог, потом до ''k = 2d'', потом до ''k = 3d'', и т.д. === Алгоритм с учётом индексации === С учётом выбранного подхода — индексации одной последовательности и разложения другой «на лету» — алгоритм принимает следующий вид: * Загрузить входные файлы последовательностей.* ''Подсчитать и сохранить в памяти коэффициенты разложения всех подпоследовательностей 1-ой последовательности по выбранному ОНБ.''* ''Подсчитать и сохранить в памяти нормы всех векторов коэффициентов разложения этих подпоследовательностей.''* По всем ''сохранённым коэффициентам разложения подпоследовательностей'' 1-ой последовательности:** По всем подпоследовательностям 2-ой последовательности:*** Подсчитать коэффициенты разложения подпоследовательности 2-ой последовательности по выбранному ОНБ.*** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.*** Подсчитать L₂-расстояние между векторами коэффициентов разложения подпоследовательностей.*** Поделить подсчитанное расстояние на сумму норм векторов коэффициентов.*** Сохранить подсчитанное значение как (i, j)-ый элемент матрицы гомологии.* Записать матрицу гомологии в выходной файл. === Алгоритм с учётом параллелизма === Изменения с учётом параллелизма тривиальны: наиболее внешние циклы разделяются на ''M'' частей и для обработки каждой части работы создаётся собственный поток. Далее главный поток приложения ожидает завершения всех созданных, т.е., ожидает окончания очередного этапа работы. * Загрузить входные файлы последовательностей.* ''Создать требуемое число M вычислительных потоков, далее, для каждого из них:''** ''Подсчитать и сохранить в памяти коэффициенты разложения своей <m>\frac{1}{M}</m>-ой части подпоследовательностей 1-ой последовательности по выбранному ОНБ.''** ''Подсчитать и сохранить в памяти нормы своей <m>\frac{1}{M}</m>-ой части векторов коэффициентов разложения этих подпоследовательностей.''* ''Создать требуемое число M вычислительных потоков, далее, для каждого из них:''** ''По своей <m>\frac{1}{M}</m>-ой части сохранённых коэффициентов разложения подпоследовательностей 1-ой последовательности'':*** По всем подпоследовательностям 2-ой последовательности:**** Подсчитать коэффициенты разложения подпоследовательности 2-ой последовательности по выбранному ОНБ.**** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.**** Подсчитать L₂-расстояние между векторами коэффициентов разложения подпоследовательностей.**** Поделить подсчитанное расстояние на сумму норм векторов коэффициентов.**** Сохранить подсчитанное значение как (i, j)-ый элемент матрицы гомологии.* Записать матрицу гомологии в выходной файл. === Сравнение векторов с учётом векторных операций и дискриминантности === * Вычислить относительный порог <m>l = (\varepsilon \cdot (s_1 + s_2))²</m>, где s₁ и s₂ — нормы векторов.* Начальное значение ''f = 0''.* В цикле:** С помощью функции IPP <code>ippsNormDiffL2_64f</code> (или 32f, в зависимости от требуемой точности) вычислить норму разности очередных участков длины ''d'' сравниваемых векторов.** Добавить к ''f'' квадрат полученного значения.** Если ''f > l'', принять, что вектора «не подобны».* Если цикл завершился без принятия того, что вектора «не подобны», принять, что вектора подобны. === Сравнение ОНБ === Учитывая, что поиск повторов может осуществляться по выбору с использованием любого из ортогональных базисов, и что в библиотеке функций разложения их было реализовано 9 различных — базис Чебышева 1 рода, базис Чебышева 2 рода, дискретные косинусное и синусное преобразования, базис Фурье, базис Лежандра, базис Лагерра, базис Якоби и базис Эрмита — очевидным образом встаёт вопрос: а какой же из них «лучше» в задаче поиска повторов в последовательностях? А кроме того, каковы в целом критерии качества, по которым требуется производить сравнение базисов? Очевидным подходом к данному вопросу является критерий «максимум соотношения сигнал/шум в найденных в итоге повторах». Другой вариант — максимум средней длины найденных подобных участков, так как цель поиска повторов заключается в том, чтобы найти как можно более длинные подобные участки. Как можно оценить эту длину? Опишем простейший подход. Во-первых, нужно выбрать ширину скользящих окон и глубину разложения и выбрать некоторые тестовые данные, содержащие широкий спектр различных повторов — здесь хорошо подходит часть реальной ДНК-последовательности. Далее, используя различные базисы и подбирая порог сравнения (<m>\varepsilon</m>) такой, чтобы общее число найденных подобных участков было приблизительно равно, подсчитывать среднюю длину найденных подобных участков. Как вариант — можно вычислять медианное значение. В процессе реализации программы вначале был выбран базис Чебышева 1-го рода; потом пробовали базис Лежандра. Потом было высказано предположение о том, что базис Чебышева 2-го рода произведёт «революцию» по той причине, что имеет выпуклую весовую функцию и сильнее учитывает центр сравниваемого отрезка, чем края, но революции не произошло, результаты базиса Чебышева 2-го рода сильно похожи на базис Чебышева 1-го рода, и даже немного хуже, в том числе и по средней длине найденных повторов. Ниже приводится табличка с замерами средней длины найденных повторов на различных базисах и части генома мыши длиной 1.5 млн нуклеотидов в качестве тестовых данных. Сравнение производилось при приблизительно равных количествах найденных «подобных» участков — 5000. При выбранных настройках минимально возможная найденная длина подобного участка — 3500 нуклеотидов. <tab sep="tab" border="1" class="simpletable" head="topleft">- Eps Среднее МедианаЧебышева 1 рода .025 '''3978''' '''10000'''Чебышева 2 рода .0285 3882 3500ДКП .025 '''3978''' '''10000'''ДСП .021 3975 '''10000'''Фурье .025 '''3978''' '''10000'''Эрмита .0015 3502 3500Лагерра .0063 3505 3500Лежандра .0225 3966 '''10000'''</tab> Каковы выводы? По средней длине повтора лидирует базис Чебышев 1 рода, а базисы ДКП, ДСП и Фурье дают чрезвычайно похожие на него, практически идентичные, результаты. С небольшим отставанием следует базис Лежандра, далее — базис Чебышева 2 рода, а базисы Эрмита и Лагерра для поиска подобных участков не подходят вообще, чему есть простое математическое обоснование — оба они действуют на бесконечной полупрямой — либо <m>(0, +\inf)</m>, либо <m>(-\inf, +\inf)</m>. Вариантов значения медианной длины при этом было всего 2: 3500 (минимально возможная) или 10000. Медианная длина в данном случае отражает, фактически, «чистое» количество шума — мелких отрезков, и гласит, что приемлемый уровень шума дают базисы Чебышева 1 рода, ДКП, ДСП, Фурье и Лежандра. [[Категория:Статьи]][[Категория:УчёбаБиоинформатика]]