Лекции "Распознавание и анализ сайтов связывания транскрипционных факторов" - korshu.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Здравствуйте, тема нашей сегодняшней лекции "Распознавание и анализ... 1 207.75kb.
Руководство разработчика Общие сведения Требования к установке Установка 1 150.18kb.
Техническое задание на разработку веб-системы (сайта) г. Белгород... 1 68.92kb.
Сальваторе Мадди Теории личности сравнительный анализ 52 9987.9kb.
Лекции для индивидуальной пропагандистской деятельности, отдельные... 6 1112.03kb.
Лекции Второе издание, переработанное и дополненное 13 4275.34kb.
Лекция для учеников 8 1 38.08kb.
Академия социального управления анализ результатов единого государственного... 12 1913.51kb.
Царство растений. Строение (ткани, клетки, органы), жиз­недеятельность... 1 88.26kb.
Лекции по дисциплине " Инструментальные программные средства" 20 1278.98kb.
Рекомендации по разработке собственного модуля по мониторингу сайтов... 1 73.56kb.
Итак, дошкольный период развития ребенка подходит к концу. И тут... 1 54.57kb.
Инструкция по работе с сервисом «sms-платеж» 1 218.94kb.

Лекции "Распознавание и анализ сайтов связывания транскрипционных факторов" - страница №1/1


Здравствуйте, тема нашей сегодняшней лекции “Распознавание и анализ сайтов связывания транскрипционных факторов”.


Хорошо известно, что районы регуляции транскрипции эукариотических генов имеют довольно сложную структуру, с модульной и иерархической организацией регуляторных элементов. Самый низший уровень организации регуляторного района соответствует сайту связывания транскрипционного фактора. Следующий уровень- композиционному элементу. Следующий – энхансерам, сайленсерам, коровым промоторам и некоторым другим типам регуляторных элементов. Наивысшим уровнем организации является район регуляции транскрипции в целом.


В зависимости от клеточного состояния, в ядре клетки представлен специфичный набор белковых факторов, взаимодействующих с конкретным поднабором сайтов связывания регуляторных районов генов. В результате, у многоклеточных организмов, на регуляторных районах одного и того же гена для его экспрессии, в зависимости от стадии клеточного цикла, типа клетки, ткани, органа, стадии развития организма, условий внешней среды и т.д. формируются существенно отличающиеся транскрипционные комплексы.


Регуляторные районы генов могут иметь сложное строение и включать сайты связывания различных транскрипционных факторов. В качестве примера приведены регуляторные районы, контролирующие транскрипцию гена аполипопротеина В человека. Апо В имеет восемь регуляторных единиц. Пять регуляторных единиц располагаются в 5’фланкирующем районе: промотор (-128/-1), два негативных регуляторных элемента (-3678/-1802 и –261/-129), регуляторный район (-898/-262), а также кишечно-специфический энхансер (intestine specific enhancer) длиной 300 п.о в далекой 5’области гена (-57000 п.о). Три регуляторные единицы расположены ниже старта транскрипции: регуляторный район а первом экзоне (+1/+128), печень-специфический энхансер (liver-specific enhancer) в первом интроне (+346/+521) и liver and intestine specific enhancer во втором интроне (+621/+1064).


Регуляторный район (-121,-1) изучен наиболее детально. Этот район содержит экспериментально подтвержденные сайты связывания многих транскрипционных факторов, таких как HNF-3, COUP, HNF-4, C/EBP and TATA box. Причем, сайты HNF-3 и C/EBP формируют композиционный элемент, и одновременное взаимодействие белковых факторов с HNF-3 и C/EBP приводит к синергичной активации транскрипции.


Другой типичный пример регуляторного района транскрипции гена тирозин аминотрансферазы крысы показан на этом слайде. Он содержит более 40 экспериментально полученных сайтов связывания траскрипционных факторов, объединенных в 6 блоков. 1)печень-специфичный энхансер, 2) печень-специфичный регуляторный район, 3)еще один печень-специфичный энхансер, 4)глюкокортикоид-индуцибельный энхансер, 5)модуль, гиперчуствительный к ДНКазе II, 6)коровый промотор, содержащий ряд сайтов связывания транскрипционных факторов, в том числе TATA-бокс.


Вся экспериментально полученная информация о расположении транскрипционных факторов на последовательности ДНК, характере взаимодействия и типе их регуляции заносится в компьютерные базы данных. Одним из примеров таких баз данных является TRRD – созданная в нашей лаборатории, одна из крупнейших в мире база данных регуляторных районов. Здесь приведен пример записи в базе TRRD полученной в ходе различных экспериментов информации о сайте связывания HNF-4.


Переходим к рассмотрению методов анализа и распознавания сайтов связывания.

Первыми, и наиболее распространенными способами анализа и описания сайтов связывания были подходы, основанные на получении предварительной экспериментальной информации о примерном расположении реальных сайтов в последовательности. Затем эти районы присутствия сайта фазируются или выравниваются друг относительно друга и исследователи пытаются понять, какая именно последовательность нуклеотидов определяет функциональность сайта, и какова ее длина.

Сайты рестрикции, на которых впервые применялся подобный подход были идеальным объектом, для анализа и распознавания, поскольку представляют собой очень простую последовательность ДНК, например GAATTC для EcoRI белка. Причем все участки немодифицированной ДНК имеющие точно такие последовательности нуклеотидов будут распознаваться соответствующими рестриктазами и разрезаться. Мутация хотя бы в одной позиции приводит к снижению эффективности рестрикции на порядки. До сих пор сайты рестрикции остаются наиболее легко распознаваемыми сигналами в ДНК.


Сайты связывания различных регуляторных белков обычно имеют гораздо менее консервативный нуклеотидный контекст и для их описания требуются несколько более сложные подходы.



Метод консенсуса.

Рассмотрим выборку 6 участков –10 районов первых из выявленных промоторов E.coli (Pribnov, 1975).

Хорошо видно, что из 6 позиций только две являются полностью консервативными, две – содержат по одному отличному от остальных нуклеотиду, а две являются относительно вариабельными. При этом полностью похожими являются только 2 последовательности. Наиболее простым способом описания такой выборки может быть построение так называемого консенсуса, то есть последовательности букв, наиболее адекватно описывающей все последовательности выборки. Для этого каждой позиции консенсуса приписывается нуклеотид, наиболее часто присутствующий в данной позиции последовательностей выборки. В нашем случае консенсус примет вид TATAAT. При распознавании с помощью такого консенсуса в геномных последовательностях программа будет предсказывать по случайным причинам такой сайт примерно один раз на 4100 пн (при равных частотах нуклеотидов) и распознает только 2 сайта из 6 реальных. Для распознавания всех последовательностей требуется допустить некоторое количество несовпадений в произвольных или заданных позициях, но это приведет к значительному повышению количества предсказанных по случайным причинам сайтов.

Альтернативным способом записи консенсуса является использование расширенного IUPAC алфавита (таблица).


В этом случае консенсус примет вид TATRHT и сможет распознать 4 реальных последовательности из 6, при обнаружении по одному ложному сайту на примерно 770 пн. Для выявления всех сайтов требуется допущение несовпадений в двух позициях консенсуса, что так же приведет к существенному возрастанию количества ложных распознаваний.



Приметы консенсусов трех основных сайтов связывания корового промотора.


Другим распространенным методом описания выборки выравненных последовательностей регуляторных сайтов является метод частотной матрицы.

Данный метод заключается в построении так называемой частотной матрицы – матрицы W, каждая ячейка wi,b содержит информацию о встречаемости b-го нуклеотида (b=A,T,G,C) в i-й позиции (i=1…L, где L – длина сайта). Так, для примера на рисунке частотная матрица может иметь вид:

