Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
В гл. "Поиск гомологий" описаны алгоритмы поиска выравниваний максимального веса. Получить аналитические формулы для статистических характеристик оптимального выравнивания довольно сложно в связи с большим числом потенциальных выравниваний. Этот вопрос рассматривается ниже (см. "Статистическая значимость оптимального выравнивания" ).
Точечные матрицы. Сходство между двумя нуклеотидными последовательностями можно визуализовать на точечной матрице (dot- matrix) (рис.1.1 гл. "Поиск гомологий"). При построении точечной матрицы фиксируется размер окна W и рассматриваются пары окон, одно из которых начинается в позиции i последовательности X, а другое - в позиции j последовательности Y. Если последовательности X и Y, попавшие в выбранные окна похожи (например, уровень сходства между ними превышает 0.75W в модели фиксированного выравнивания), то на пересечении i-й строки и j-ro столбца точечной матрицы ставится точка. В результате гомологичным участком в X и Y будут соответствовать некоторые (идущие параллельно диагонали) линии из точек в точечной матрице. Вопросы выбора параметров при построении точечных матриц и связанные с ними вопросы статистической значимости гомологий обсуждаются ниже (см. "Гомологии и точечные матрицы.").
Теоретические оценки для длины максимальной общей подпоследовательности и максимального общего подслова. Изучение статистических характеристик для длины максимальной общей подпоследовательности началось в работе Хватала и Санкоффа (Chvatal,Sankoff,1975), где были
L
получены нижние и верхние оценки для величины lim — (через L
п-->» п
обозначено математическое ожидание длины максимальной общей подпоследовательности последовательностей Х=х,........хп и Y=y,,..,yn). Легко
показать, что функция L супераддитивна, т.е. Lktm > Lk+Lm. Отсюда следует, что
L L
lim — - sup — = S .
п—>оо п п п
Нижние оценки для S были получены с помощью построения простых алгоритмов нахождения общих (не обязательно максимальных) подпосле-доательностей. Хваталу, Санкоффу и Декену (Chvatal,Sankoff,1975; Deken,1979) удалось оценить вероятностное поведение этих алгоритмов и в качестве нижней оценки использовать длину получающихся последовательностей. При построении верхних оценок для S рассматриваются оценки для числа пар последовательностей X и Y, содержащих общую последовательность Z длины m (m=<n), и проводится усреднение по все
возможным последовательностям Z.
С помощью этой техники показано, что для 4-буквенного алфавита
0,5454 < S < 0,7181 .
В дальнеДпщм Cmfl,,.j(-Steele, 1982) показал, что дисперсия распределения длины максимальной общей подпоследовательности невелика и оценивается как 0(п). Вопрос о более точных оценках для описания параметров распределения длины максимальной общей подпоследовательности остается открытым, однако уже приведенные результаты могут быть использованы для оценки статистической значимости длины максимальных общих подпоследовательностей.
Если длина максимальной общей подпоследовательности оценивается как 0(п), то длина максимального общего поделова имеет порядок O(logn). Арратиа и Ватерман (Waterman,1984; Arratia,Waterman,1985; Waterman,1986) показали (тот же результат в несколько другой форме был получен Karlin et al.,1983), что математическое ожидание M(n,m) длины максимального общего подслова двух слов длины пит оценивается как
M(n,m)=log((l-p)nm) + а/р - 1/2 +г,(п,т) + 0(1) ,
а дисперсия D(n,m) как
D(n,m)= n2/(6p2) + 1/12 + r2(n,m) + 0(1).
Здесь логарифм берется по основанию 1/р (р - вероятность совпадения двух произвольно взятых нуклеотидов в рассматриваемых последовательностях), а-0,577... - константа Эйлера-Машерони, р=1п(1/р), а величины г, и г2 относительно невелики. Для случая максимальных общих подслов с к дефектами эти оценки имеют вид
M(n,m)=log(nm) + kloglog(nm) + (k+l)log(l-p) - log(k!) + k + a/p - 1/2 +r,(n,m) + 0(1),
D(n,m)= n2/(6p2) + 1/12 + r2(n,m) + 0(1).
Интересно отметить, что изучение статистических характеристик уровня локальной гомологии (см. гл. "Поиск гомологий"), проведенное с помощью метода Монте-Карло, также дало логарифмическую оценку (Smith et al.,1985).
Статистическая значимость оптимального выравнивания. В работах Хватала, Санхоффа и Райха с соавт. ( Chvatal.Sankoff,1975; Reich et al.,1984) для n<8 с помощью перебора на ЭВМ были получены гистограммы распределения уровня гомологии. Оказалось, что математическое ожидание m уровня оптимального выравнивания лежит в пределах 50-60% (при нулевых штрафах за замены и удаления), а дисперсия s относительно мала (т.е. распределение имеет вид пика).
Известны попытки анализа статистических характеристик уровня гомологии методом статистического моделирования. Райх и др. (Reich et al.,1984) предлагают следующие эмпирические формулы, полученные после аппроксимации результатов моделирования уровня гомологии с помощью метода Монте-Карло (vd,vc=0):
