Kodomo

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

Лекция 1

Введение. Структура решения биологической задачи

Если тестирование не получается, меняют параметры или формализацию. Про алгоритм считают, что он всё же решает задачу, поэтому при провале тестирования алгоритм обычно не меняют.

Другой подход: кулинарный подход:

задача -> алгоритм(ы) -> параметры -> тестирования. То есть алгоритм решает ровно ту задачу, которая в нем написана.

Пример: сравнения последовательностей - математические задачи

  1. глобальное выравнивание NW - поиск оптимального пути в графе (формализация)
  2. SW локальное выравнивание -тоже путь в графе
  3. FASTA - сравнивает последовательности - пример "кулинарного алгоритма"
  4. BLAST - формальной оптимизации нет - пример "кулинарного алгоритма"
  5. CLUSTUL - множественное выравнивание. тоже решает ровно то, что в нем написано

Итак, мы видим два пути: с постановкой формальной задачи и без неё.

Способы формализации задачи сравнения последовательностей

Есть строки

Операции:

Если есть набор операций прямого преобразования (S2 в S2), то набор операций для обратного преобратзования получается однозначно. FIXME Поэтому расстояние от S1 до S2 равно расстоянию от S2 до S1:

D(S1, S2) = D(S2, S1)

Свойства расстояния:

Редакционное расстояние обладает всеми свойствами расстояния.

Заклинания:

Получается матрица: || ||s11||...||s1i||... ||s21 ||... ||s2j|| ||->||x

Растояние вертикального и горизонтального ребра: 1 (это пропуск буквы в одной из последовательностей). Расстояние диагонального ребра: delta - функция несовпадения, = 1 или 0, в зависимости от того, равны ли соответствующие буквы.

Редакционное расстояние - вес минимального пути на этом графе.

Задачи проверки последовательностей на гомологичность и выравнивание - разные задачи

Сколько всего бывает выравниваний последовательностей длин m и n:

2 * Sqrt(pi/n)* 2**(2n) или более точно (2n)! / (n!)**2

Выравнивание можно представить в виде выборочной последовательности:

s11,s12,s21,s22,s21,s21...

Выборочная последовательность <==> выравнивание Выборочную последовательность получают, читая выравнивание слева направо, читая столбики. Однако следующие выравнивания дадут одинаковую выборочную последовательность: 

-a-                     -a--
-b-     и               --b-

То есть, выб. последовательностей немного(?) меньше.

Теперь, выборочной последовательности соответствует последовательность из 0 и 1 Пишем 0, когда берем из S1 и 1, когда берем из S2 Число последователньостей С(2n, n) = (2n)! / (n!)**2. дальше по формуле Стирлинга. Итак, просматриваемое пространство очень большое. ~2**n

Динамическое программирование для нахождения редакционного расстояния

Есть очередная вершина графа, ячейка таблицы. В ней есть число, хрянящее редакционное расстояние.

Теперь обсудим инициацию/базу рекурсии/индукции. Вводим краевые вершины слева от таблицы и сверху над таблицей, с которых всё начинается. Аналогично завершение осуществляется через краевые вершины справа и снизу как определить d в краевой вершине завершения: d(m+1,i) = min(d(m,i), d(m+1,i-1)+1) движение по краевым полосам соответствует инделям в начале или в конце.

Замена: w(i,j) = -d(i,j) На ребрах будем ставить не 1 и -Delta, а -1 и Delta w(i,j) - max вес сходства.

Ещё изменения: диагональное ребро:

вертикальное и горизонтальное:

Такое решение позволяет решать задачу уже при identity = 80% 

------- 
|
|                                       |
                        -----

Если на горизонтальных и вертикальных ребрах в краевой зоне написать 0, то мы не штрафуем за индели в краевой зоне. Это выравнивание с висячими концами. Бывают разные варианты высичих концов. Когда мы натягиваем фрагмент на геном, мы не штрафуем за висячие концы генома, но штрафуем за висячие концы фрагмента

Время работы алгоритма: T =O(m*n) Количество памяти: M = O(m*n) - раньше это было слишком много.

Количество памяти можно сократить. Алгоритм Мюллера-Майерса. Он не очень актуален при современной технике, но красив и поучителен. Гоним алгоритм в обратном направлении, пользуясь симметричность замен, которые нужно произвести. Берем линию, рассекающую таблицу пополам: n/2 Для всех точек этой линии за один проход находим значения оптимальных путей от начала и от конца. Можем найти ту точку, через которую проходит оптимальное выравнивание. Знаем одну точку на оптимальном выравнивании и его вес. 