Другим способом представления информации о сайтах связывания транскрипционных факторов является построение матрицы относительных частот. В этом случае в каждой ячейке матрицы содержится отношение представленности каждой буквы в позиции к общему количеству сайтов.




В то же время, частотные матрицы не позволяют использовать в анализе информацию о средних частотах встречаемости нуклеотидов в окружающих районах, хотя известно, что в геномах реальных организмов частоты мононуклеотидов могут существенно отличаться от ¼. Bucher в 1990 году предложил следующий способ оценки позиционных весов оптимизированной весовой матрицы:



где Fib – относительная частота b-й буквы в i-й позиции сайта, pb – средняя частота присутствия b-й буквы в геноме, а ci и s – константы, подбираемые эмпирически.


Пример позиционной весовой матрицы для –10 района промоторов E.coli.


Общий вес W (score) найденного в процессе распознавания такой матрицей сайта равен сумме ее позиционных весов. При этом предполагается, что веса соседних позиций независимы.





На этом слайде представлен пример расчет скора нуклеотидной последовательности GCTATG на основе весовой матрицы –10 района промоторов E.coli. Для получения общего веса, мы суммируем соответствующие позиционные веса для каждой буквы последовательности.


На этом слайде приведен пример распознавания сайта связывания транскрипционного фактора Sp1 в нуклеотидной последовательности с помощью позиционной весовой матрицы.

В процессе распознавания исследователь задает граничный уровень веса Wbord. В том случае, когда вес анализируемого участка нуклеотидной последовательности превышает Wbord, этот участок считается потенциальным сайтом связывания.
Необходимо отметить, что весовая матрица может являться расширенным описанием консенсуса, то есть любой консенсус может быть записан в виде весовой матрицы, но не всякая матрица может быть однозначно записана в виде консенсуса.

Для оценки информативности построенных весовых матриц для выборок сайтов в различных регуляторных системах Shneider et.al. в 1986 использовал следующий способ расчета информационного содержания каждой позиции матрицы:



,

где i – позиция в сайте, b – соответствует каждому из возможных нуклеотидов, fb.i – частоты соответствующих нуклеотидов в i-й позиции. Таким образом, I варьирует от 0, при равных частотах нуклеотидов в позиции, до 2, если в позиции представлен только один нуклеотид.

В то же время, предложенный им подход мог быть использован только в случае равных частот встречаемости нуклеотидов в геноме. Реальные геномы имеют значительные смещения нуклеотидного состава, что приводит к неправильной оценке информационного содержания позиций. В общем случае формула выглядит следующим образом:

где pb- частота соответствующего нуклеотида в геноме.


Полное информационное содержание сайта длины L, в случае независимости входящих в него позиций оценивается как сумма информационного содержания входящих в него позиций.



На данном слайде показан пример оценки полного информационного содержания информационной матрицы –10 района промоторов E.coli.


Кроме табличного, еще одним распространенным способом визуализации частотных матриц является представление позиционных частот нуклеотидов в виде графической картинки – логотипа (sequence logo). Каждая колонка логотипа соответствует позиции матрицы, а относительная высота каждой буквы рассчитывается пропорционально частоте представленности буквы в данной позиции. Буквы сортируются по этому критерию и более представленные буквы располагаются выше менее представленных.

Построение Sequence Ligo проведено с использованием Интеренет - программы http://www.cbs.dtu.dk/gorodkin/appl/slogo.html.

Следующим подходом анализа сайтов связывания транскрипционных факторов является учет физико-химических и конформационных свойств ДНК, входящих в эти сайты.

Из экспериментальных данных хорошо известно, что локальные конформационные и физико-химические свойства двойной цепи ДНК в ее B-форме являются контекстно-зависимыми. Фактически, можно говорить о существовании специальных кодов, определяющих эти свойства. В простейшем случае эти коды могут быть описаны в виде динуклеотидов.

