Biopolym. Cell. 1988; 4(5):233-238.
http://dx.doi.org/10.7124/bc.000230
Структура та функції біополімерів
Рестрикційні графи і фізичне картування молекул ДНК
1Певзнер П. А.
  1. ВНДІ генетики та селекції промислових мікроорганізмів Главмікробіопрома при РМ СРСР
    Москва, СРСР

Abstract

Побудова фізичних карт ДНК за даними одиночних і спільних рестрикцій призводить до аналізу величезного числа гіпотез про взаємне розташування сайтів рестрикції. При перевірці та відбракуванні подібних гіпотез виникає завдання уточнення фізичних карт, для вирішення якого вводиться поняття рестрикційного графа. Це дозволяє застосувати для фізичного картування методи дискретної оптимізації та перенести основні проблеми в область побудови потокових алгоритмів. Запропонований підхід відбраковує карти зі значними відхиленнями від експериментальних даних (такі відхилення на окремих фрагментах можливі при вирішенні задачі методом Шредера-Блаттнера).
Повний текст: (PDF, російською)

References

[1] Stefic M. Inferring DNA structure from segmentation data. Artif. Intel. 1978; 11(1-2):85-114.
[2] Stefik M., Eikins Ya, Balzer R. et al. M. Organization of expert systems. Kiberneticheskiy sbornik. Moscow, Mir, 1985; Is. 22: 170-220.
[3] Pearson WR. Automatic construction of restriction site maps. Nucleic Acids Res. 1982;10(1):217-27.
[4] Polner G, Dorgai L, Orosz L. PMAP, PMAPS: DNA physical map constructing programs. Nucleic Acids Res. 1984;12(1 Pt 1):227-36.
[5] Durand R, Bregegere F. An efficient program to construct restriction maps from experimental data with realistic error levels. Nucleic Acids Res. 1984;12(1 Pt 2):703-16.
[6] Nolan GP, Maina CV, Szalay AA. Plasmid mapping computer program. Nucleic Acids Res. 1984;12(1 Pt 2):717-29.
[7] Fitch WM, Smith TF, Ralph WW. Mapping the order of DNA restriction fragments. Gene. 1983;22(1):19-29.
[8] Pevzner PA, Mironov AA. Application of branch and bound method for solving problems of physical (restriction) mapping. Genetics and biochemistry of microorganisms - biotechnologies: Proc. posts. conf. Moscow, 1986. 80.
[9] Pevzner PA, Mironov AA. Effective method for physical mapping the DNA molecule. Mol Biol (Mosk). 1987;21(3):788-96.
[10] Schroeder JL, Blattner FR. Least-squares method for restriction mapping. Gene. 1978;4(2):167-74.
[11] Ford L, Fulkerson D. Flows in Networks. Moscow, Mir, 1966; 266 p.
[12] Pevzner PA. Efficient compression algorithm branching in a weighted graph. Combinatorial methods in streaming tasks. Moscow, 1979; 91-104.
[13] Adel'son-Vel'skiy GM, Dinits EA, Karzanov AV. Flow algorithms. Moscow, Nauka, 1975; 119 p.