Рестрикционные графы и физическое картирование молекул ДНК

Построение физических карт ДНК по данным одиночных и совместных рестрикций приводит к анализу огромного числа гипотез о взаимном расположении сайтов рестрикции. При проверке и отбраковке таких гипотез возникает задача уточнения физических карт, для решения которой вводится понятие рестрикционного гр...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	1988
Автор:	Певзнер, П.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут молекулярної біології і генетики НАН України 1988
Назва видання:	Биополимеры и клетка
Теми:	Структура и функции биополимеров
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/154046
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Рестрикционные графы и физическое картирование молекул ДНК / П.А. Певзнер // Биополимеры и клетка. — 1988. — Т. 4, № 5. — С. 233-238. — Бібліогр.: 13 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-154046
record_format	dspace
spelling	irk-123456789-1540462019-06-16T01:27:21Z Рестрикционные графы и физическое картирование молекул ДНК Певзнер, П.А. Структура и функции биополимеров Построение физических карт ДНК по данным одиночных и совместных рестрикций приводит к анализу огромного числа гипотез о взаимном расположении сайтов рестрикции. При проверке и отбраковке таких гипотез возникает задача уточнения физических карт, для решения которой вводится понятие рестрикционного графа. Это позволяет применить для физического картирования методы дискретной оптимизации и перенести основные проблемы в область построения потоковых алгоритмов. Предложенный подход отбраковывает карты со значительными отклонениями от экспериментальных данных (такие отклонения на отдельных фрагментах возможны при решении задачи методом Шредера—Блаттнера). Побудова фізичних карт ДНК за даними одиночних і спільних рестрикцій призводить до аналізу величезного числа гіпотез про взаємне розташування сайтів рестрикції. При перевірці та відбракуванні подібних гіпотез виникає завдання уточнення фізичних карт, для вирішення якого вводиться поняття рестрикційного графа. Це дозволяє застосувати для фізичного картування методи дискретної оптимізації та перенести основні проблеми в область побудови потокових алгоритмів. Запропонований підхід відбраковує карти зі значними відхиленнями від експериментальних даних (такі відхилення на окремих фрагментах можливі при вирішенні задачі методом Шредера-Блаттнера). DNA physical mapping concluded from the single and double restrictions analysis leads to a great variety of hypotheses about order of the sites. The concept of graph of restrictions was introduced for examination and selection of such hypotheses. It allows applying methods of discrete optimization for physical mapping and solving the major problems by maximal flow-minimum cut algorithms. This approach throws away maps with significant deviations from experimental data (such deviations on individual fragments are allowed in the Schroeder-Blattner method). 1988 Article Рестрикционные графы и физическое картирование молекул ДНК / П.А. Певзнер // Биополимеры и клетка. — 1988. — Т. 4, № 5. — С. 233-238. — Бібліогр.: 13 назв. — рос. 0233-7657 DOI: http://dx.doi.org/10.7124/bc.000230 http://dspace.nbuv.gov.ua/handle/123456789/154046 577.323:519.852 ru Биополимеры и клетка Інститут молекулярної біології і генетики НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Структура и функции биополимеров Структура и функции биополимеров
spellingShingle	Структура и функции биополимеров Структура и функции биополимеров Певзнер, П.А. Рестрикционные графы и физическое картирование молекул ДНК Биополимеры и клетка
description	Построение физических карт ДНК по данным одиночных и совместных рестрикций приводит к анализу огромного числа гипотез о взаимном расположении сайтов рестрикции. При проверке и отбраковке таких гипотез возникает задача уточнения физических карт, для решения которой вводится понятие рестрикционного графа. Это позволяет применить для физического картирования методы дискретной оптимизации и перенести основные проблемы в область построения потоковых алгоритмов. Предложенный подход отбраковывает карты со значительными отклонениями от экспериментальных данных (такие отклонения на отдельных фрагментах возможны при решении задачи методом Шредера—Блаттнера).
format	Article
author	Певзнер, П.А.
author_facet	Певзнер, П.А.
author_sort	Певзнер, П.А.
title	Рестрикционные графы и физическое картирование молекул ДНК
title_short	Рестрикционные графы и физическое картирование молекул ДНК
title_full	Рестрикционные графы и физическое картирование молекул ДНК
title_fullStr	Рестрикционные графы и физическое картирование молекул ДНК
title_full_unstemmed	Рестрикционные графы и физическое картирование молекул ДНК
title_sort	рестрикционные графы и физическое картирование молекул днк
publisher	Інститут молекулярної біології і генетики НАН України
publishDate	1988
topic_facet	Структура и функции биополимеров
url	http://dspace.nbuv.gov.ua/handle/123456789/154046
citation_txt	Рестрикционные графы и физическое картирование молекул ДНК / П.А. Певзнер // Биополимеры и клетка. — 1988. — Т. 4, № 5. — С. 233-238. — Бібліогр.: 13 назв. — рос.
series	Биополимеры и клетка
work_keys_str_mv	AT pevznerpa restrikcionnyegrafyifizičeskoekartirovaniemolekuldnk
first_indexed	2025-07-14T05:32:42Z
last_indexed	2025-07-14T05:32:42Z
_version_	1837599208113176576
fulltext	УДК 577.323:519.852 РЕСТРИКЦИОННЫЕ ГРАФЫ И ФИЗИЧЕСКОЕ КАРТИРОВАНИЕ МОЛЕКУЛ ДНК * П. А. Певзнер Введение. Физическое картирование — один из самых распространен- ных методов анализа Д Н К , применяющийся при клонировании, опре- делении первичной последовательности Д Н К , выявлении эволюцион- ной близости геномов, определении специфичности рестриктаз и т. п. Математические аспекты задачи физического картирования интенсивно изучаются с середины 70-х годов [1, 2]. В последнее время появились методы и программы для ЭВМ [3—7], позволяющие проводить карти- рование при числе сайтов порядка 10 (по каждой рестриктазе) , однако задачи построения более подробных физических карт и оптимального планирования биохимических экспериментов при картировании еще ждут своего решения. Большинство алгоритмов физического картирования основано на последовательном выдвижении, анализе и отбраковке гипотез о том или ином расположении сайтов рестрикции. В связи с огромным чис- лом взаимного расположения сайтов (и, как следствие, необходимостью проверки большого числа гипотез) при реализации таких алгоритмов возникают значительные трудности, и на первый план выдвигаются следующие задачи: 1) оптимальная организация перебора гипотез о взаимном расположении сайтов; 2) эффективная проверка и отбраков- ка гипотез о взаимном расположении сайтов. Первая задача для слу- чая парной физической карты уже перешла в разряд классических, и для ее решения предложен целый ряд алгоритмов, в частности метод ветвей и границ [8]. Значительно более сложной становится первая задача при построении множественных физических карт (этот случай гораздо чаще встречается на практике); для ее решения предложен метод потенциалов [9]. В настоящей работе исследуется вторая задача [10]; другое ее название — уточнение физических карт, так как проверка гипотез сво- дится, как правило, к уточнению положения сайтов рестрикции относи- тельно некоторой точки на карте — начала отсчета. Д л я ее решения вводится понятие рестрикционпого графа и строится взаимно-однознач- ное соответствие между физическими картами, удовлетворяющими при- нятой гипотезе о взаимном расположении сайтов, и циркуляциями в рестрикционном графе (в работе используется терминология, принятая в теории графов, определения даны в [11]). В результате удается свести задачу уточнения физической карты к задаче поиска циркуляции в сети с двухсторонними ограничениями. Это позволяет перенести основные проблемы в область построения потоковых алгоритмов и, используя результаты теории графов, получить как исчерпывающее теоретическое (теорема Гофмана) , так и алгоритмическое (алгоритм построения максимального потока в сети) решение проблемы уточне- ния физических карт. П о с т а н о в к а з а д а ч и . Исходной информацией для построе- ния физических карт служили данные электрофореграмм о длине фраг- ментов одиночных и совместных рестрикций (в соответствии с общепри- нятой терминологией фрагменты одиночных рестрикций называются SD-фрагментами, а совместных — DD-фрагмеитами). В дальнейшем мы считаем, что зафиксирована гипотеза о порядке расположения сайтов рестрикций и следовании фрагментов па молекуле Д Н К . Каждой такой гипотезе соответствует диаграмма D (схема 1), на которой указаны порядок следования сайтов и соответствующие длины SD- и DD-фраг- ментов. Физическая карта Μ (схема 1) дает информацию о порядке * П р е д с т а в л е н а членом редколлегии М. Д . Франк-Каменецким. 233 БИОПОЛИМЕРЫ И КЛЕТКА.— 1988.— Т. 4, № 5 234 Б И О П О Л И М Е Р Ы И КЛЕТКА,— 1988.—Т. 4, № 5 следования сайтов и расстоянии каждого сайта от начальной точки. Всякая физическая карта Μ порождает некоторую диаграмму DM, в качестве длины фрагментов на этой диаграмме используются рас- стояния между соответствующими сайтами. Однако обратное утвержде- ние неверно: не по всякой диаграмме можно построить физическую карту (например, по диаграмме D нельзя построить физической карты, так как уже для первых двух фрагментов рестрикции В: 8 + 1 5 ^ = 2 4 ) . Поэтому возникает необходимость ь построении карты, наилучшим обра- зом приближающей диаграмму,— это и есть задача уточнения физи- ческих карт. В качестве меры расхождения между диаграммой и физической картой рассматривается равномерная норма, т. е. если длины фрагмен- тов диаграммы представлены вектором D= (du ... , dt), а длины фраг- ментов физической карты — вектором М= (ть ... , tnt), το под отклоне- нием физической карты Μ от диаграммы D понимается (в векторах D и Μ представлены в некотором порядке длины фрагмен- тов SD- и DD-рестрикций). Таким образом, задача уточнения физиче- ской карты состоит в отыскании по диаграмме D физической карты Af, дающей решение следующей минимальной задачи: Физическая карта М называется оптимальным представлением диаг- раммы D (можно показать, что на схеме 1 карта Μ — оптимальное представление диаграммы D). Нам представляется, что выбор равномерной нормы в большей сте- пени соответствует реальной задаче картирования, чем, скажем, выбор евклидовой нормы /2: Дело в том, что незначительные отклонения от данных электрофоре- грамм вполне допустимы (они постоянно встречаются при картирова- нии), а вот значительные отклонения хотя бы па одном фрагменте недопустимы и должны приводить к отбраковке гипотезы о порядке расположения сайтов. Ρ е с τ ρ и к ц и о н π ы е г р а ф ы . Всякой диаграмме можно поста- вить в соответствие рестрикционный граф с пропускными способностями дуг (сеть). Построение графа проводили в три этапа (на схеме 2 по- казан процесс построения рестрикционпого графа, соответствующего диаграмме па схеме 1). - 1. Строили трехдольный ориентированный граф G' (схема 2) с до- лями: А — множество SD-фрагментов рестрикции А; В — множество SD-фрагментов рестрикции В\ А В — множество DD-фрагментов. Из вер шины ν верхней доли А проводили дугу (v, w) в вершину w средней доли АВ, если SD-фрагмент υ содержит DD-фрагмент w. Аналогично, в вершину ν нижней доли В проводили дугу (wt ν) из вершины W средней доли АВ, если SD-фрагмент υ содержит DD-фрагмент w. 2. Граф G' преобразовывали в граф G" (схема 2), заменив каж- дую вершину дугой, пропускная способность которой равна длине соот- ветствующего фрагмента. 3. Д л я завершения формирования рестрикционного графа G до- бавляли к графу G" (схема 2) две вершины — источник 5 и сток t — и соединяли источник 5 с началами всех дуг, соответствующих SD-фраг- ментам Л, а все концы дуг, соответствующих SD-фрагмеитам В, соеди- няли со стоком t. После этого добавляли в граф последнюю дугу (/, s). Описанный процесс позволяет строить рестрикционные графы по диа- граммам как линейных, так и кольцевых молекул; исходя из него, можно обобщить понятие рестрикционного графа для случая трех рест- риктаз, учета информации о недорестрикциях и т. д. (на схеме 3 приве- ден пример построения рестрикционного графа кольцевой молекулы для трех рестриктаз) . 235 Б И О П О Л И М Е Р Ы И КЛЕТКА.— 1988.— Т. 4, № 5 Ф и з и ч е с к и е к а р т ы и ц и р к у л я ц и я в р е с т р и к - ц и о н н ы х г р а ф а х . К а ж д о м у DD-фрагменту физической карты, со- гласующейся с нашей гипотезой о порядке следования сайтов рестрик- ции, соответствует некоторая дуга в графе G. Можно показать, что через эту дугу в графе G проходит ровно один ориентированный цикл. Взвешенная сумма таких циклов (в качестве веса цикла используется длина соответствующего фрагмента) дает циркуляцию в G. Таким об- разом, каждой физической карте, согласующейся с принятой гипотезой о порядке следования сайтов, можно поставить в соответствие циркуля- цию в G. Наоборот, если дана циркуляция в G, то она однозначно определяется значениями на дугах, соответствующих DD-фрагмептам (это следует из того, что всякий ориентированный цикл в G проходит через некоторую DD-дугу и через к а ж д у ю такую DD-дугу проходит ровно один цикл) . По значениям на DD-дугах, в свою очередь, одно- значно строится соответствующая физическая карта (координата і-го і сайта рестрикции на ней равна V / / , где fj—поток по /-й DD-дуге гра- / = ι фа G). Таким образом, установлено взаимно-однозначное соответствие между физическими картами и циркуляциями в G (заметьте, что при таком подходе поток по дуге (t, s) определяет общую длину молекулы Д Н К ) . Так как физическим картам соответствуют циркуляции, для отыскания оптимального представления диаграммы физической картой необходимо найти циркуляцию в графе G, наилучшим образом прибли- ж а ю щ у ю пропускные способности дуг, т. е. циркуляцию, минимизи- рующую 236 Б И О П О Л И М Е Р Ы И КЛЕТКА.— 1988.—Т. 4, № 5 где d(v, w) — п р о п у с к н а я способность дуги (v, w), a f(vf w) — п о т о к по дуге (и, w) (максимум в формуле берется по всем дугам, на кото- рых определена пропускная способность). Д л я решения этой задачи введем нижние и верхние пропускные способности на дугах по правилу (для дуг (ν, w) , на которых ранее пропускная способность не опреде- лялась , положим d~(v, w)= 0; d+(v, w)=oо). В этом случае суще- ствование физической карты, отклонение которой от диаграммы не пре- вышает ε, эквивалентно существованию циркуляции в сети с нижними и верхними пропускными способностями d~ и d+. Д л я циркуляций в сети с двухсторонними ограничениями пропуск- ной способности верна теорема Гофмана. Т е о р е м а Г о ф м а н а . Циркуляция в графе G с двухсторонними ограничениями пропускной способности существует тогда и только то- гда, когда для любого подмножества X вершин графа выполняется в сети с двухсторонними ограничениями пропускной способности не существует циркуляции, то по теореме Гофмана D F > 0 . К а к у ж е от- мечалось, в реальной ситуации, как правило, не существует физической карты, в точности соответствующей диаграмме, поэтому при ε = 0 (в этом случае функции d~ и d+ совпадают и равны d) найдется мно- жество X, такое что суммарная верхняя пропускная способность прямых ребер — суммарная нижняя пропускная способность Если (здесь с разреза обратных ребер разреза Определим дефицит сети, как и дефицит сети DF>0. Значение DF может быть определено с по- мощью алгоритма вычисления максимального потока в некоторой сети специального вида [11]. Множество Ху при котором достигается дефи- цит сети, позволяет локализовать фрагменты, на которых принятая гипотеза дает «максимальные» противоречия (на схеме 2 для графа G выделено множество X из шести вершин, дающее максимальный дефи- цит: сумма пропускных способностей по его обратным дугам равна 2 0 + 1 8 , а по п р я м ы м — 1 5 + 1 9 . Следовательно, DF=38—34 = 4) . При возрастании ε d~(X, X) уменьшается, a d+(Xf X) увеличивается для любого множества X. Таким образом, дефицит сети d~~(Xy X) —d+(X, Χ)—убывающая функция DF(e). Можно показать, кроме того, что DF(e)—кусочно-линейная выпуклая вверх функция, число звеньев которой оценивается как 0 ( г ) , где г — число сайтов рестрикции. К а к у ж е отмечалось, Z ) / 7 ( 0 ) > 0 для реальных диаграмм. Обозначим через εο точку, в которой DF(e) обращается в 0. При таком во, по теореме Гофмана, впервые появляется возможность построить циркуляцию в сети с двухсторонними ограничениями, и, следовательно, ε0 дает мини- мальное отклонение исходной диаграммы от физической карты, а соот- ветствующая циркуляция порождает физическую карту, являющуюся оптимальным представлением диаграммы. В результате з адача уточнения физической карты сводится к на- хождению во и построению циркуляции в соответствующей сети. Заме- тим, что функция DF(e) неизвестна, однако ее значение в любой точке можно вычислить решением задачи о максимальном потоке в сети. Проблема нахождения точки пересечения таких функций с прямой (нас интересует пересечение графика функции DF(E) С прямой DF = 0) рас- сматривалась в работе [12], и для ее решения был предложен алго- ритм, число этапов которого не превышает числа звеньев кусочно-линей- ной функции. Таким образом, решение задачи уточнения физических карт све- лось к серии итераций, па каждой из которых находится максималь- ный поток в сети. Так как для поиска максимального потока в сети известны эффективные полиномиальные алгоритмы [13], предложен- ный метод позволяет проводить уточнение физических карт практически при любом числе фрагментов. G R A P H S O F R E S T R I C T I O N S AND DNA P H Y S I C A L M A P P I N G P. A. Pevzner Research Ins t i tu te for Genetics and Breed ing of Commercia l Mic roorgan i sms , Moscow S u m m a r y DNA physical m a p p i n g concluded f rom the s ingle and double res t r ic t ions ana lys i s leads to a g rea t va r ie ty of hypotheses about order of the sites. The concept of g r aph of re- s t r ic t ions was introduced for examina t ion and selection of such hypotheses . It a l lows apply ing methods of discrete opt imizat ion for physical m a p p i n g and so lv ing the m a j o r problems by max imal f low-min imum cut a lgor i thms . This approach th rows a w a y m a p s with s ign i f ican t devia t ions f rom exper imenta l da ta (such devia t ions on individual f r a g - ments are al lowed in the Schroeder -Bla t tner me thod ) . 1. Stefic M. I n f e r r i ng DNA s t ruc tu re f rom segmen ta t i on da ta // Artif . Intel .— 1978.— 11, N 1 .—P. 85—115. 2. Экспертные с и с т е м ы / Μ. Стефик, Я. Эпкппс, Р. Балзер и д р . / / К и б е р н е т . сб.— Μ : Мир, 1985,—Вып. 22 ,—С. 170—220. 3. Pearson Ψ. Au tomat ic cons t ruc t ion of restr ict ion site m a p s / / Nucl. Acids Res — 1982,—10, N 1 .—P. 217—227. 4. Polner G., Dorgai L., Orosz L. P M A P , P M A P S : DNA physical m a p cons t ruc t ing pro- g r a m s / / I b i d . — 1 9 8 4 . — 1 2 , N 1 ,—P. 227—236. 5. Duranci R., Bregegere F. An eff icient p r o g r a m to cons t ruc t res t r ic t ions m a p s f rom exper imental da ta wi th real is t ic error l e v e l / / I b i d . — P. 703—716. Б И О П О Л И М Е Р Ы II КЛЕТКА.— 1988.—Τ. 4. Кг 5 3—8-411 237 6. Nolan G., Maina C., Szalay A. P l a s m i d m a p p i n g c o m p u t e r p r o g r a m / / Ib id .— P. 717—729. 7. Fitch WSmith Т., Ralph W. M a p p i n g the o rde r of D N A res t r i c t ion f r a g m e n t s / / G e - ne .—1983 .—22 , N 1 , — P . 19—29. 8. Певзнер Π. Α., Миронов А. А. Применение метода ветвей и границ д л я решения за - дач физического (рестрикционного) к а р т и р о в а н и я / / Генетика и биохимия микроор- ганизмов-биотехиологии: Тез. сообщ. конф.—М., 1986.— С. 80. 9 Певзнер П. Α., Миронов А. А. Э ф ф е к т и в н ы й ^ м е т о д физического к а р т и р о в а н и я мо- лекул Д Н К / / М о л е к у л я р . биология.— 1987.—21, № 3 . — С . 788—796. 10. Schroeder J. L., Blattner F. R. L e a s t - s q u a r e s m e t h o d for res t r i c t ion m a p p i n g / / G e - ne .—1978 .—4, N 2 . — P . 167—174. 11. Форд JI., Фалкерсон Д. Потоки в сетях .— М. : Мир, 1966.—266 с. 12. Певзнер П. А. Э ф ф е к т и в н ы й алгоритм упаковки ветвлений во взвешенном г р а ф е / / К о м б и н а т о р н ы е методы в потоковых з а д а ч а х . — М., 1979.— С. 91 —104. 13. Адельсон-Вельский Г. М., Диниц Ε. Α., Карзанов А. В. Потоковые алгоритмы.— М . : Н а у к а , 1975.—119 с. В Н И И генетики и селекции пром. микроорганизмов . Получено 04.02.87 Москва УДК 577.150.6 ВОЗМОЖНОЕ КОДИРОВАНИЕ ЖЕЛЕЗО-СЕРНЫХ БЕЛКОВ В МИТОХОНДРИАЛЬНОМ ГЕНОМЕ МЛЕКОПИТАЮЩИХ * Η. Н. Береговская, А. В. Савич Железо-серные белки ( Ж С Б ) , согласно существующей номенклатуре [1], подразделяются на простые и сложные. Среди сложных известны железо-серные флавопротеины, молибдено-флавопротеины и др. Прос- тые содержат только железо-серные функциональные группы; к ним относятся: рубредоксины, принадлежащие анаэробным и сульфатре- дуцирующим бактериям, у которых атом Fe координационно связан с четырьмя атомами S от цистеиновых остатков белка и не содержится свободных атомов серы; ферредоксины ( Ф Д К ) , содержащие железо- серные кластеры с одинаковым количеством атомов железа и свободной серы типа 2Fe-2S, 3Fe-3S, 4Fe-4S, в которых лигандами железа служат еще аминокислотные остатки белка — чаще всего цистеиновые; Ф Д К типа 8Fe-8S (кластеры 4 + 4 ) имеются у анаэробных и фотосинтези- рующих бактерий; типа 7Fe-7S ( 3 + 4 ) найдены у анаэробной азот- фиксирующей бактерии; 4Fe-4S—-у анаэробных, сульфатредуцирую- щих и фотосинтезирующих бактерий; 2Fe-2S — у бактерий и в хлоро- пластах растений и водорослей [2]. Высокопотенциальные Ж С Б типа 4Fe-4S найдены у фотосинтези- рующих пурпурных бактерий и в митохондриях высших живот- ных [3, 4]. Ж С Б (простые и сложные) являются обязательными и наиболее многочисленными компонентами систем электронного транс- порта. Они входят в комплексы НАДН-дегидрогеназы, сукцинатдегид- рогеназы, комплекс цитохромов Ъ — а также в цепь β-окисления ненасыщенных жирных кислот. Этим белкам приписывается непосред- ственное участие в сопряжении дыхания и фосфорилирования [3—5]. Д л я многих Ж С Б из бактерий и хлоропластов определена первич- ная структура, но ни одна из аминокислотных последовательностей митохондриальных Ж С Б неизвестна, что связано с трудностью их вы- деления. Нуклеотидная последовательность митохондриалыюго генома че- ловека расшифрована полностью [6]. В нем имеются участки, коди- рующие рибосомальные и транспортные Р Н К , а также информацион- * П р е д с т а в л е н а членом редколлегии В. И. И в а н о в ы м . 238 Б И О П О Л И М Е Р Ы И КЛЕТКА.— 1988.— Т. 4, № 5

Рестрикционные графы и физическое картирование молекул ДНК

Репозитарії

Схожі ресурси