На данном слайде приведен пример таблицы динуклеотидного кода, определяющего такой конформационный параметр ДНК как угол TWIST. Максимальные и минимальные значения этого параметра отмечены звездочками. Хорошо видно, что этот параметр может варьировать в пределах 9 градусов.



На следующем слайде приведена аналогичная таблица для угла TILT. Здесь вы также можете наблюдать строгую зависимость параметра от динуклеотидного контекста.

С помощью подобных таблиц можно выявлять и анализировать значимые конформационные и физико-химические свойства ДНК сайтов связывания.

На этом слайде показан профиль такого параметра ДНК как температура плавления в пределах сайта посадки нуклеосом, полученная программой Левитского. Чем меньше температура плавления локального района ДНК, тем более высока гибкость этого участка. Ниже приведена схема локализация на поверхности нуклеосомы участков ДНК с резко отличающимися значениями гибкости.



Система B-DNA-VIDEO Пономаренко позволяет проводить выбор лучших физико-химических и конформационных параметров, обеспечивающих наиболее эффективное дискриминирование сайтов от случайных последовательностей. Выбор этих параметров осуществляется на основе теории полезности Фишбурна для принятия решения. Эта теория основывается на концепции размытой логики развитой Задех.


На этом слайде приведен пример нахождения свойств, приводящих к наилучшему разделению сайтов от случайных последовательностей для ряда сайтов связывания транскрипционных факторов.



Для предсказания активности функциональных сайтов на основе их контекста была разработана система ACTIVITY (Пономаренко).

Этот метод основывается на предположении, что активность сайта определяется облигаторными и факультативными конформационными и физико-химическими свойствами последовательности сайтов.

Облигаторные свойства константны и определяют уровень базальной активности сайта, а факультативные свойства отвечают за модулирование активности сайта относительно базального уровня.


Для предсказания активности использовалась линейно аддитивная модель. Конформационные и физико- химические свойства получались из системы B-DNA-Video.


Рассмотрим пример использования такой системы. Анализ мутантных вариантов промотора гена мышиного А-crystalline с экспериментально определенным уровнем транскрипционной активности показал, что среднее значение угла TILT промотора негативно коррелирует с его транскрипционной активностью. В то время как глубина большой бороздки ДНК позитивно коррелирует с его транскрипционной активностью.


Используя эти характеристики была получена функция предсказания транскрипционной активности промотора гена А-crystalline, обеспечивающий хорошее соответствие между экспериментальными и контрольными данными.




Методы распознавания сайтов связывания транскрипционных факторов в невыровненных нуклеотидных последовательностях.
Не смотря на значительный прогресс в разработке новых экспериментальных подходов анализа регуляторных районов и накопление большого количества данных о локализации сайтов связывания транскрипционных факторов, компьютерные методы анализа и распознавания регуляторных элементов остаются одним из эффективных инструментов исследователей. Такие методы позволяют выявлять характерные контекстные сигналы в выборках регуляторных районов объединенных общей функцией без использования экспериментальных данных о локализации в них известных сайтов связывания. Подобный анализ может дать информацию о присутствии нового сайта или о конформационных характеристиках анализируемого района. В то же время решение этой задачи требует применения более сложных методов анализа и способов оценки значимости выявленных сигналов.


Методы k-плетов.

Для обнаружения коротких и высоко консервативных мотивов широко используются методы, основанные на обнаружении слов заданной длины достоверно перепредставленных в обучающей выборке по сравнению с ожидаемым по случайным причинам или в негативной выборке.

Метод WORDUP, предложенный Pesole et al. (1992) заключается в поиске относительно коротких слов в 4-х буквенном алфавите, представленных в большей части последовательностей обучающей выборки и наращивания их длины до тех пор, пока значимость удлиненного слова, определенная по критерию 2 не станет ниже значимости более короткого входящего в него слова.

Дана последовательность S= x1x2…xn; xi=A,T,G,C

