Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
f (х) =
О, если х или какой-либо потомок х является вложением _ 1, в противном случае.
Задача поиска вложений эквивалентна задаче поиска минимума f(х) на вершинах дерева Т. Примитивный подход к минимизации f(х) связан с анализом всех вершин дерева Т и требует перебора колоссального числа б**
Ч 6. 6 Ь, 7,30.36 (6.36). 4.6,8,17.,30
[Я-‘Ли
11 1
4. ti.fi. в к.зп.зв (8,зб},члд. гг. зо
[Б-36], [8-JS] [6 36]
1 0
(8.36},4.6.8д,3д (8,36),(Ч,30),6.8.12
16-36], [4-J0] [Ь'-Зб]
0 л
1в,зв},ч,в,в,п.;м 1д.зб),пг.щ,ш (В,36),(Ч,Щ,6,ВЛ №,ЗВ),(ЧАЗЩ.6,П
[в-зв].[ч-т].[аЩ [6 34]. [4-J0] [6-36].[B-4],[B-3Sl [в-зв]
1 а 1 в
(В,36).т.30),1.В.В (д.зв/Жзоити) («,зв),(члщ,вл IS.361,1ч,в.з111,/в,/г)
[б-х],[ч-я],ММ [6-зе]. [ч-зо] [6-м], [6-1?] [6-36]
1 о . 1 в
Р и с.5.8. Дихотомичное дерево ветвления(фрагмент). Каждой вершине соответствует прямоугольник, в первой строке которого представлена информация о разбиении,во второй - о запрещении объединения фрагментов, в третьей - значение функции оценки вариантов. В круглых скобках - информация об объединении фрагментов, в квадратных - о запрещении объединения (например, запись [6,36] означает, что фрагменты 6 и 36 объединяются, а запись [6-36] - что объединение фрагментов запрещено). В двойных прямоугольниках показаны вершины, соответствующие вложениям
вариантов. Поэтому для отсечения заведомо тупиковых вариантов используется минорирующая функция g(x): g(x)<f(x), которую можно вы-
числить, не прибегая к полному перебору. В качестве такой функции выберем функцию
g(x)= -
1, если в разбиении есть подмножество, не входящее ни в какую вилку
О, в противном случае.
При просмотре дерева Т вершины, в которых g(x)=l, отбрасываются вместе со всеми потомками. При реализации метода ветвей и границ возможно совместное использование функции g(x) и различных процедур отсечений (Fitch et al.,1983; Nolan et al.,1984). Следует отметить, что, несмотря на обилие предложенных подходов, поиск вложений явля-
ется самым трудным этапом при построении парных физических карт.
Проверка совместимости вложений и интервальные графы. После построения вложений АВ в А и в В производится проверка совместимости пар влсжений("склейка" вложений), при этом может быть использован метод интервальных графов (Waterman,Griggs,1986) или специальные процедуры (Nolan et al.,1984).
Для рестрикционной карты, представленной на рис.5.4,б, можно ввести матрицу инциденций(перекрытий):
КА,В)
0 1 1
1 О О
1 0 1
0 0 1
где А и В - сокращенные обозначения для рестриктаз HindiII и BamHI и
| 1, если k-й фрагмент рестриктазы А перекрыва-
Ikl(A,B) = -| ется с 1-м фрагментом рестриктазы В |_ 0, в противном случае.
Таким же образом вводятся матрицы
1(А,А+В)
ИВ, А+В) =
10 0 10 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0
0 110 0 0
1 0 0 0 0 0
0 0 0 1 1 1
где
I (А,А+В)= -|
1,если k-й фрагмент одиночной рестрикции А содержит 1-й фрагмент совместной рестрикции А+В
|_ 0,в противном случае
(матрица Ikl(B,A+B) определяется аналогично).
Заметим, что для любого i, i-я строка матрицы I(А,А+В) определяет i- вилку А, а i-я строка I(В,А+В) - i-вилку В(например, (10,9 + 2,7)
- 1-вилка А, а (7,7 + 4,8) - 1-вилка В). Таким образом, матрице 1(А,А+В) соответствует некоторое вложение АВ в А, а матрице 1(В,А+В)
- вложение АВ в В.
Матрицы инциденций используются при проверке совместимости вложений. Для построения парной физической карты после этапа поиска вложений можно перебирать всевозможные пары вложений и для каждой
4
н
1
2
В
3
Р и с.5.9. Граф G(H,B) физической карты,приведенной на рис.5.4: каждому рестрикционному фрагменту соответствует вершина, а каждой паре перекрывающихся фрагментов - ребро графа G(H,B). Цифры возле ребер, соединяющих вершину i в верхней доле и вершину j в нижней доли,соответствуют номерам фрагментов совместной рестрикции, образующихся при перекрывании фрагментов i и j
пары строить матрицы Ikl(A,A+B) и Ikl(B,A+B). Ватерман и Григе (Waterman,Griggs, 1986) показали, что матрица НА,В) может быть получена как произведение булевых матриц 1(А,А+В) и 1Т(В,А+В) (здесь Г(В,А+В) - транспонированная матрица для 1(В,А+В) ). По матрице К А,В) можно построить двудольный граф G с долями А и В (рис.5.9).
