Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 11 лет назад пользователемda.fizteh.ru
1 Выравнивание последовательностей
2 Простое взвешивания +1 : вес совпадения -μ : штраф за несовпадение -σ : штраф за делецию/вставку Вес выравнивания = #совпадения – μ(#несовпадений) – σ (#делеций/вставок)
3 Алгоритм = -б = 1 если совпадение = -µ если несовпадение s i-1,j-1 +1 if v i = w j s i,j = max s i-1,j-1 -µ if v i w j s i-1,j - σ s i,j-1 - σ
4 Identity A C C T G A G – A G A C G T G – G C A G Identity = 70% mismatch indel
5 Измерение схожести – Идентичность – Консервативность
6 Матрицы весов Для ДНК составим (4+1) x(4+1) матрицу весов δ. Для белков размер матрицы (20+1)x(20+1). Дополнительные строка и столбец нужны для включения gap символа. Это упростит алгоритм следующим образом: s i-1,j-1 + δ (v i, w j ) s i,j = max s i-1,j + δ (v i, -) s i,j-1 + δ (-, w j )
7 Создание матриц весов Матрицы создаются на основе экспериментальных данных. Выравнивания – представления белков, различающихся мутациями. Некоторые из этих мутаций менее пагубно влияют на функцию белка, и, соответственно, штраф δ(v i, w j ), будет меньше прочих.
8 Пример матрицы весов ARNK A5-2 R-7 3 N--70 K---6 Несмотря на то, что R и K разные аминокислоты, их пара имеет положительный вес. Почему? Обе являются положительно заряженными полярными аминокислотами
9 Консервативность Замены аминокислот, сохраняющие физико-химические свойства белков. – Полярные на полярные аспартат глутамат – Неполярные на неполярные аланин валин – Прочие похожие лейцин на изолейцин
10 Типы матриц весов Матрицы замен аминокислот – PAM – BLOSUM ДНК матрицы
11 PAM Point Accepted Mutation (Dayhoff et al.) 1 PAM = PAM 1 = 1% аминокислот мутировали. – Однако после 100 PAMов эволюции, не все остатки изменятся Некоторые остатки мутируют несколько раз Некоторые остатки вернутся к начальному состоянию Некоторые вообще не изменятся
12 PAM X PAM x = PAM 1 x – PAM 250 = PAM PAM 250 широко используемая матрица: Ala Arg Asn Asp Cys Gln Glu Gly His Ile Leu Lys... A R N D C Q E G H I L K... Ala A Arg R Asn N Asp D Cys C Gln Q Trp W Tyr Y Val V
13 BLOSUM Blocks Substitution Matrix Веса извлекаются из статистики выравниваний родственных белков Название отображает расстояние между белками выборки – BLOSUM62 была создана на выборке последовательностей с 62% identity
14 Матрица весов BLOSUM50
15 Локальное выравнивание Задача глобального выравнивания – найти наиболее весомый путь между вершинами (0,0) и (n,m) графа. Задача локального выравнивания – найти наиболее длинный путь среди всех путей между вершинами (i,j) и (i, j ). В графе с ребрами с отрицательными весами локальное выравнивание может давать более высокий результат нежели глобальное
16 Глобальное выравнивание Локальное выравнивание – лучше находит консервативные сегменты. --T-CC-C-AGT-TATGT-CAGGGGACACGA-GCATGCAGA-GAC | || | || | | | ||| || | | | | |||| | AATTGCCGCC-GTCGT-T-TTCAG----CA-GTTATGT-CAGAT--C tccCAGTTATGTCAGgggacacgagcatgcagagac |||||||||||| aattgccgccgtcgttttcagCAGTTATGTCAGatc
17 Как? Global alignment Local alignment Мини-Глобальное выравнивание сегмента Время работы - O(n4)
18 Решение – free ride Вершина (0,0) Yeah, a free ride!
19 Алгоритм локального выравнивания Наибольшее значение s i,j – лучший вес локального выравнивания. Рекурсия: 0 s i,j = max s i-1,j-1 + δ (v i, w j ) s i-1,j + δ (v i, -) s i,j-1 + δ (-, w j ) Лишь одно отличие от глобального выравнивания.
20 Взвешивание делеций/вставок: простой подход. Фиксированный штраф σ за каждую делецию/вставку: – -σ за одну делецию, – -2σ за две делеции подряд, – -3σ за три делеции подряд, и т.д.
21 Афинный штраф за gap В природе, серии последовательных k делеций происходят чаще, чем k одиночных событий: Обычное взвешивание оценит эти два выравния одинаково Более предпочтительно Менее предпочтительно
22 Gaps Gap – непрерывный пропуск в одной из последовательностей. Вес гэпа длины x: -(ρ + σx) где ρ >0 - штраф за открытие гэпа, а σ – штраф за продолжение гэпа. ρ >> σ
23 Афинный штраф за гэпы – -ρ-σ за одну делецию 1 indel – -ρ-2σ за две делеции 2 indels – -ρ-3σ за три делеции 3 indels, etc.
24 Добавление ребер афинных штрафов. Сложность возрастает с O(n 2 ) до O(n 3 ) Как бы сделать попроще?
25 3-leveled Manhattan ρ ρ σ σ δ δ δ δ δ
26 The 3-leveled Manhattan Grid
27 Переключение между уровнями Уровни: – Основной уровень для диагональных ребер – Нижний уровень для горизонтальных ребер – Верхний уровень для вертикальных ребер Штраф за переход с основного уровня на верхний или нижний (с шагом) (- ) Штраф за проход по верхнему или нижнему уровню (- )
28 Алгоритм 3-х уровнего подхода s i,j = s i-1,j - σ max s i-1,j –(ρ+σ) s i,j = s i,j-1 - σ max s i,j-1 –(ρ+σ) s i,j = s i-1,j-1 + δ (v i, w j ) max s i,j s i,j Продолжит гэп в w (делеция) Начать гэп в w (делеция): с середины Продолжить гэп в v (вставка) Начать гэп в v (вставка): с середины Совпадение или несовпадение Закончить делецию: сверху Закончить вставку: снизу
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.