Содержащая n-w+1 олигонуклеотидов длины w, определенных как

sj= xj,xj+1,…,xj+w-1; j=1, n-w+1

Рассмотрим N нуклеотидных последовательностей S1, S2, …,SN, длиной Li нуклеотидов (i=1,…,N).

Если олигонуклеотиды распределяются согласно распределению Пуассона, то вероятность встретить олигонуклеотид k, длиной w нуклеотидов (k=1, …,4w), в последовательности Si хотя бы один раз:

,
где

– ожидаемая вероятность олигонуклеотида sk в последовательности i исходя из марковской модели первого порядка. f(ux,y) и f(uz)– частоты ди и мононуклеотидов в каждой последовательности.


Наблюдаемое число последовательностей, содержащих олигонуклеотид sk из N равно:



,

где pi(sk) = 1, если олигонуклеотид sk обнаружен в i последовательности, и pi(sk) = 0, если олигонуклеотид sk не обнаружен в i последовательности.

Ожидаемое число последовательностей, содержащих олигонуклеотид sk из N равно:

.

Статистическая значимость наблюдения слова sk может быть вычислена по критерию χ2.



Олигонуклеотиды, чья значимость превышает пороговое значение могут быть отсортированы на основании этого критерия.


Стартовая длина слова w используемая в анализе, определяется по наименьшей длине последовательности, удовлетворяющей условию того, что олигонуклеотиды распределяются по Пуассону (Lseq<<4w). Таким образом, для регуляторных районов неизвестной длины наиболее удобным является использование стартовой длины олигонуклеотида w=6.

Следующим этапом процедуры является выявление олигонуклеотидов длины w+1, w+2,… и т.д.

Пусть W={s1,…, sz} – набор значимых олигонуклеотидов длины w, отсортированных согласно их значениям χ2. Генерируются все олигонуклеотиды длины w+1, содержащие слова si и sj длины w из множества W и рассчитывается их значение χ2. Полученный олигонуклеотид длины w+1, sw+1 будет считаться статистически значимым, если


χ2(sw+1)>max[χ2 (si), χ2 (sj)],
В этом случае олигонуклеотиды si и sj длины w заменяются на sw+1 длины w+1.

Данная процедура повторяется для слов длины w+2 и так далее до тех пор, пока выполняется это условие.




Метод реализаций.

Метод выявления ССТФ предложенный Кондрахиным основан на представлении ССТФ как набора конкретных реализаций . Каждая из реализаций представляет собой слово длины в 15-символьном коде IUPAC-IUB. Такой подход позволяет избежать усреднения нуклеотидного контекста в описании функционального сайта, как это имеет место при построении одиночного консенсуса. Построение набора реализаций определятся двумя параметрами: 1) длиной олигонуклеотидного слова ; 2) максимально допустимым различием (расстояние Хэмминга) между этими олигонуклеотидными словами.


На первом шаге в анализируемом наборе ={} последовательностей экспериментально определенного ССТФ путем полного перебора выявляется так называемая главная реализация, представляющая из себя олигонуклеотидное слово длины с наибольшей частотой встречаемости в выборке . После этого все последовательности , содержащие , удаляются из выборки образуя множество . На следующем этапе в получившейся выборке последовательностей путем полного перебора производится поиск следующей реализации, то есть такого слова , которое обладает наименьшим расстоянием от слова и наибольшей представленностью в выборке. Этот процесс итерационно продолжается до тех пор, пока когда множество окажется пустым, либо в нем присутствуют только слова, отличающиеся от больше чем на .



Для автоматического выявления наиболее эффективных значений параметров и производится запуск описанной процедуры для всех возможных заданных значений пар и . При этом максимизируется функционал f(,) соответствующий проценту покрываемых последовательностей, то есть последовательностей содержащих хотя бы одну из реализаций R при текущих значениях параметров.

