Определение регуляторных сегментов в геномах методами теоретического анализа последовательностей нуклеотидов ДНК (1097789), страница 4
Текст из файла (страница 4)
Вклад перекрывающихся мотивов всвободный член, не зависящий от n , также меньше или порядка аналогичноговклада в матожидание, причем величина этого вклада приближается к17величине этого слагаемого в матожидание снизу для сильносамоперекрывающихся мотивов (с консенсусами типа AAAAAA).В случае длинных последовательностей n >> 1 основную роль играетслагаемое, пропорциональное n . Если вероятность мотива P ( H )1 , то всемичленами, пропорциональными P 2 ( H ) , можно пренебречь, и основнойнепуассоновский вклад дают перекрывающиеся вхождения мотивов. Напрактике это означает, что дисперсия меняется только для однородных (типаpolyA) или периодических (типа poly-AT) мотивов. Для таких мотивовПуассоновское приближение неприемлемо. Для остальных мотивовПуассоновское приближение работает с большой точностью.В случае, если мотивы не являются маловероятными (при P ( H ) € 1 ),становятся важными поправки, пропорциональные P 2 ( H ) .
В этом случаепуассоновское приближение очевидно неприменимо, однако Z-значение (см.ниже) остается хорошим критерием представленности мотива в тексте, вчастности, и в случае самопересекающихся мотивов, число появленийкоторых в последовательности не распределено согласно нормальномузакону. При этом, в случае длинных последовательностей достаточноиспользовать поправки, пропорциональные n . На практике, для конкретногомотива обычно легко оценить вероятность того, что его вхождения будутсамоперекрываться.
Если число перекрывающихся вхождений невелико,можно ограничиться поправками, для которых не требуется сколько-нибудьсложных вычислений, кроме вычисления вероятности вхождения мотиваP (H ) .В случае коротких последовательностей n m следует учитыватьчлены, не зависящие от n . В случае P ( H )1 работает приближениеПуассона, при тех же условиях, что и в случае длинных последовательностей.Следует отметить, что вычисление дисперсии числа вхождений мотива впоследовательность редко является самоценной задачей и обычно18используется для построения статистических оценок наперепредставленность или избегание мотива в каких-то выборкахпоследовательностей.В диссертации также приведено точное вычисление дисперсии дляслучая, когда случайная последовательность представляет собой цепьМаркова первого порядка.
В этом случае появляется дополнительноеслагаемое, отражающее корреляцию отдельных слов на близком расстоянии.Относительный вклад этого слагаемого падает при P ( H )1.Вычисленные матожидание E ( H ) и дисперсия V ( H ) позволяютвычислить P-значение того, что мотив H перепредставлен в даннойпоследовательности, при условии, что E ( H )1 и верно нормальноеприближение. В этом случае P-значение вычисляется как вероятность«хвоста» нормального распределения, и величиной от которой однозначнозависит P-значение является Z-значение Z =O (H ) − E (H )V (H ), где O ( H ) - этоколичество реально наблюдаемых вхождений мотива.Глава 4.
АЛГОРИТМИЧЕСКОЕ ВЫЧИСЛЕНИЕ P-ЗНАЧЕНИЯДЛЯ ВЕРОЯТНОСТИ ПОСЛЕДОВАТЕЛЬНОСТИ, СОДЕРЖАЩЕЙМИНИМАЛЬНЫЕ КОЛИЧЕСТВА ВСТРЕЧ КАЖДОГО МОТИВА ИЗЗАДАННОГО НАБОРА МОТИВОВВ тех случаях, когда распределение Пуассона неприменимо, длявычисления P-значения приходится использовать алгоритмический подход. Воснове подхода лежит модификация алгоритма Ахо-Корасик (Aho, Corasick,1975).
Основная структура данных представляет собой дерево T ( H ) ,являющееся вариантом бора Trie ( H ) (Knuth, 1975). Дерево строитсяследующим образом. Пусть Q ( H ) - множество префиксов слов множества H .Каждый префикс q ∈ Q ( H ) отождествляется с узлом Node ( q ) . В частности,19корень бора отождествляется с пустой строкой ε . Длина префикса являетсяглубиной узла Node ( q ) .Текст читается слева направо и прочтение каждой буквысопровождается с передвижением по дереву, задаваемому функцией перехода.Эта функция для каждого узла и для каждой буквы имеет своими значениямиузлы дерева, между которыми осуществляется переход.
Значением функцииперехода δ : Q ( H ) × Σ → Q ( H ) для данной пары {узел, буква} ∀ ( p, a ) ∈ Q ( H ) × Σ ,является δ ( p, a ) - наибольший суффикс конкатенации pa , принадлежащий кQ ( H ) . Заметим, что δ ( p, a ) = pa iff pa ∈ Q ( H ) .Пусть T [i ] - буква текста T на позиции i . Обозначим как qi самыйбольшой суффикс текста T [1]...T [i ] , принадлежащий Q ( H ) .Последовательность узлов, определенная словами qi , строится по индукции∀i ≥ 0, qi +1 = δ ( qi , T [i + 1]) , с начальным условиям q0 = ε .
Такаяпоследовательность называется Ахо-Корасик-обходом бора Trie ( H ) ,ассоциированного с текстом Tk : {q0 ,..., qk } = AC (Trie ( H ) , Tk ) .Конкретный регуляторный сегмент эукариотической ДНК можетсодержать достаточно большое число сайтов связывания для различныхфакторов, причем эти сайты могут перекрываться друг с другом. В результатеестественно возникает проблема изучения мотивов, совместновстречающихся в одном и том же сегменте ДНК. Для оценки статистическойзначимости совместного наблюдения ряда мотивов необходимо вычислить Pзначения P ( Ln ( H1 ,..., Hs ; k1 ,..., ks ) ) того, что мотивы (H1 ,..., H ss ) имеютсоответственно как минимум ( k1 ,..., ks ) , возможно перекрывающихся,вхождений в текст Tn длины n , записанный в алфавите Σ .20Рисунок 1. Обход дерева Trie ( H ) . Мотив задан как множество H = {AAA, AAC,ACA, ACC, CCT}.
Синими стрелками показаны переходы, выходящие из вершиныААС, соответствующие каждой возможной следующей букве текста. Краснымистрелками показаны переходы, выходящие из вершины СС, соответствующиекаждой возможной следующей букве текста.Пусть дано s различных мотивов (H1 ,..., Hss ). Упомянутое P-значениебудет также обозначаться как P (Tn ( H1 ,..., H s ; k1 ,..., ks ) ) .
Рассмотрим мотивH = H1 U ... U H s являющийся объединением искомых мотивов, т.е. включающийв себя все слова, принадлежащие хотя бы одному из мотивов Hi . Построимбор Trie ( H ) для полного множества слов H . Узел q ∈ Q ( H ) можетпринадлежать как какому-то одному конкретному мотиву Hk либоодновременно некоторому подмножеству мотивов {H j }0< j ≤ s . Функцияперехода δ : Q ( H ) × Σ → Q ( H ) определяется также, как она была определена дляслучая единственного мотива H .Все тексты Ti длины i подразделяются на классы, в зависимости отналичия в них вхождения различных мотивов H j . Вводится индексвхождений I ( k ,...,k ) ( l1 ,..., ls ) , вычисляемый для набора мотивов (H1 ,..., Hss ) и1sпоказывающий, что текст Tn содержит li , возможно перекрывающихсявхождений мотива Hi . Индекс представляет собой s -вектор, i-я координатакоторого может быть вычислена следующим образом:21 l if l ≤ ki I ( k ,...,k ) ( l1 ,..., ls ) = λi = i i. 1 siki if li > kiДалее определяются классы Ci ( λ1 ,..., λs ; q ) , 0 ≤ λi ≤ ki , содержащие текстыTi длины i, для которых индекс вхождений мотивов (H1 ,..., H s ) в текст Ti равенAC (Trie ( H ) , Ti ) заканчивается в узле q .
Кроме того( λ1 ,..., λs ) , а обход бораопределяются дополняющие классы Gi ( k1 ,..., ks ) .Для вычисления искомой вероятности производится суммирование повсем узлам дерева q и по всем символам алфавита a. Пусть q′ - это значениефункции перехода δ ( q, a ) для такой пары (узел, буква). Такое значение можетпринадлежать сразу нескольким мотивам {H j }0< j ≤ s .
Тогда, вероятностьP ( Ci +1 ( λ1 ,..., λs , q ') ) того, что текст Ti принадлежит классу Ci +1 ( λ1 ,..., λs ; q ) можетбыть вычислена как:P ( Ci +1 ( λ1 ,..., λs , q ' ) ) =∑( q , a ):δ ( q , a ) = q ', q '∈{H j }0≤ j<s()P Ci ( I ( r1 ,..., rs ) , q ) * p ( a ) ,( li − 1) if q′ ∈ Hi. li if q′ ∉ Hiгде ri = Искомая вероятность получается тогда, когда достигается необходимоечисло вхождений всех мотивов.Техника, основанная на обходе бора, может быть естественным образомраспространена на вычисления P-значения числа вхождений мотива вслучайном тексте, порожденном цепью Маркова порядка K (Roytberg, 2007).Трудоемкость определяется временами порядка(KOn Σ m H + K Σ) ∏ k , гдеiΣ - это размер алфавита, H - это полноеiколичество слов в объединенных мотивах, m - это максимальная длина слова,K - порядок цепи Маркова, а ki - минимально допустимое количествовхождений мотива i .22В диссертации рассматриваются также эффективные способыпостроения дерева-бора в случае, если мотив задан не в виде перечисленияслов, а в виде матрицы позиционных весов, с конкретным порогом.
В этомслучае бор можно построить без явного выписывания всех слов.Глава 5. РАЗБИЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ НА УЧАСТКИ,ОДНОРОДНЫЕ ПО НУКЛЕОТИДНОМУ СОСТАВУ, МЕТОДОММАКСИМИЗАЦИИ БАЙЕСОВСКОГО ПРАВДОПОДОБИЯИерархическая структура генома, отражающается в иерархии доменовДНК, имеющих сходный нуклеотидный состав (Frank, Lobry, 1999). Можнопредположить, что это связано с различными условиями к термодинамикеформирования структур ДНК соответствующих уровней.В этой главе описывается алгоритм разбиения последовательностинуклеотидов на сегменты, которые могут приближенно считатьсястатистически однородными. Алгоритм состоит из двух стадий.
На первойстадии с помощью динамического программирования находится оптимальнаяконфигурация границ, разбивающих последовательность на сегменты такимобразом, что некоторая функция правдоподобия достигает на этом разбиениисвоего максимума.
На второй стадии алгоритма вычисляется вес каждойнайденной границы. Удаление границ с небольшими весами позволяетполучить субоптимальную сегментацию, устойчивую к малым вариациямисходной последовательности.Пусть задан текст T , длины n , записанный в алфавите Σ , состоящем изL = Σ символов. Целью алгоритма является построение оптимальногоразбиения T на некоторое множество сегментов {T1 ,..., TK } . ТекстT моделируется как реализация некоторой вероятностной модели. В отличиеот предыдущих разделов предполагается, что исходный текст представляетсобой серию сегментов {T1 ,..., TK +1} , в каждом сегменте текст порожден какпоследовательность независимых случайных испытаний и параметры модели23в пределах одного сегмента не меняются, причем сегменты предполагаютсявероятностно независимыми друг от друга.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
