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

Простое взвешивания +1 : вес совпадения -μ : штраф за несовпадение -σ : штраф за делецию/вставку Вес выравнивания = #совпадения – μ(#несовпадений) – σ (#делеций/вставок)

Алгоритм = -б = 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 - σ

Identity A C C T G A G – A G A C G T G – G C A G Identity = 70% mismatch indel

Измерение схожести – Идентичность – Консервативность

Матрицы весов Для ДНК составим (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 )

Создание матриц весов Матрицы создаются на основе экспериментальных данных. Выравнивания – представления белков, различающихся мутациями. Некоторые из этих мутаций менее пагубно влияют на функцию белка, и, соответственно, штраф δ(v i, w j ), будет меньше прочих.

Пример матрицы весов ARNK A5-2 R-7 3 N--70 K---6 Несмотря на то, что R и K разные аминокислоты, их пара имеет положительный вес. Почему? Обе являются положительно заряженными полярными аминокислотами

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

Типы матриц весов Матрицы замен аминокислот – PAM – BLOSUM ДНК матрицы

PAM Point Accepted Mutation (Dayhoff et al.) 1 PAM = PAM 1 = 1% аминокислот мутировали. – Однако после 100 PAMов эволюции, не все остатки изменятся Некоторые остатки мутируют несколько раз Некоторые остатки вернутся к начальному состоянию Некоторые вообще не изменятся

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

BLOSUM Blocks Substitution Matrix Веса извлекаются из статистики выравниваний родственных белков Название отображает расстояние между белками выборки – BLOSUM62 была создана на выборке последовательностей с 62% identity

Матрица весов BLOSUM50

Локальное выравнивание Задача глобального выравнивания – найти наиболее весомый путь между вершинами (0,0) и (n,m) графа. Задача локального выравнивания – найти наиболее длинный путь среди всех путей между вершинами (i,j) и (i, j ). В графе с ребрами с отрицательными весами локальное выравнивание может давать более высокий результат нежели глобальное

Глобальное выравнивание Локальное выравнивание – лучше находит консервативные сегменты. --T-CC-C-AGT-TATGT-CAGGGGACACGA-GCATGCAGA-GAC | || | || | | | ||| || | | | | |||| | AATTGCCGCC-GTCGT-T-TTCAG----CA-GTTATGT-CAGAT--C tccCAGTTATGTCAGgggacacgagcatgcagagac |||||||||||| aattgccgccgtcgttttcagCAGTTATGTCAGatc

Как? Global alignment Local alignment Мини-Глобальное выравнивание сегмента Время работы - O(n4)

Решение – free ride Вершина (0,0) Yeah, a free ride!

Алгоритм локального выравнивания Наибольшее значение 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 ) Лишь одно отличие от глобального выравнивания.

Взвешивание делеций/вставок: простой подход. Фиксированный штраф σ за каждую делецию/вставку: – -σ за одну делецию, – -2σ за две делеции подряд, – -3σ за три делеции подряд, и т.д.

Афинный штраф за gap В природе, серии последовательных k делеций происходят чаще, чем k одиночных событий: Обычное взвешивание оценит эти два выравния одинаково Более предпочтительно Менее предпочтительно

Gaps Gap – непрерывный пропуск в одной из последовательностей. Вес гэпа длины x: -(ρ + σx) где ρ >0 - штраф за открытие гэпа, а σ – штраф за продолжение гэпа. ρ >> σ

Афинный штраф за гэпы – -ρ-σ за одну делецию 1 indel – -ρ-2σ за две делеции 2 indels – -ρ-3σ за три делеции 3 indels, etc.

Добавление ребер афинных штрафов. Сложность возрастает с O(n 2 ) до O(n 3 ) Как бы сделать попроще?

3-leveled Manhattan ρ ρ σ σ δ δ δ δ δ

The 3-leveled Manhattan Grid

Переключение между уровнями Уровни: – Основной уровень для диагональных ребер – Нижний уровень для горизонтальных ребер – Верхний уровень для вертикальных ребер Штраф за переход с основного уровня на верхний или нижний (с шагом) (- ) Штраф за проход по верхнему или нижнему уровню (- )

Алгоритм 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 (вставка): с середины Совпадение или несовпадение Закончить делецию: сверху Закончить вставку: снизу