Метод распознавания на основе набора реализаций был реализован в программе FUNSITE-SIG-REAL. Считается, что фрагмент ДНК длины может рассматриваться как функциональный сайт определенного типа, если он совпадает с одной из реализаций этого сайта.



Методы Suffix trees.

Дерево суффиксов – это способ представления последовательности S=s1,..,sn символов в виде направленного (root directed) дерева. Такое дерево имеет ровно n висячих вершин пронумерованных от 1 до n, а каждый внутренний узел такого дерева за исключением корневого узла имеет, по меньшей мере, две исходящие ветки – подслова последовательности, имеющие одинаковое начало, исходящее из корня дерева, и различное продолжение, начиная с данного узла. Таким образом, все пути по ветвям дерева суффиксов начиная с корня и до висячих вершин представляет собой все подстроки исследуемой последовательности.

Данный подход может быть легко расширен и для описания набора последовательностей, в которых необходимо найти общие подслова произвольной длины. При этом новая ветка дерева может быть продолжена, то есть к ней может быть добавлена буква X только в том случае, когда ее продолжение имеет соответствующую поддержку, то есть новое подслово, начинающееся в корне дерева и заканчивающееся этой буквой содержится, по меньшей мере, в k последовательностях выборки из K. Ветки, не имеющие такой поддержки, терминируются.




Алгоритм WINNOWER.

Другой метод, реализованный в виде программы WINNOWER [Pevzner and Sze, 2000] использует следующий способ поиска. Пусть нам дана выборка из n последовательностей произвольной длины и нам необходимо найти все мотивы длины L, представленные в n последовательностях с не более чем d несовпадениями. Таким образом, если найденный мотив встретился в двух участках разных последовательностей, то эти участки имеют не более 2*d несовпадений. Исходя из, этого задачей алгоритма является поиск групп из n подслов длины L содержащихся в разных последовательностях, различающихся друг от друга не более чем по 2*d позициям. Эта задача может быть сформулирована в рамках теории графов. В этом случае каждая подстрока длины L исследуемой выборки будет представлена в виде вершины в графе G. Две вершины графа G представляющие разные подслова соединяются ребром, если они находятся в разных последовательностях и различаются не более чем по 2*d позициям (рисунок a).

Задачей алгоритма является найти все клики графа G - группы, содержащие по n вершин, каждая из которых связана с каждой из других вершин клики. Для решения этой задачи программа WINNOWER проводит последовательное отсечение всех вершин, которые не могут являться вершинами клики размера n (рисунок (b)). На основе оставшихся в графе вершин можно построить набор мотивов, обобщающих полученные клики.



Методы локального множественного выравнивания регуляторных последовательностей.

Для нахождения более длинных и более вырожденных сигналов используют методы локального множественного выравнивания. В этом случае задачей алгоритма является нахождение оптимального локального выравнивания максимизирующего целевую функцию.



Примером такого подхода является программа CONSENSUS. Суть этого метода заключается в следующем.

Пусть даны 3 последовательности (рисунок ХХ А), которые необходимо выровнять.

На первом этапе программа производит построение частотных матриц для всех k-плетов (рисунок ХХ В) первой последовательности.

Затем каждая из этих матриц комбинируется с каждым из k-плетов второй последовательности и матрицы пересчитываются (рисунок ХХ С).

Из всех матриц построенных для каждого из k-плетов первой последовательности сохраняются только матрицы с максимальным информационным содержанием I. Затем каждая из построенных матриц, содержащих информацию уже о k-плетах двух последовательностей комбинируется с каждым из k-плетов третьей последовательности и матрицы пересчитываются (рисунок ХХ D).

Из всех матриц построенных для каждого из k-плетов первой последовательности так же сохраняется информация только о матрицах с максимальным значением информационного содержания I. Эта процедура повторяется для всех выравниваемых последовательностей. Среди полученных на последнем этапе матриц производится селекция, например с использованием граничного значения Ibord. Анализируя профиль функции позиционного информационного содержания перекрывающихся матриц можно оценить реальную длину описываемых ими сайтов связывания.


