Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
двусторонними ограничениями пропускной способности существует тогда и только тогда, когда для любого подмножества X вершин графа выполняется
dt(X,X') > d-(X,X)
(здесь d*(X,X') - суммарная верхняя пропускная способность прямых дуг разреза (Х,Х), a d‘(I,X) - суммарная нижняя пропускная способность обратных дуг разреза (X,X) ).
Определим дефицит сети как DF= max (d_(X',X)-d*(X,X)). Если в
X
сети с двухсторонними ограничениями пропускной способности не
существует циркуляции, то по теореме Гофмана DF>0. Как уже отмечалось, в реальной ситуации, как правило, не существует физической карты, в точности соответствующей диаграмме, поэтому при t=0 (в этом случае функции d' и d+ совпадают и равны d) найдется множество X, такое, что
d(X,X) > d(X,X)
и дефицит сети DF>0. Значение DF может быть определено с помощью алгоритма вычисления максимального потока в некоторой сети специального вида (Форд, Фалкерсон,1966). Множество X, на котором достигается дефицит сети, позволяет локализовать фрагменты, на которых принятая гипотеза дает "максимальные" противоречия (на рис.5.15 для графа G выделено множество X из 6 вершин, дающее максимальный дефицит: сумма пропускных способностей по его обратным дугам равна 20+18, а по прямым - 15+19. Следовательно, DF=38-34=4). При возрастании t d"(X',X) уменьшается , a d*(X',X) увеличивается для любого множества X. Таким образом, дефицит сети DF(t) - убывающая функция. Можно показать, кроме того, что DF(t) - кусочно-линейная выпуклая вверх функция, число звеньев которой оценивается как 0(г), где г - число сайтов рестрикции. Как уже отмечалось, DF(0)>0 для реальных диаграмм. Обозначим через t0 точку, в которой DF(t) обращается в 0, при таком t0, по теореме Гофмана, впервые появляется возможность построить циркуляцию в сети с двухсторонними ограничениями, и, следовательно, t0 дает минимальное отклонение исходной диаграммы от физической карты, а соответствующая циркуляция порождает физическую карту, являющуюся оптимальным представлением диаграммы.
В результате задача уточнения физической карты свелась к нахождению и построению циркуляции в соответствующей сети. Заметим, что функция DF(t), вообще говоря, неизвестна, однако ее значение в любой точке можно вычислить путем решения задачи о максимальном потоке в сети. Задача нахождения точки пересечения таких функций с прямой (нас интересует пересечение графика функции DF(t) с прямой DF=0) рассматривалась в работе Певзнера(1979), и для ее решения был предложен алгоритм, число этапов которого не превышает числа звеньев кусочно-линейной функции.
Таким образом, решение задачи уточнения физических карт свелось к серии итераций, на каждой из которых находится максимальный поток в сети. Так как для решения последней задачи известны эффективные полиномиальные алгоритмы (Адельсон-Вельский и др.,1975), предложенный метод позволяет решать задачу уточнения физических карт практически при любом числе фрагментов.
Уточнение физических карт и задача об оптимальном контуре в гра-фе(,). Рассмотренный подход устанавливает связь между потоковыми алгоритмами и физическими картами при числе рестриктаз к<3, но уже при к=4 не удается построить потоковую сеть, сводящую задачу уточнения физических карт к построению циркуляций. В этом случае предлагается более универсальный подход: сведение задачи построения физичес ких карт к задаче об оптимальном контуре в графе(Романовский,1977). Для ориентированного графа G(V,Е) с весами на дугах 1(e) будем обозначать через 1(C) длину цикла С с учетом ориентаций дуг,а через d(С)
- число дуг в С . Например, для цикла, составленного из жирных дуг’ на рис.5.14: 1 (0=20+18-19-15=4,d(C)=4. Обозначим
lmjn=min 1(C),
lmld=min l(C)/d(C)
(минимум берется по множеству всех простых циклов графа).
Задача определения lmln известна как задача поиска минимального цикла в графе, она относится к классу NP. Задача определения lmid известна как задача определения оптимального контура в графе, и для нее в отличие от задачи о поиске минимального цикла известны эффективные алгоритмы (Karp,1978; Карзанов,1985).
Оказывается, что задача уточнения физической карты (при произвольном числе рестриктаз) сводится к поиску оптимального контура в графе специального вида. На рис. 5.14 приведен взвешенный ориентированный граф, построенный по диаграмме - каждому сайту рестрикции на диаграмме (а также началу и концу линейной молекулы) соотвествует вершина в G, две вершины соединяются дугой веса 1, если расстояние между соответствующими сайтами на диаграмме известно и равно 1.
Всякая физическая карта М, построенная по диаграмме D , описывается функцией р на множестве вершин графа G ( p(v) - расстояние от сайта, соответствующего вершине v, до начальной точки). Физическая карта М порождает диаграмму DM, которой соответствует граф G(V,E) с весами дуг l*(v,w)=p(w)-p(v).
Таким образом, отклонение физической карты М от диаграммы D дается формулой:
