Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
Таблица 5.2 Размеры фрагментов SD- и DD-расщеплений.
Общая длина молекулы - 104(в условных единицах).
Информация о рестриктазе С используется в разделе 5.4 при построении множественных карт
Тип обработки Номера фрагментов |
1 2 1 з 4 5 I 6 7 1
А 44 42 18
В 42 38 16 8
С 58 46
АВ 36 30 12 8 8 6 4
ВС 40 38 8 8 8 2
СА 42 34 14 10 4
Следуя работе Нолана и др.(Nolan et al.,1984), будем называть группу DD-фрагментов расщепления рестриктазами AB i-вилкой расщепления А, если сумма длин этих фрагментов равна длине i-го SD- фрагмента расщепления А (с учетом ошибок измерения). Например, S=(36+8) и S=(30+8+6) - 1-вилки расщепления A, S=(30+12) и S=(30+8+4) - 2-вилки расщепления A, S=(8+8) - 3-вилка расщепления В (рис.5.6). i-вилку расщепления А можно интерпретировать как набор фрагментов, на которые может разбиться i-й фрагмент А при действии рестриктазы В.
Назовем вложением набора фрагментов АВ в набор А такое разбиение п
множества фрагментов AB=_U St на подмножества S;, что каждое S.
является i-вилкой расщепления А (вложения можно рассматривать как предварительные заготовки для построения физической карты). Например, разбиения
б * Заказ № «27
165
36+8 ЗО+в+6 36+6 30+8+4 30+12 12+4 8+8
P и c.5.6. Примеры вилок
(36+8), (30+8+4), (12+6);
(36+8), (30+12), (8+6+4)
являются вложениями АВ в А. Очевидно, что каждая физическая карта порождает вложения АВ в А и в В(рис.5.7). Обратное, вообще говоря, неверно. Например, вложениям
(36+8), (30+8+4), (12+6) АВ в А;
(36+8), (30+6), (12+4),(8) АВ в В
не отвечает ни одна физическая карта, в этом случае мы будем говорить, что вложения АВ в А и АВ в В несовместимы.
Решение задачи о построении парной физической карты разобьем на три этапа: 1) поиск вилок расщеплений А и В; 2) поиск вложений АВ в А и в В; 3) удаление несовместимых пар вложений и восстановление парных физических карт по совместимым парам вложений.
А
Р и с.5.7. Соответствие между физическими картами и вложениями. Карта на рисунке по-ождает вложения:
36+8),(30+8+4W12+6) АВ в А; 36+6), (30+8), (12+4), (8) АВ в В
Поиск вилок. Задача поиска вилок сводится к классической задаче
о сумме размеров (Гэри,Джонсон,1982) : в множестве чисел {а} найти все подмножества X, для которых
А-6 < Е а < А+б, аеХ
где А и б - фиксированные числа. Эта задача может быть решена с использованием метода динамического программирования - таким образом,
поиск вилок не является проблемой (для задач физического картирования реальной размерности). Однако при высоком уровне погрешностей в определении размеров фрагментов возможна ситуация, когда число вилок оказывается очень большим, что затрудняет этап поиска вложений АВ в А и в В. Для уменьшения трудоемкости этого этапа Нолан и др. (Nolan et al.,1984) предложили методы, позволяющие резко сократить множество вилок, использующихся при поиске вложений.
Поиск вложений(,). Поиск вложений - самый трудный этап при построении парных карт. Удобно сформулировать эту задачу на языке теории графов как задачу поиска "представительных" наборов вилок (т.е. наборов, в которые входят все DD-фрагменты).
Для поиска вложений АВ в А строится гиперграф Н на множестве вершин АВ U А (определения, относящиеся к теории графов, см. Зыков, 1987). Каждой i-вилке S рестрикции А, состоящей из 1 DD- фрагментов, соответствует ребро S U {i} в гиперграфе Н, состоящее из 1+1 вершины. Задача поиска вложений эквивалентна задаче нахождения точного покрытия гиперграфа Н ребрами(Гэри,Джонсон,1982). Отсутствие эффективных алгоритмов для решения этой задачи заставляет применять переборные методы дискретной оптимизации, например метод ветвей и границ (Fitch et al., 1983; Певзнер,Миронов,1987а). Следует отметить, что многие эвристические правила отбора вилок, введенные Ноланом и др.(Nolan et al.,1984), вытекают из процедур поиска точного покрытия гиперграфа ребрами.
Описание метода ветвей и границ (Романовский,1977) применительно к конкретной задаче предполагает описание стратегии ветвления и процедуры отсечения. Например, в работе Певзнера и Миронова(1987а) для организации перебора строится дихотомичное дерево ветвления Т (рис.5.8). Корневой вершине дерева Т отвечает разбиение АВ. На каждой итерации вершина дерева Т порождает две новые вершины; одна из них отвечает варианту, в котором подмножества (элементы разбиения) объединяются, другая - варианту, в котором объединение запрещено. Размножение вершин дерева Т продолжается до тех пор, пока число групп в разбиении вершины не станет равным п - числу фрагментов SD-расщепления. Теперь задача поиска вложений сведена к задаче поиска висячих вершин дерева Т, соответствующих вложениям. Для определения процедуры отсечения определим на вершинах х дерева Т функцию оценки вариантов f(х):
