Kodomo

Пользователь

Лекция 2

замечание 1

caagacatac - случайная последовательность?

– нет, случайное число/последовательность/событие не произошло, данная последовательность - реализация случайной последовательности. Как только случайное число было получено, его вероятность стала 1. Вероятность выпавшего орла равна 1, так как он уже выпал.

замечание 2

мы писали: ... = w(i-1,j-1) + S(s(i), s(j)) а до этого использовали δ(s(i), s(j)) S - матрица сопоставления букв. Мы получили:

Общие соображение по составлению таких матриц

Транзиция: пурин на пурин или пиримидин на пиримидин. Транзиция более вероятна, чем трансверсия.

Составление матрицы сопоставления

Рассмотрим парное выравнивание без делеций (вернее, их мы сейчас не учитываем). Считаем позиции независимыми (Бернулиевская модель) x и y – последовательности. p(x и y - выравнивание) = П p(x(i), y(i) | выравнивание) по всем i p(x,y | нет выравнивания) = П p(x(i)) * p(y(i)) - вероятность, что совпали случайно

Условимся о таких обозначениях: 

L = \log \frag{p(\alpha \beta | M)}{p(\alpha \beta | R)} = \log \frag{p(\alpha \beta | M)}{p(\alpha)p(\beta)} = S(\aplha \beta)

L – правдоподобие

это и становится значением матрицы сопоставления (например, BLOSUM)

используем программу локального выравнивания, использующую простую функцию delta Строим стопки множественных выравниваний, построенных из локальных выравниваний. Такие локальные выравнивания ложатся в БД BLOCKS. Длина одного такого блока небольшая (например, 6 аминокислот) 

f(\alpha \beta) = \frag{n(\alpha \beta}{N} | все белки, все колонки \approx p(\alpha \beta | M)

S_bl \alpha \beta) = \log_2 \fraq{p(\alpha \beta | M)}{p(\alpha)p(\beta)}

Пример: 

    A
    G
    G
    S

значения n:

Из-за большого количества близких последовательностей возникает перегруженность базы. Выкинем последовательности, слишком похожие на кого-то ещё в базе (когда уровень сходства выше определенного порога). Для разных значений порого получаем разные блоки. Если задать порого 50% (последовательности довольно далекие). Мы получим матрицу BLOSUM50. Это число определяет уровень фильтрации последовательностей.

Самой правильной матрицей определили BLOSUM62. Использовались структурные выравнивания. BLOSUM62 дало наилучшее соответствие структурным выравниваниям.

  1. Нехорошо делать порог слишком низким (25, очень далекие последовательности, мало колонок), статистика будет слишком малой. Чтобы увидеть все 210 независимых параметров, нужно много испытаний.
  2. если белки близкие, надо использовать высокие BLOSUM (80-90). В далеких белках далекие замены (триптофан на глицин) более вероятны. Можно сначала строить выравнивание при помощи BLOSUM62, а потом использовать другую BLOSUM, в зависимости от identity

примерные значения identity:

Процесс эволюции: α -> β Близкие последовательности: повторных событий мало, то есть вторичных замен не произошло. p(α β) = p(Δt)(α | β) * p(beta) – по прошествии времени Δt Это марковское событие

p(α β) = p(2Δt)(α | β) * p(beta) – по прошествии времени 2Δt

p(2Δt) = p(Δt) ^ 2 (возвели матрицу условных вероятностей в квадрат) p(NΔt) = p(Δt) ^ N (возвели матрицу условных вероятностей в степень N)

PAM

PAM1 - 1 одна замена на 100 аминокислот PAM2 - PAM1 ^ 2 ... PAM250 - на 100 аминокислотах произошло 250 замен

p(NΔt)(α β | M) = p(NΔt)(α | β) * p(β) PAM(N) = log (p(NΔt)(α | β) / P(α))

Получается серия матриц PAM.

выбор матрицы сказывается на качестве выравнивания при identity около 40%

Распределение экстремальный значений

кси - случайная величина (СВ) G(x) = p(кси < x) - функция распределения (ФР) случайной величины кси. Бросили кубик несколько раз. Посмотрели максимальное значение - это новая СВ. N случайных испытаний. Хотим найти G(max(ξ1, ξ2, ..., ξn)) ζ = max(ξ1, ξ2, ..., ξn) p(x <= ζ) = 1 - p(x>ζ) = 1 - p(x > ξ1) * ... * p(x > ξn) , то есть x больше каждого из кси 1...n ФР максимума = 1 - (1-G(x)) ** N ФР минимума = G(x) ** N

