Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
3 4 Б 4 2 • I
слишком много негомологичных последовательностей имеют близкие оуквен-ные составы. Это связано прежде всего с тем, что буквенный состав никак не учитывает порядок следования букв. Использование дибуквенного состава существенно более сильный фильтр, поскольку в нем в какой-то мере учтен порядок букв. Если же еще использовать разнесенные диграммы, то порядок следования букв будет учтен еще полнее. Таким образом, чтобы сравнить две последовательности, необходимо подсчитать количества двухбуквенных сочетаний Еида XY, X-Y, X—Y и т.д. для каждой последовательности и затем сравнить полученные наборы чисел - если они будут близки, то последовательности могут быть (но не обязательно будут) гомологичными, в противном случае они заведомо не гомологичны. Максимальная степень к разнесенности двоек является параметром алгоритма: чем больше к, тем более жестким фильтром является соответствующее необходимое условие гомологии, но тем больше времени требуется для его проверки.
Отличие диграммного состава может служить мерой расстояния между последовательностями, однако в таком виде она неудобна. Действительно, если при сравнении двух последовательностей длиной 100 при к=3 это расстояние оказалось равным 85, а при сравнении двух других последовательностей длиной 800 при к=5 - 370, то, что из этого следует? Какое расстояние следует считать случайным, а какое указанием на возможность гомологии? Для решения этих проблем разумно нормировать диграммные составы следующим образом. Рассмотрим последовательность S длиной N. Характеристической функцией e(i,X) буквы X будем называть величину, которая равна 1 во всех позициях последовательности, где встречается буква Х?и равна 0 в остальных позициях:
1, S(i)-X
е(i,X)=
0, S(i)A .
Через эту функцию удобно записать буквенный, диграммный, 1-" грамм-ный состав последовательности
a(X)-Ee(i,X),
S
а(Х,У, d)=Se(i,X)*e(i+d,Y),
S
а(Х,Y.....Z,dl,...,dl)=Se(i,X),e(i+dl,Y)•...*е(i+dl,Z).
S
Обозначим вероятность появления буквы X через р(Х) и зададим нормированный диграммный состав формулой
b(X,Y,d)=(l/ (N-d) )2 [e( i,X)-p(X)]*[e(i+d,Y)-p(Y)]. (1.5)
S
Тогда расстояние между последовательностями определим как
r(S,,S2) = (l/k)S[b1(X,Y,d)-b2(X,Y,d)]2 . (1.6)
d < k
X,Y - по всему алфавиту
Формула (1.6) обладает тем преимуществом, что определяемое ею расстояние универсально: его математическое ожидание не зависит от длины
последовательности. На рис.1.17 приведена плотность распределения ве-
2
Рис. 1.17. Плотность распределения вероятностей для статистического расстояния между двумя случайными последовательностями
m = 1 ,825
роятностей расстояния между двумя случайными последовательностями. Математическое ожидание расстояния между двумя случайными нуклеотидными последовательностями (р(Х)=0,25) равно т=1,825.
Посмотрим теперь на свойства расстояния (1.6). Пусть две последовательности длиной N отличаются друг от друга заменой или делецией. Тогда в них различаются 2(к+1) и к(к+4)/2 диграмм, и расстояние между ними будет соответственно равно
ro=2(k+l)/N; rd=k(k+4)/N. (1.7)
Глядя на формулы (1.7), можно сказать, что расстояние г характеризует плотность числа дефектов гомологии. Отметим еще важное свойство расстояния г. Пусть две последовательности длиной N, и N2 имеют совпадающий участок длиной N. Тогда математическое ожидание расстояния между ними равно
M[r(S,,S2)]=m*[l- (h,*h2)],
где m - математическое ожидание расстояния между случайными последовательностями, h,=N/N,f h2=N/N2. Последнее свойство расстояния г означает, в частности, что при сдвиге последовательностей друг относительно друга расстояние будет увеличиваться, но незначительно, и поэтому оно позволяет улавливать гомологии на сдвинутых друг относительно друга
2 Заказ № 4327 ГЗГЗ
последовательностях. Наконец, расстояние г мало чувствительно к блочным перестановкам в последовательностях.
Алгоритм поиска гомологий по банку последовательностей выглядит так. Тестируемая последовательность разбивается на протяженные фрагменты, длина которых L примерно равна ожидаемому размеру гомологии. При этом, чтобы учесть возможность несовпадения начал отсчета последовательностей, это разбиение делается дважды - со сдвигом на L/2 или трижды - со сдвигом на L/3 (обычно используется L=200). Банк последовательностей также разбивается на фрагменты длиной L. На каждом из фрагментов тестируемой последовательности и банка определяется нормированный диграммный состав по формуле (1.5) (для банка такую работу можно сделать заранее), и для каждой пары фрагментов вычисляется расстояние г по формуле (1.6). Если расстояние г меньше порогового значения г0 (обычно ro=0,3m), то эта пара фрагментов имеет много шансов на гомологию. Трудоемкость этого алгоритма оценивается величиной a2*k'N,•Nj/L2, где а - размер алфавита. Из этой формулы видно, что чем длиннее искомая гомология, тем эффективнее работает алгоритм. На поиск гомологии последовательности длиной 103 нуклеотидов по банку нуклеотидных последовательностей требуется всего порядка 107 операций, что вполне доступно персональному компьютеру средней мощности. Из формулы для трудоемкости следует, что если для нуклеотидных последовательностей (w-4) он достаточно эффективен, то для аминокислотных последовательностей (w=20) его применимость сомнительна. Однако в этом случае можно прибегнуть к редукции алфавита, как это делалось при применении метода 1-граммного разложения, и значительно сократить время работы.
