Точечная матрица

Рис. 1.1. Построение точечной матрицы гомологии. Линии соответствуют гомологиям

Р и с.. 3. Пример точечной матрицы гомологии фрагмента последовательности Deo оперена Е. соИ с самим собой при параметрах фильтрации к=12, 1=16 (1) и к=31, 1=63 (б) [c.14]

Р и с. 1.10. Путь на точечно матрице гомологии (а" и ооо ветствующее выравнивание (б [c.20]

Метод динамического программирования. Чтобы описать алгоритм построения оптимального выравнивания, попробуем представить себе геометрический образ выравнивания. Для этого вспомним точечную матрицу гомологии (рис.1.10). Любую линию на зтой матрице, идущую либо вверх, либо вправо, либо вправо - вверх параллельно диагонали условимся называть путем по точечной матрице гомологий. Нетрудно догадаться, что любой путь по матрице из левого нижнего в правый верхний угол отвечает некоторому выравниванию, причем движение вверх или вправо отвечает делеции в одной из последовательностей, а при движении параллельно диагонали прохождение через пустые клетки соответствуют заменам, прохождение через точки - совпадениям. Например, пути рис.1.10,а соответствует выравнивание 1.10,6. Задача оптимального выравнивания, таким образом, сводится к поиску наилучшего пути по матрице гомологии. При поиске этого пути будем одновременно строить матрицу наилучших значений функции сходства F(i,j) - есть значение функции сходства, отвечающее оптимальному пути из левого нижнего угла матрицы гомологий в точку (i,j). Если известны значения функции сходства в точках (i-l,j), (i,j-1) и (i-l,j-l) и оптимальные пути в эти точки, то можно найти значение функции сходства для наилучшего пути, ведущего из точки (1,1) в точку (i,j), и определить этот путь. Оптимальное значение функции определяется по формуле [c.22]

Гомологии и точечные матрицы. Часть точек при построении точечной матрицы может появиться вследствие случайных причин. Ясно,что такой "фон" является помехой для биолога, анализирующего точечную матрицу. Если задаться некоторым уровнем значимости (например, 0,99), то можно поставить вопрос как выбрать параметры построения точечной матрицы (т.е. при каком уровне гомологии в окне следует ставить точку), для того чтобы вероятность появления "случайной" точки не превышала 1-0,99 Иными словами, биологу нужно выбирать такие параметры построения точечных матриц, которые исключают (при некотором уровне значимости) "случайные" точки. [c.73]

V можно оценить вероятность Q того, что диагональ в точечной матрице размера п окажется свободной от штрихов [c.74]

Одной из наиболее часто применяемых функций анализа последовательностей является построение так называемых точечных матриц гомологии (гл. 1). Эти матрицы, особенно при удачном подборе параметров фильтрации, дают ценную информацию о гомологичных областях последовательностей (рис. 7.7). [c.239]

Рус. 9-34. Точечные матрицы, показывающие расположение экзонов в гене Р-глобина человека (А) и соотношение между гомологичными последовательностями мыши и экзонами гена человека (Б) (ответ [c.387]

Для решения задач о поиске гомологий разработаны эффективные алгоритмы и соответствующие прогршлмы. Однако, пожалуй, наибольшей популярностью среди биологов пользуются програмтда, прямо не решающие ни одну из перечисленных задач. Это - программы построения так называемых точечных матриц гомологии. Они очень наглядны и не требуют от исследователя точного знания, какого типа гомология его интересует. [c.12]

Точечные матрицы гомологии. Построение так называемых точечных матриц гомологий (с л., ь пр1 мер, Gibls, M Intyre. 1970) ЯЕ.чяется одч М наиболее популярных мэтодоз поиска гомологий, Суть метода сводится к следующему. Пусть требуется сравнить последовательности S, и длиной N, и Nj соответственно. Для анализа этих последовательностей строится прямоугольник размером N/Nj (рис.1.1), по верхней стороне прямоугольника выписывается (или подразумевается) первая последовательность, по [c.13]

Рис. 1.2.Зависимость вероятности появления точки на точечной матрице гомологии от отношения(т1пчисло совпадений)/ (длина окна) при разных размерах окна 1 для нуклеотидных (а) и аминокислотных (б) последовательностей

Простейшие методы поиска общего слова. Опшем теперь методы решения задач 1 и 2, к которым сводится задача построения точечной матрицы гомологии. Простейший алгоритм заключается в следующем (рис.1.4.). Последовательность S, со сдвигом накладывается на последовательность Sj. По общей части этих последовательностей пробегает окно длиной w. В каждом положении окна подсчитывается число совпадающих букв. Если это число превышает пороговое значение к, значит найдена пара гомологичных участков. После просмотра всех возможных наложений S, на и всех возможных положений окна задача 2 считается решенной. Число операций, которые выполняются при работе этого алгоритма, оценивается выражением число возможных наложений последовательностей число возможных положений окна-длина окна=М,-N w, и для большинства реальных задач составляет величину порядка IG . Иными словами, этот простой алгоритм достаточно трудоемок. [c.16]

При описании точечных матриц гомологии говорилось о проблеме фильтрации. В качестве альтернативы описанному методу фильтрации можно использовать следующий фильтр точка ставится в том случае, если она принадлежит локальной гомологии (Staden, 1582). В этом случае точечная матрица гомологии выступает в качестве спсссба визуализации результатов поиска гомологий . [c.29]

Вилбур и Липман (Wilbur, Lipraan, 1983) предложили следующий метод поиска гомологий по банку последовательностей. Представим себе точечную матрицу гомологий, построенную для тестируемой последовательности и банка последовательностей (рис.1.16) при параметрах фильтрации длина окна 1, число ошибок 0. Для построения такой матрицы применим метод [c.30]

Точечные матрицы. Сходство между двумя нуклеотидными последовательностями можно визуализовать на точечной матрице (dot- matrix) (рис.1.1 гл. "Поиск гомологий"). При построении точечной матрицы фиксируется размер окна W и рассматриваются пары окон, одно из которых начинается в позиции i последовательности X, а другое - в позиции j последовательности Y. Если последовательности X и Y, попавшие в выбранные окна похожи (например, уровень сходства между ними превышает 0,75W в модели фиксированного выравнивания), то на пересечении i-й строки и j-ro столбца точечной матрицы ставится точка. В результате гомологичным участком в X и Y будут соответствовать некоторые (идущие параллельно диагонали) линии из точек в точечной матрице. Вопросы выбора параметров при построении точечных матриц и связанные с ними вопросы статистической значимости гомологий обсуждаются ниже (см. "Гомологии и точечные матрицы."). [c.71]

Если мы сравниваем две последовательности длины 1000, то вероятность р проставления точки в произвольном месте должна быть достаточно низкой 10 или менее - в противном случае вся точечная матрица будет испещрена случайными точками. Какой должна быть р, для того чтобы с вероятностью 0,99 в точечной матрице для двух случайных последовательностей отсутствовали точки К сожалению, для решения этого вопроса нельзя привлечь модель испытаний Бернулли дело в том, что хотя проставления точек в точечной матрице - редкие события, однако они сильно коррелированы. Например, вероятность простав- [c.73]

Если положить Q=0,95, то следует выбирать v=0,05/n. Формулы для v (Rei h,Meiske,1987) позволяют выбрать параметры при построении точечных матриц. Так, например, если мы хотим оценить уровень фиксированного выравнивания в окне размера W, при котором следует ставить точку (Q=0,95), то можно использовать грубую оценку [c.74]

Рис. 9-5. Точечная матрица, позволяющая сравнить ген Р-глобина человека с кДНК для Р-глобина человека А) и с геном Р-глобина мыши (Б) (задача 9-6). Указаны 5 -и З -концы этих последовательностей. На обеих матрицах последовательность гена человека одна и та же, кДНК человека (А) короче, чем ген мыши (Б), поэтому диагональные линии на двух матрицах имеют разные наклоны.

Г. Исходя из точечной матрицы, представленной на рис. 9-5, В, можно заключить, что первые интроны имеют примерно одну и ту же длину в генах мыщи и человека, однако вторые интроны у них значительно различаются по длине. Если бы эти интроны имели одинаковую длину, то линейные сегменты, представляющие собой гомологичные области, лежали бы на одной и той же диагонали. Самый простой способ выявить подобную колинеарность-это наклонить страницу и посмотреть вдоль диагонали. На основе представленного сравнения невозможно определить, с чем связано [c.387]

Справочник химика 21

Химия и химическая технология