--------
|
        тут             |                               |
|                               x
                                                                |
|                               |       тут
                                                                |
                                ---------

Потом запускаем ту же задачу для двух более маленьких частей Нам не нужно помнить само динамическое программирование, только его результат. Расход памяти: M = O(m+n) Из-за этого динамическое программирование для одной точки приходится проводить много раз. Пусть m = n T ~ n**2 + n**2/2 + n**4 + ... = 2 n**2 То есть, всего в два раза больше операций, а экономия памяти значительна.

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

При должном упорстве все описанные алгоритмы хорошо работают при identity > 70% Вводим локально-оптимальное выравнивание - такое выравнивание фрагментов последовательностей, что любое удлиннение или укорочение его приводит к уменшению его веса.

Часть II

SW Локальное выравнивание - выравнивание с максимальным весом, его нельзя улучшить. За всё, что происходит за границами выравнивания, даем цену 0. Из стартовой вершины проводим ребра нулевого веса в каждую из точек. Из каждой точки также ребра нулевого веса в конечную точку.

Примечание: ввели новое понятие S - матрица замен. Используется вместо delta.

w(i,j) = max(w(i-1,j)-d, w(i,j-1)-d, S(s,s), 0)

(i max, j max) = argmax(w(i,j)) по всем (i,j)

Вычисляем вес от вхождения до конца, а потом находим максимум - там и делаем конец выравнивания.

В большей степени зависит от параметров, чем глобальное выравнивание. Хорошо работает при identity > 60%

Хорошее выравнивание часто разбивается на блоки: www---wwww---

Плохое выравнивание: w-w-ww--ww-w-w

Хочется, чтобы выравнивание получалось блочным.

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

реализация: вводим в нашем графе вертикальные и горизонтальные переходы на несколько ячеек. Такой переход будет соответствовать делеции блока. w(i,j) = max(max по k(w(i-k,j)-delta_del(i-k)), max по k(w(i,j-k)-delta_del(j-k)), S(si, sj), 0)

T = O(n**3)

Можно от O(n**3) перейти к O(n**2): Вводим два пути: v-путь - путь делеций, w-путь - путь замен, а также ребра "рождения" и закрытия делеций. На ребрах v-пути стоит d_ext. Всего будет в каждую вершину входить ограниченное чило ребер (5). закрытие делеции (переход v->w) - бесплатно рекурсия:

Часто выравнивание блочное, но в нем есть плохие участки. Хочется выделять невыравниваемые участки. Чтобы это реализовать, к предыдущей схеме добавляем переход v -> v с ценой d_un (невыравниваниваемое). Афинные штрафы идут ещё и за эти переходы. В каждую ячейку 6 переходов

параметры: match, mism, del. Пусть match = 1 (так как конкретный размер нам неважен) mism > 2 * del (иначе любое несовпадение можно будет обойти двумя делециями).

случайная аминокислотная последовательность. при оценке E-value в BLAST используется бернулиевская модель случайной последовательности, а белки в реальности подчиняются не этой модели.

Считаем, что есть две последовательности бернулиевские, причем все буквы равновероятны. Получили вес выравнивания 18. Надо оценить вероятность получить на случайных последовательностях вес 18 или больше.

Можно всю теорию перенести на марковскую модель.

Наибольшая общая подпоследовательность

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

Теорема. Мат.ожидание длины наибольшей общей подпоследовательности пропорционально длине последовательности. Доказательство. Обе последовательности длины n. Возьмем половину первой последовательности, половину второй последовательности, построим выравнивание половин. Получили вес выравнивания правой части и левой части. Вес общего выравнивания больше или равен суммы весов выравниваний половин.

Но E(r) <= 2n, так как длина общей подпоследовательности не может быть больше сумме длин исходных последовательностей. Значит, E(r) ~ n

Наибольшее общее слово

Если наложить последовательности без сдвигов, то длина наибольшего общего слова будет равна числу последовательных успехов в серии испытаний Бернулли. При одном наложении E(r) = log(1/p, m*n) + const (известная константа), где p - вероятность совпадения. Таким образом, E(r) ~ log(n)

Утв. На плоскости с осями mism, del ассимптотика E в некоторой области около 0 будет линейной, а во внешной области - логарифмическая. Параметры (матрица BLOSUM) подбираются так, чтобы получить логарифмическую ассимптотику, чтобы не было больших висячих хвостов