Изменения

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

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

Идея — применить ОСАМк поиску повторов в ДНК, таким образом ускорив его. Мысль простая: разложить сигнал Как?! Во-первых, построить профиль последовательности, т.&nbsp;е. перевести её в длинный числовой вектор, выбрав w — окно профиля, и принимая за каждый элемент последовательности ''(количество пуринов в w-окрестности элемента) минус (количество пиримидинов в w-окрестности элемента)''. Далее, выбирая по какомуN значений из полученной последовательности — <m>(0 \ldots N-нибудь классическому ортогональному базису1), (s \ldots N+s-1), (2s \ldots N+2s-1), \ldots</m> (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;е. перевести её в длинный числовой вектор, выбрав 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 рода, Якоби, Лежандра, Лагерра, Эрмита, Фурье, ДКП, ДСП. Она работает и рисует красивые картинкиdiff'оподобными алгоритмами.