Алгоритмы выравнивания Артем Артемов, Светлана Виноградова 2012

Эволюционный смысл выравнивания Выравнивание должно отражать эволюцию последовательностей с общим предком. Гомологи – последовательности, имеющие общего предка Следует ли из сходства последовательностей наличие общего предка? – Зависит от степени сходства – Другие соображения: 3D структура, …

Как сравнить 2 выравнивания между собой? Рассмотрите 2 последовательности: LILEPSHFQ LELSHVQ Какие можно предложить выравнивания? Какое лучше? Как одним числом оценить качество выравнивания? LILEPSHFQ LEL--SHVQ LILEPSHFQ --LELSHVQ

# Matrix made by matblas from blosum62.iij # * column uses minimum score # BLOSUM Clustered Scoring Matrix in 1/2 Bit Units # Blocks Database = /data/blocks_5.0/blocks.dat # Cluster Percentage: >= 62 # Entropy = , Expected = A R N D C Q E G H I L K M F P S T W Y V B Z X * A R N D C Q E G H I L K M F P S T W Y V B Z X *

Вес выравнивания Вес выравнивания = 25 Sequence 1LEL––SHVQ Sequence 2LILEPSHFQ Вес позиции4–34–4 48–15

Карта локального сходства LILEPSHFQ L E L S H V Q LILEPSHFQ LEL--SHVQ LILEPSHFQ L E L S H V Q LILEPSHFQ --LELSHVQ

Веса сопоставленных букв LILEPSHFQ L4 E-3 L4 S4 H8 V Q5 LILEPSHFQ LEL--SHVQ LILEPSHFQ L4 E5 L7 S4 H8 V Q5 LILEPSHFQ --LELSHVQ

Как учитывать гэпы? LILEPSHFQ L4 E-3 L4 S4 H8 V Q5 LILEPSHFQ LEL--SHVQ LILEPSHFQ L4 E5 L-3 S4 H8 V Q5 LILEPSHFQ --LELSHVQ -4 Вес = 13 Вес = 14

Идея алгоритма выравнивания Рассмотрим ячейку, где начальные фрагменты LILEPS и LELS как- то сопоставлены Для неё можем записать максимальный вес выравнивания этих частей последовательности Так делаем для каждой ячейки, двигаясь сверху вниз и слева направо Для расширения выравнивания достаточно знать веса оптимального выравнивания более коротких фрагментов LILEPSHFQ LEL--SHVQ LILEPSHFQ --LELSHVQ LILEPSHFQ L E L S61 H218 V Q

Шаг алгоритма выравнивания Хотим выровнять: – LILEPSH – LELSH Знаем, как выравнивать все «начала» последовательностей не длиннее данных Какие варианты: 1. H и H выровнено: LILEPS HFQ LELS HVQ Как-то оптимально выровнено 2. Гэп в п.1: LILEPSH -FQ LELS HVQ Как-то оптимально выровнено 3. Гэп в п.2: LILEPS HFQ LELSH -VQ Как-то оптимально выровнено

Шаг алгоритма выравнивания LILEPSHFQ L E L S 61 H 2? V Q (LILEPS, LELS) (LILEPSH, LELSH) Вес: 6+вес(H,H)=6+8=14 Вариант 1. Буквы H и H сопоставлены

Шаг алгоритма выравнивания LILEPSHFQ L E L S 61 H 2? V Q (LILEPS, LELSH) (LILEPSH, LELSH) Вес=2-штраф_за_гэп=2-4=-2 Вариант 2. Буква H в вертикальной последовательности соответствует гэпу в горизонтальной

Шаг алгоритма выравнивания LILEPSHFQ L E L S 61 H 2? V Q Вариант 3. Буква H в горизонтальной последовательности соответствует гэпу в вертикальной (LILEPSH, LELS) (LILEPSH, LELSH) Вес=1-штраф_за_гэп=1-4=-3

Шаг алгоритма выравнивания LILEPSHFQ L E L S 61 H 214 V Q (LILEPS, LELS) (LILEPSH, LELSH) Вес: 6+вес(H,H)=6+8=14 Находим максимальный вес – в первом парианте

Идея алгоритма выравнивания LILEPSHFQ 0 L E L S H V Q

Идея алгоритма выравнивания -L-L LILEPSHFQ 0 L -4 E L S H V Q

Идея алгоритма выравнивания ? LILEPSHFQ 0 L -4 E L S H V Q

Идея алгоритма выравнивания L-L- LILEPSHFQ 0-4 L E L S H V Q

Идея алгоритма выравнивания -- LE LILEPSHFQ 0-4 L E -8 L S H V Q

Идея алгоритма выравнивания ? LILEPSHFQ 0-4 L E -8 L S H V Q

Идея алгоритма выравнивания LLLL LILEPSHFQ 0-4 L 4 E -8 L S H V Q Вес = max (0+4, #match -4-4, -4-4) = 4

Идея алгоритма выравнивания LI L LILEPSHFQ L -440 E -8 L S H V Q Вес = max (-4+2, #match -8-4, 4-4) = 0 LI L-

Идея алгоритма выравнивания LILEPSHFQ L -440 E -80 L S H V Q Вес = max (-4-3, #match 4-4, -8-4) = 0 L- LE

Идея алгоритма выравнивания LILEPSHFQ L -440 E -801 L S H V Q Вес = max (4-3, #match 0-4, 0-4) = 1 LI LE

Локальное выравнивание Основное отличие в том, что оно может начаться и закончиться в любой клеточке LILEPSHFQ G -2 P S H W Вес = max (-2+7, match -2-4, -1-4, 0+7 начать выравнивание с этой позиции ) = 7

Аффинные штрафы за делецию Два гэпа подряд лучше, чем два одиночных гэпа в разных местах Штраф за открытие гэпа (большой) и штраф за его расширение на 1 позицию (меньше). Число гэпов подряд Штраф 1

Существующие алгоритмы алгоритм Нидельмана – Вунша (Needleman – Wunsch, 1970) – для полных выравниваний алгоритм Смита – Уотермэна (или Смита – Ватермана, Smith – Waterman, 1981) – для частичных выравниваний