Метод поиска максимального правдоподобия (EM) метод.

Метод EM является стандартным и широко используемым подходом для решения задач поиска максимального правдоподобия (Dempster et al. 1977). Он представляет собой два итерационных шага: expectation (E) –шаг оценки вероятностных параметров модели и maximization (M)- шаг максимизации параметров модели, которые повторяются до тех пор, пока не будет выполнено условие конвергенции (сойденности алгоритма).


Lawrnce and Reilly (1990) реализовали и применили EM алгоритм для анализа сайтов связывания (CRP). На первом шаге его работы происходит начальная оценка и установка частот нуклеотидов входящих в сайт pbx и не входящих в него pb0. Затем производится вероятностное взвешивание каждой позиции возможного начала сайта связывания на основе формулы Байеса. Согласно этой формуле вероятность встретить сайт связывания Bjy начинающийся в y-й позиции j-й последовательности может быть рассчитана как



где p={pbx , pb0}, S- рассматриваемая последовательность, исходная (prior) вероятность p0(Bjy) постоянна и равна 1/(L-k+1), а P(S|Bjy,p) равна произведению вероятностей оснований входящих в сайт, начинающийся в y позиции, и оснований не входящих него на основе модели p={pbx , pb0}.


Шаг E заканчивается расчетом ожидаемого числа nbx каждого основания b в каждой позиции x сайта связывания путем суммирования вероятностных весов позиций потенциальных сайтов, содержащих данное основание b, и числа nb0 каждого основания b в не - сайтах. Шаг M заключается в пересчете pbx и pb0 исходя из полученных nbx и nb0. Эти процедуры последовательно продолжаются до тех пор, пока алгоритм не сойдется, и параметры pbx и pb0 не перестанут изменяться.




Gibbs sampler

Lawrence et al (1993) предложили стохастический алгоритм Gibbs sampler для выявления сигналов в выборке регуляторных последовательностей методом локального множественного выравнивания. Метод основывается на предположении о том, что каждая последовательности исследуемой выборки содержит, по меньшей мере, один сайт. Алгоритм стартует со случайного выбора одной стартовой позиции в каждой последовательности выборки. Работа программы заключается в итерационном повторении двух операций.

А. Шаг построения модели. На этом шаге происходит генерирование модели p = {pb,x, p0b}, для первой выбранной последовательности. Как и в случае EM метода модель p оценивается на основе позиционных частот оснований, входящих в последовательности предполагаемых сайтов. При этом сайт входящий в выбранную последовательность при расчете модели p не учитывается.

B. Шаг вероятностного выбора (sampling). На этом шаге происходит выбор новой позиции сайта для первой последовательности путем вероятностного взвешивания всех возможных позиций. При этом вес каждой позиции оценивается как Ax=Qx/Px, где Qx – вероятность генерирования сегмента x на основе модели pb,x, а Px – на основе p0b. А вероятность случайного выбора сегмента x рассчитывается, как .

Аналогичная процедура повторяется для второй выбранной последовательности и так далее до последней последовательности. Затем эти операции снова повторяются с первой последовательностью и так далее до тех пор, пока алгоритм не сойдется. Теоретически, данный метод может находить локальное выравнивание соответствующее максимальному значению информационного содержания I, но на практике стохастический алгоритм зачастую сходится в точке локального максимума. Для решения этой проблемы и выведения алгоритма из точки локального минимума через каждые M итераций производится смещение рассматриваемого окна последовательностей на несколько позиций вправо или влево. На основе оценки веса каждой позиции выбирается наиболее оптимальное положение окна, и работа программы продолжается с этой позиции.

Данный метод позволяет выявлять в последовательностях множественные сайты и автоматически определять оптимальную длину сайта за счет нахождения длины окна соответствующего максимальному значению модифицированной функции информационного содержания.