Для нормального распределения: Gmax(exp(N * k FIXME

Безделеционное локальное выравнивание

Теорема. Если есть две последовательности длин m и n, w - порог на вес локального безделеционного выравнивания ξ – число ЛБВ с весом >= w Последовательности считаем бернулиевскими. Найдем мат.ожидание. E(ξ) = k * m * n * e**(-λw) – это у нас e-value константы k и лямбда зависят от матрицы замен.

Одна из последовательностей – весь банк. E-value зависит от размера банка линейно. P-value - вероятность увидеть событие такое или лучше при заданном количестве испытаний. p-value = 1 - e**-E(кси)

Как делать поиск по банку

Быстрый поиск по банку осуществляется с помощью хеширования. Подготовка банка:

Часть II (после обеда)

Что делать с индексной таблицей? Два подхода:

FASTA.

FAST A. входной формат: фаста-формат

Строим матрицу сидов. Сид имеет две координаты. Наносим сиды на таблицу. Ищем диагонали, на которых много сидов. S(i1, j1) S(i2, j2) - сиды d = i1 - j1 = i2 - j2 - сиды лежат на (одной) диагонали отбираем несколько (параметр программы) диагоналей, на которых лежат сиды (не менее 2) В выделенной полосе вокруг диагонали запускаем SW около найденных сидов – это эффективно. Как только score SW доходит до 0, на этом месте останавливаемся.

Программа FASTA работает медленнее BLAST, но аккуратнее

Как оценить статистически: a1 w1 a2 w2 ... ak wk

z-score = (w-E) / σ считают, что z-score распределен нормально (не всегда верно) исходя из этого рассчитывают p-value

BLAST

ITKAFLQV
ISRAFLEV
   сид

Начинает с сидо. Идем от сида вправо, накапливая веса, какие получатся, без вставок и делеций. Аналогично идем налево. Получаем участок высокого сходства. Выбираем максимум слева и справа, рассматриваем весь фрагмент между ними. Считает E-value для этого фрагмента. Отбирает по лучшим e-value.

Так работал BLAST1. Плохо ловил неблизкие последовательности. 

BANK:  AFL
QUERY: GFI

BLAST2:

Поэтому, чтобы такие сиды поднимались, берут не только саму L-грамму, но и множество всех L-грамм, которые отличаются L-граммы из QUERY не более, чем на определенный порог. Однако из-за этого количество сидов снова стало большим, что плохо. Поэтому используется подход FASTA: рассматривают только те диагонали, на которых есть много затравок. Делаем небольшого SW на несколько букв в сторону.

BLAST идеологически ищет короткие выравнивания, FASTA - длинные.

Ещё один подход

Наносим сиды на карту. Соединяем недалекие сиды ребрами, если они совместимы. После этого можно запускать динамическое программирование. Аккуратнее, чем все остальные, но помедленнее.

Немного математики

  1. δ-функция - это не функция
    • δ(x) = 0 для каждого x != 0
    • интергал от -inf до +inf от δ = 1 
        \int_{-\infty}^{\infty} δ(x)\,dx = 1
    • интергал от -inf до +inf от δ(x-y)f(x)dx = f(y) (это её свойство) 
        \int_{-\infty}^{\infty} δ(x-y)f(x)\,dx = f(y)

  2. δ(i, j) = 0 при i != j, 1 при i == j – символ Кронекера, родственная к δ-функции

  3. Г(x) = интеграл от 0 до +inf от e-t t(x-1) dt

    • Г(0) = Г(1) = 0

    • Г(x+1) = x Г(x) – сравни с (n+1)! = (n+1)n!

    • Г(n+1) = n! – Г является обобщением факториала на нецелые числа

Вероятностные модели последовательностей

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

Генерация последовательностей:

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

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

Порядок марковской модели ограничивается размером обучающей выборки.

Lk = сумма по всем словам в выборке n(a1, ..., ai+k) log P*(...)

BIC = -Lk + A^k(A-1)*log N, A = |∑|

как только BIC достигает максимума, это значит, что что оптимальный порядок достигнут.

Статистика

Вывод: мужчин лечит (5/9 > 1/3), женщин лечит (5/6 > 2/3), а если в сумме людей калечит (20/34 < 21/33)

Теория вероятности

Сделали N испытаний, n успехов вероятность успеха = n/N

Однако: при малом числе испытаний получается такое: три раза выпал орел. Мы всегда делаем свою априорную оценку вероятности. Вероятность выигрыша оценивается априорно. После первого забега возникает поправка - апостериорная вероятность. Но при этом вероятностный характер (из чего исходили в самом начале) сохраняется.