Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
Различные подходы к понятию сходства генетических текстов. В этом разделе задачи поиска гомологий рассматриваются, в отличие от гл. "Поиск гомологий" как задачи поиска подпоследовательностей специального вида ( такой подход удобнее при анализе статистической значимости гомологий).
Фиксированное выравнивание. Если рассматриваются две последовательности одной и той же длины п Х=(х,,...,хп ) и Y=(y, ,...,уп),то уровень и фиксированного выравнивания между ними определяется, как количество индексов i, для которых х,-=у,. Вероятность события х,=у, равна (через pB(qB) обозначена вероятность появления буквы В в последовательности Х(Y))
Р “ РдЧд+РтЧт+Ро^+РсЧс-Статистические характеристики уровня сходства и как случайной величины в модели фиксированного выравнивания легко подсчитываются:
V V ri — ]/•
P{u=k} = С *p *(l-p)* , n
m=p-n , s-p*(l-p)’n
(здесь m и s - математическое ожидание и дисперсия для величины и в модели фиксированного выравнивания).
Максимальные общие подпоследовательности и подслов а. Фиксированное выравнивание, как правило, не рассматривается в качестве меры сходства, поскольку оно не допускает "сдвигов" между сравниваемыми последовательностями.
ATCGATGA ATCGATGA ATCGATGA ATCGATGA
а | II б Г//\“11 в ^ г /////
ACGTGAGA ACGTGAGA ACGTGAGA ACGTGAGA
Р и с. 2.9.Различные подходы к понятию сходства
а - фиксированное выравнивание; б - максимальная общая подпоследовательность; в - максимальное общее подслово; г - максимальное общее подслово с одним дефектом
При анализе генетических текстов иногда ищут максимальные общие подпоследовательности и подслова. Последовательности X=ATCGATGA и Y=ACGTGAGA имеют при фиксированном выравнивании уровень гомологии 2, в то время как длина максимальной общей подпоследовательности для них равна 6 ,а длина максимального общего подслова - 3 (рис.2.9). Общая подпоследовательность для последовательностей Х=х,,...,хп и
Y=y,.....yk - это набор индексов (i,, j,),...,(it, jt ),...,(im, jj,
удовлетворяющий условиям
i|< ••• <it <•.••<!. .
j,< ... <jt
и Xj=yj для любого t=l,m.
Общее подслово -это набор индексов
(i+1,j+1).......(i+t,j+t),...,(i+m,j+m),
удовлетворяющий условию x1+t=yjtt при t=l,m. Число m называется длиной общей подпоследовательности(подслова).
Таким образом, общее подслово - это общая подпоследовательность с дополнительным условием: буквы в ней расположены подряд. Если "ослабить" определение максимальных общих подслов и рассмотреть максимальные общие слова с одним допустимым дефектом в каждой из последовательностей X и Y на рис.2.9, то получится, что длина такого максимального общего подслова равна 5 (на рис.2.9,д подчеркнутая буква А в X образует "дефект").
Если разрешить два удаления, то мы придем к тому же результату, что и при рассмотрении максимальных общих подслов (рис.2.96, буквы, образующие "дефекты" выделены подчеркиванием).
Таким образом, понятия максимального общего подслова с к дефектами и максимальной общей подпоследовательности при достаточно больших к совпадают. Вероятностные распределения для длины максимальных общих подпоследовательностей и подслов рассматриваются ниже (см. "Теоретические оценки для длины максимальной общей подпоследовательности и максимального общего подслова.").
Оптимальное выравнивание. Выравнивание последовательностей Х=х,,... ,хп и Y=yt,... ,yk - это последовательность пар индексов <i1,j1),...<it,jt),...(ini,jm),удовлетворяющая условию
i,< ... <it <----<im,
j,< ... <jt <-...<jm
(в отличие от определения общей подпоследовательности, для выравнивания не требуется выполнения условияи х, =у. для любого t=l,m).
Пары (i,j), для которых, х^у^называются совпадениями, а пары, для которых х^у^- заменами. Элементы последовательности X(Y), не вошедшие ни в одну пару, называются удалениями в X (в Y). Удаления в
Y иногда называют также вставками. Такое определение выравнивания эквивалентно введенному в главе "Поиск гомологий".
Под весом выравнивания, как и в гл. "Поиск гомологий", понимается
число vrnkm-vckc-vdkd, где vm - премия за совпадение (match); vo -
штраф за замену (change); vd - штраф за удаление (deletion); km,kc, kd - количество совпадений, замен и вставок соответственно.
Под оптимальным выравниванием понимается выравнивание с максимальным весом, а под уровнем сходства последовательностей X и Y (в модели с штрафами) - вес оптимального выравнивания X и Y .
Если принять штрафы за замены и делеции равными нулю (vc,vd=0), то мы придем к простейшему варианту задачи о выравнивании, когда поиск оптимального выравнивания эквивалентен поиску максимальной общей подпоследовательности. При поиске оптимальных выравниваний случайных последовательностей с этими параметрами обычно оказывается, что 60% приходится на совпадения, 20% - на замены и 20% на делеции. Если мы будем увеличивать vd от 0 до » , то большие штрафы за делеции приведут к тому, что число замен в оптимальном выравнивании возрастет, а число делеций уменьшиться. При vd=« и n=k мы приходим к модели фиксированного выравнивания. Нас интересует вопрос о том, какой уровень оптимального выравнивания между последовательностями следует считать значимым, т.е. при каком уровне оптимального выравнивания можно делать выводы об эволюционной или функциональной близости рассматриваемых фрагментов.
