Biopolym. Cell. 1988; 4(5):233-238.
http://dx.doi.org/10.7124/bc.000230
Structure and Function of Biopolymers
Graphs of restrictions and DNA physical mapping
1Pevzner P. A.
  1. All-Union Research Institute of Genetics and Breeding of Industrial Microorganism, Glavmicrobioprom at Council of Ministers of the USSR
    Moscow, USSR

Abstract

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).
Full text: (PDF, in Russian)

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.