Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
F 1 S3 1 14 177 140 1 1 3 1 58 1 1 6 155 103 102 97 100 50 2 1 28 205 22
Y 1 47 1 1 0 160 122 1 12 143 99 144 92 85 77 8 3 5 5 39 36 1 94 36
W 184 147 18 1 152 148 174 130 177 128 1 1 0 101 1 1 5 88 6 1 67 2 1 5 6 1
последовательностях. Уровень сходства можно также рассчитать с использованием коэффициентов отличия физических свойств аминокислот, таких, кэ!к гидрофобнос.ть, заряд, объем боковой группы. Соответствующие параметры приведены в табл. 1.2 (Grantham,1974). При этом следует иметь в виду, что числа в табл. 1.2 характеризуют отличия свойств аминокислот, в то время кан таёд* ' 1.1 отражает их сходство. Поэтому при использовании табл. 1.2 в качестве критерия постановки точки следует использовать условие, что суммарный вес меньше заданной величины.
Простейшие методы поиска общего слова. Опишем теперь методы решения задач 1 и 2, к которым сводится задача построения точечной матрицы гомологии. Простейший алгоритм заключается в следующем (рис.1.4.). Последовательность S, со сдвигом накладывается на последовательность S2. По общей части этих последовательностей пробегает окно длиной w. В каждом положении скна подсчитывается число совпадающих букв. Если это число превышает пороговое значение к, значит найдена пара гомологичных участков. После просмотра всех возможных наложений S, на S2 и всех возможных положений окна задача 2 считается решенной. Число операций, которые выполняются при работе этого алгоритма, оценивается выражением: число возможных наложений последовательностей’число возмож-
ных положений окна’длина окнами,*N2*w, и для большинства реальных задач составляет величину порядка 1C7. Иными словами, этот простой алгоритм достаточно трудоемок.
о
Oj ТTGAAGTATCAAGGTGAGGG. . .
| - + + 4 - + + - +|
S2 GAATCTAGATGTATTCA. . .
Рис. 1.4. Простейший алгоритм поиска общего слова. Рамка соответствует бегущему окну
S. TTGAAGTATCAAGGTGAGGG...
|- + + + - + + -+Н-+ + - -t + - -n-l
GAATCTAGATGTATTCA.
Рис. 1.5. Улучшенный алгоритм поиска общего слова
Верхняя рамка - предыдущее положение окна; нижняя - новое положение окна
Трудоемкость этого алгоритма можно сократить примерно в w раз. Для этого достаточно сделать простое наблюдение (рис. 1.5). При сдвиге правой границы окна на одну позицию вправо число совпавших букв к* в окне увеличится на 1, если в окно попадет совпавшая пара и не изменится в противном случае. При сдвиге же левой границы окна на одну позицию вправо число к* уменьшится на 1, исли из окна вышла совпадающая пара букв и не изменится в противном случае. Таким образом, нет необходимости в каждом положении окна подсчитывать число совпадающих букв, а достаточно лишь следить за его изменением. Теперь алгоритм выглядит так: просматриваются все наложения последовательности S, на S.; при
каждом наложении подсчитываем число совпадений в крайнем левом положении окна, затем сдвигаем окно вправо и следим за изменением числа к* совпадений. В тех случаях, когда к* превысит пороговое значение счита-
ется, что найдена гомология. Этот алгоритм называют методом скользящей рамки. Его трудоемкость равна N,*N2.
Метод 1-граммного разложения. Описанные алгоритмы применимы для решения задач 1 и 2, однако для задачи 1 (поиск строгих гомологий без замен и делеций) можно предложить алгоритм, требующий всего N,+N2+a' операций, где а - число букв в алфавите (для нуклеотидных последовательностей а=4, для аминокислотных последовательностей m=20), а 1 -некоторое число, смысл которого будет пояснен ниже. Работа этого алгоритма также весьма проста (Karlin et al., 1983). По последовательностям S, и S2 составляем таблицы Т, и Т2 положений всех подслов (фрагментов) длиной 1 (например, таблицы положений всех гексануклеотидов) так, что каждой строке этой таблицы отвечает одно подслово. Например, последовательности TATGCA соответствует одна строка, а последовательности CTAGCG - другая и т.д.. Число строк в каждой такой таблице равно а1. -На рис.1.6 приведен пример построения такой таблицы. При достаточно большом 1 многие строки будут пустыми. Для нахождения гомологий между последовательностями в таблицах находим непустые строки - именно они и определяют гомологию. Остается только проследить за тем, что не-
АА
АТ
AG
Рис. 1.6. Разложение последова- т*
тельности по 1-граммам (1=2) I*
Сверху показана последователь- тс
ность; слева - 1-граммы; горизон- с»
тальные линии - найденные 1-граммы; справа изображена таблица 1-грам- сс
много разложения сд
