Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
АВ
в
А
АВ
в
& г<д ?4 г---1*
1 а 1Ь Тз 1 i 8 1 ь ; ь 1
? 4 1 19 1 2
[}
9) Ь Я'4 \аЧ 4 4 I 50
1 * ? i t I !
i
м
а 19 ; гз г-. .liu
1 н 1 16 jaj, 17 6 is. i
;-4 ' гв 11
• >
20 ?4
Р и с.5.14.Диаграммы и физические карты
D - диаграмма(цифры показывают размеры фрагментов); М - физическая карта ( цифры показывают расстояния от сайтов рестрикции до начала молекулы ДНК; DM - диаграмма, построенная по физической карте М; G - граф для задачи о минимальном в среднем цикле, построенный по диаграмме D
Р и с.5.15.Построение рестрикционного графа по диаграмме
Рестрикционные графы. Всякой диаграмме можно поставить в соответствие рестрикционный граф G с пропускными способностями дуг (не путать с ранее вводившимися интервальными графами) . Построение графа G проведем в три этапа (на рис.5.15 показан процесс построения рестрикционного графа, соответствующего диаграмме на рис.5.14).
1. Построим трехдольный ориентированный граф G' (рис.5.15) с долями:
А - множество SD-фрагментов рестрикции А;
В - множество SD-фрагментов рестрикции В;
АВ - множество DD-фрагментов.
Из вершины v верхней доли А проведем дугу (v,w) в вершину w средней доли АВ, если SD-фрагмент v содержит DD-фрагмент w. Аналогично в вершину v нижней доли В проведем дугу (w,v) из вершины w средней доли АВ, если SD-фрагмент v содержит DD-фрагмент w.
2. Граф G' преобразуем в граф G" (рис.5.15), заменив каждую вершину дугой, пропускная способность которой равна длине соответствующего фрагмента.
3. Для завершения формирования рестрикционного графа G добавим к графу G" (рис.5.15) две вершины - источник s и сток t - и соединим источник s с началами всех дуг, соответствующих SD-фрагментам А, а все концы дуг, соответствующих SD-фрагментам В, соединим со стоком t. После этого добавим в граф последнюю дугу (t,s)(9TH преобразования делаются для сведения задачи уточнения физических карт к классической задаче о циркуляции).
Описанный процесс позволяет строить рестрикционные графы по диаграммам как линейных, так и кольцевых молекул и обобщить понятие рестрикционного графа для случая трех рестриктаз, учета информации о недорестрикциях и т.д. (на рис.5.16 приведен пример построения рестрикционного графа кольцевой молекулы для трех рестриктаз).
Циркуляции в рестрикционных графах(,). Каждому DD-фрагменту физической карты, согласующейся с нашей гипотезой о порядке следования сайтов рестрикции, соответствует некоторая дуга в графе G. Можно показать, что через эту дугу в графе G проходит ровно один ориентированный цикл. Взвешенная сумма таких циклов (в качестве веса цикла используется длина соответствующего фрагмента) дает циркуляцию в G. Таким образом, каждой физической карте, согласующейся с принятой гипотезой о порядке следования сайтов, можно поставить в соответствие циркуляцию в G. Обратно, если дана циркуляция в G, то она однозначно определяется значениями на дугах, соответствующих DD-фрагментам (это следует из того, что всякий ориентированный цикл в G проходит через
Р и с.5.16. Построение рестрикционного графа по диаграмме кольцевой молекулы для трех рестриктаз
некоторую DD-дугу и через каждую такую DD-дугу проходит ровно один цикл). По значениям на DD-дугах, в свою очередь, однозначно строится соответствующая физическая карта (координата i-ro сайта рестрикции
на ней равна 2 f , где f - поток по j-й DD-дуге графа G). j=l.i
Таким образом, установлено взаимооднозначное соответствие между физическими картами и циркуляциями в G (заметьте, что при таком подходе поток по дуге (t,s) определяет общую длину молекулы ДНК). Так как физическим картам соответствуют циркуляции, для отыскания оптимального представления диаграммы физической картой необходимо найти циркуляцию в сети G (графы с пропускными способностями дуг в дискретной оптимизации принято называть сетями), наилучшим образом приближающую пропускные способности дуг,т.е. циркуляцию, минимизирующуг
max |d(v,w)-f(v,w) |,
(v,w)
где d(v,w) - пропускная способность дуги (v,w), a f(v,w) - поток по дуге (v,w) (максимум в формуле берется по дугам, на которых определена пропускная способность).
Для решения этой задачи введем нижние и верхние пропускные способности на дугах по правилу
d'( v,w)=d(v,w)-t ; d+(v,w)=d(v,w)+t
(для дуг (v,w), на которых ранее пропускная способность не определялась, положим d‘(v,w)=0, dt(v,w)=~ )).
В этом случае существование физической карты, отклонение которой от диаграммы не превышает t , эквивалентно существованию циркуляции в сети с нижними и верхними пропускными способностями d‘ и d*.
Уточнение физических карт и теорема Гофмана(,). Для циркуляций в сети с двухсторонними ограничениями пропускной способности верна следующая
Теорема Гофмана(Форд,Фалкерсон, 1966): циркуляция в графе G с