Для поиска нескольких типов сайтов в выборке последовательностей, которые могут, как содержать несколько сайтов, так и не содержать их вовсе был предложен алгоритм motif (Bernoulli) sampler Neuwald et al (1995). Процесс поиска мотивов производится следующим образом. В начале все последовательности выборки объединяются в одну последовательность. Затем производится выравнивание случайно разбросанных сайтов. При этом сайты не должны перекрываться или попадать на границы последовательностей. Оставшиеся районы считаются не-сайтами. После этого программа берет первую позицию объединенной последовательности и проверяет, не перекрывается ли сайт, начинающийся в этой позиции с границами последовательностей или с ранее определенными сайтами других типов. Затем из выравненного набора текущих анализируемых сайтов удаляются сайты, с которыми он перекрывается и производится пересчет вероятностей p={pbx , pb0}.



Следующим шагом программы является вероятностное помещение анализируемой позиции либо в набор сайтов, либо не сайтов согласно отношению p(site)* pbx/(p(non-site)*pb0), где p(site) и p(non-site) – постериорные вероятности принадлежности какого либо участка к сайтам или не сайтам, определяемые пользователем. Затем программа берет следующую позицию и т.д. до последней позиции объединенной последовательности. Затем процесс снова повторяется с первой позиции и т.д. до тех пор, пока алгоритм не сойдется. Данный подход позволяет последовательно находить сайты разных типов и оптимизировать их длину.




Оценка качества работы процедур предсказания функциональных элементов генетических последовательностей.
Значительный интерес, проявляемый в последние десятилетия к компьютерному анализу генетических текстов, привел к разработке большого числа разнообразных методов автоматического распознавания функциональных районов в нуклеотидных и аминокислотных последовательностях.

При этом задачей разработчиков было создание методов, обеспечивающих максимально полное распознавание рассматриваемых элементов в тех последовательностях, где он действительно представлен, и минимизация ошибочного обнаружения таких элементов в случайных последовательностях или последовательностях, где данный элемент гарантированно отсутствует.

Использование универсальных способов оценки качества распознавания объектов одного типа разными методами позволяет оценить не только относительную эффективность методов, но и продемонстрировать уровень полноты имеющейся о данном объекте первичной информации (качество обучающих выборок), а так же степень адекватности моделей описания объекта существующими на данный момент подходами (качество методов).

Для оценки качества работы метода распознавания обычно используют следующие величины:

TP- true positive, количество правильного обнаружения сайтов в тех последовательностях, в которых эти сайты реально представлены;
TN- true negative, количество не обнаружения сайтов в последовательностях реально не содержащих данный сайт;
FP- false positive, количество обнаружения сайтов в последовательностях реально не содержащих данный сайт;
FN- false negative, количество не обнаружения сайтов в последовательностях реально содержащих данный сайт;

На основе использования вектора (TP, TN, FP, FN) было предложено несколько способов оценки эффективности распознающих процедур.

Наиболее простым и широко распространенным методом являются процентные оценки ошибок первого (недопредсказания, E1), и второго (перепредсказание, E2) рода.

, .

При этом ошибка первого рода демонстрирует долю реальных сайтов, которые ошибочно не были найдены, а второго рода – долю последовательностей, не содержащих реальных сайтов, в которых эти сайты были ошибочно предсказаны.

В качестве результирующей величины, характеризующей эффективность метода используется средняя ошибка Ea


Кроме того, часто используются такие характеристики как чувствительность (sensitivity, Sn) и специфичность (specificity, Sp).



, .

При этом Sn отражает долю правильно предсказанных сайтов среди всех реальных сайтов, а Sp – долю правильно предсказанных сайтов среди всех предсказаний сайтов.



Одним из наиболее широко применяющихся методов оценки качества распознавания сайтов является расчет коэффициента корелляции:



Этот коэффициент может принимать значения от –1 до +1. В случае абсолютно случайного распознавания он становится равен 0.