Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
шах | p(w)-p(v)-l(v,w)j (v,w)eE
и задача уточнения физической карты состоит в поиске неотрицательной функции р на V, на которой достигается минимум
min max | p(w)-p(v)-l(v,w)!.
p (v,w)eE
Эту задачу можно сформулировать, как задачу линейного программирования. Если добавить в граф G |Е| новых дуг, вводя для каждой дуги (v,w) веса l(v,w) антипараллельную дугу (w,v) веса -i(v,w), то задачу (5.3) можно преобразовать к виду :
min max ( p(w)-p(v)-l(v,w))
р (v.w)eE'
(через Е' обозначено новое множество дуг мощности 2|Е|). Эта задача эквивалентна следующей задаче линейного программирования:
t>0,
VveV: p(v)>0,
V(v,w)eE': p(v)-p(w)-t <i(v,w),
t —> min.
Вводя двойственные переменные g(v,w) и переходя к двойственной задаче, получим
V(v,w)eE': g(v,w)>0 ,
VveV: S g(v,w) - 2 g(w,v)-0 ,
(v.w)eE' (w.v)eE'
S g(v,w) = -l ,
(v,w)eE'
S g(v,w)'l(v,w) --> max .
(v,w)eE'
Последняя задача: постановка задачи об оптимальном контуре(или о минимальном в среднем цикле в графе) в форме задачи линейного программировать Романовский, 1977)
V(v,w)eE': g(v,w)>0 ,
VveV: Е g(v,w) - S g(w,v)=0 ,
(v.w)eE' (w,v)eE'
S g(v,w)=l ,
(v,w)eE'
E g(v,i)'l(v,w) --> min .
(v,w)eE'
Использование алгоритма Карзанова(Карзанов,1985) для минимизации этого функционала дает возможность одновременно с построением опти-
мального контура получить также решение задачи об уточнении физической карты.
5.6.ДОПОЛНИТЕЛЬНЫЕ БИОХИМИЧЕСКИЕ МЕТОДЫ И СТРАТЕГИЯ КАРТИРОВАНИЯ
При картировании больших геномов и построении подробных физических карт необходимо привлекать дополнительные методы. Мы рассмотрели методы физического картирования, основанные на анализе результатов одиночных и совместных рестрикций. При этом подходе экспериментальная работа сводится к минимуму, однако построение карты по такой косвенной информации вызывает большие математические трудности, которые не всегда удается преодолеть (при значительном числе сайтов рестрикции и ошибках в определении размеров фрагментов). Дополнительные биохимические эксперименты по картированию позволяют за счет дополнительной экспериментальной работы снять некоторые математические проблемы. Даже в тех случаях, когда математические проблемы удается преодолеть, при картировании больших геномов, как правило, возникает несколько физических карт, согласующихся с экспериментальной информацией - снять эту неоднозначность удается только при использовании дополнительных биохимических экспериментов.
В предыдущих разделах уже затрагивался вопрос об оптимальном планировании экспериментов по картированию при минимизации числа элект-рофорезов, необходимых для однозначной идентификации физической карты. Однако при картировании больших геномов вычислительные трудности столь велики, что даже анализ данных о многих рестрикциях не дает возможности построить физическую карту. В этих случаях необходимс выбрать стратегию картирования: набор и последовательность дополнительных биохимических методов, приводящих к построению физической карты при минимальной экспериментальной работе.
Возможности дополнительных биохимических методов картирования. В этом разделе кратко описаны некоторые дополнительные методы, использующиеся при картировании.
1. Разрезание отдельных фрагментов рестрикции А рестриктазой В. Обычно при этом используется двумерный гель-электрофорез: SD- фрагменты рестрикции А сначала разделяются в первом направлении , затем разрезаются рестриктазой В и получившиеся DD-фрагменть; разделяются во втором направлении. Этот метод позволяет резко сократить вычислительные сложности при поиске вилок и вложений - лимитирующих этапах при построении парных карт.
2. Гибридизация по Саузерну. Гибридизация по Саузерну позволяет получить информацию о перекрывании фрагментов различных рестрикций и "обойти" этапы поиска вилок и вложений, перейдя сразу к построению рестрикционной карты по интервальному графу (разд. 5.3). Помимо это-
го для получения информации о перекрывании фрагментов могут быть использованы помеченные пробы (например, высокоповторяющиеся рассеянные последовательности ДНК при физическом картировании эукариот).
3. Линеаризация кольцевых ДНК. Для линеаризации кольцевой ДНК нужно найти рестриктазу с уникальным сайтом. В случае больших кольцевых ДНК (например, космид) поиск такой рестриктазы представляет проблему, однако ее можно пытаться решить с помощью специфического разрезания по соэ-последовательности (Rackwitz et al.,1985).
