{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T07:30:05Z","timestamp":1770795005543,"version":"3.50.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1995,2,1]],"date-time":"1995-02-01T00:00:00Z","timestamp":791596800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,2]]},"DOI":"10.1007\/bf01188582","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T21:03:45Z","timestamp":1108674225000},"page":"77-105","source":"Crossref","is-referenced-by-count":96,"title":["DNA physical mapping and alternating Eulerian cycles in colored graphs"],"prefix":"10.1007","volume":"13","author":[{"given":"P. A.","family":"Pevzner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01188582_CR1","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0167-5060(08)70852-5","volume":"8","author":"J. Abrham","year":"1980","unstructured":"Abrham, J., and Kotzig, A. Transformations of Eulerian tours.Ann. Discrete Math.,8 (1980), 65\u201369.","journal-title":"Ann. Discrete Math."},{"key":"BF01188582_CR2","first-page":"97","volume":"4","author":"L. Allison","year":"1988","unstructured":"Allison, L., and Yee, C. N. Restriction site mapping is in separation theory.CABIOS,4 (1988), 97\u2013101.","journal-title":"CABIOS"},{"key":"BF01188582_CR3","first-page":"111","volume":"4","author":"B. Bellon","year":"1988","unstructured":"Bellon, B. Construction of restriction maps.CABIOS,4 (1988), 111\u2013115.","journal-title":"CABIOS"},{"key":"BF01188582_CR4","first-page":"190","volume-title":"Lecture Notes in Computer Science, Vol. 557","author":"A. Benkouar","year":"1991","unstructured":"Benkouar, A., Manoussakis, Y. G., Paschos, V. T., and Saad R. On the complexity of some Hamiltonian and Eulerian problems in edge-coloured complete graphs. In W. L. Hsu and R. C. T. Lee (eds.),ISA '91 Algorithms. Proceedings of the 2nd International Symposium on Algorithms, Taipei, December 1991. Lecture Notes in Computer Science, Vol. 557. Springer-Verlag, Berlin, 1991, pp. 190\u2013198."},{"key":"BF01188582_CR5","first-page":"117","volume":"4","author":"T. I. Dix","year":"1988","unstructured":"Dix, T. I., and Kieronska, D. H. Errors between sites in restriction site mapping.CABIOS,4 (1988), 117\u2013123.","journal-title":"CABIOS"},{"key":"BF01188582_CR6","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1093\/nar\/12.1Part2.703","volume":"12","author":"R. Durand","year":"1984","unstructured":"Durand, R., and Bregegere, F. An efficient program to construct restriction maps from experimental data with realistic error levels.Nucleic Acids Res.,12 (1984), 703\u2013716.","journal-title":"Nucleic Acids Res."},{"key":"BF01188582_CR7","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(88)90170-6","volume":"28","author":"J. Ebert","year":"1988","unstructured":"Ebert, J. Computing Eulerian trails.Inform. Process. Lett.,28 (1988), 93\u201397.","journal-title":"Inform. Process. Lett."},{"key":"BF01188582_CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0378-1119(83)90060-4","volume":"22","author":"W. M. Fitch","year":"1983","unstructured":"Fitch, W. M., Smith, T. F., and Ralph, W. W. Mapping the order of DNA restriction fragments,Gene,22 (1983), 19\u201329.","journal-title":"Gene"},{"key":"BF01188582_CR9","volume-title":"Flows in Networks","author":"I. R. Ford","year":"1962","unstructured":"Ford, I. R., and Fulkerson, D. R.Flows in Networks. Princeton University Press, Princeton, NJ, 1962."},{"key":"BF01188582_CR10","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0196-8858(87)90013-3","volume":"8","author":"L. Goldstein","year":"1987","unstructured":"Goldstein, L., and Waterman, M. S. Mapping DNA by stochastic relaxation.Adv. in Appl. Math.,8 (1987), 194\u2013207.","journal-title":"Adv. in Appl. Math."},{"key":"BF01188582_CR11","first-page":"107","volume":"6","author":"A. V. Grigorjev","year":"1990","unstructured":"Grigorjev, A. V., and Mironov, A. A. Mapping DNA by stochastic relaxation: a new approach to fragment sizes.CABIOS,6 (1990), 107\u2013111.","journal-title":"CABIOS"},{"key":"BF01188582_CR12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.3109\/10425179109020776","volume":"1","author":"A. V. Grigorjev","year":"1991","unstructured":"Grigorjev, A. V., and Mironov, A. A. Mapping DNA by stochastic relaxation: a schedule for optimal annealing.J. DNA Mapping and Sequencing,1 (1991), 221\u2013226.","journal-title":"J. DNA Mapping and Sequencing"},{"key":"BF01188582_CR13","unstructured":"Hall, M., Jr.,Combinatorial Theory. Toronto, 1967."},{"key":"BF01188582_CR14","first-page":"195","volume":"6","author":"S. T. S. Ho","year":"1990","unstructured":"Ho, S. T. S., Allison, L., and Yee, C. N. Restriction site mapping for three or more enzymes.CABIOS,6 (1990), 195\u2013204.","journal-title":"CABIOS"},{"key":"BF01188582_CR15","first-page":"47","volume-title":"Nucleic Acids and Protein Sequence Analysis: Practical Approaches","author":"P. Hoyle","year":"1987","unstructured":"Hoyle, P. Use of commercial software on IBM personal computers. In M. J. Bishop and C. J. Rawlings (eds),Nucleic Acids and Protein Sequence Analysis: Practical Approaches. IRL Press, Oxford, 1987, pp. 47\u201382."},{"key":"BF01188582_CR16","first-page":"76","volume":"18","author":"A. Kotzig","year":"1968","unstructured":"Kotzig A. Moves without forbidden transitions in a graph.Mat. casopis,18 (1968), 76\u201380.","journal-title":"Mat. casopis"},{"key":"BF01188582_CR17","doi-asserted-by":"crossref","first-page":"7298","DOI":"10.1073\/pnas.85.19.7298","volume":"85","author":"M. Krawczak","year":"1988","unstructured":"Krawczak, M. Algorithms for the restriction site mapping of DNA molecules.Proc. Nat. Acad. Sci. USA,85 (1988), 7298\u20137301.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"BF01188582_CR18","unstructured":"Mironov, A. A., Alexandrov, N. N., Bogodarova, N. Yu., Grigorjev, A., Lebedev, V. F., Lunovskaya, L. V., Pevzner, P. A., and Truchan M. E. DNASUN: A Package of Computer Programs for Biotechnology Laboratory (submitted)."},{"key":"BF01188582_CR19","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1006\/aama.1993.1009","volume":"14","author":"L. Newberg","year":"1993","unstructured":"Newberg, L., and Naor, D. A lower bound on the number of solutions to the probed partial digest problem.Adv. in Appl. Math.,14 (1993), 172\u2013185.","journal-title":"Adv. in Appl. Math."},{"key":"BF01188582_CR20","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1093\/nar\/12.1Part2.717","volume":"12","author":"G. P. Nolan","year":"1984","unstructured":"Nolan, G. P., Maina, C. V., and Szalay, A. A. Plasmid mapping computer program.Nucleic Acids Res.,12 (1984), 717\u2013729.","journal-title":"Nucleic Acids Res."},{"key":"BF01188582_CR21","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1093\/nar\/10.1.217","volume":"10","author":"W. Pearson","year":"1982","unstructured":"Pearson, W. Automatic construction of restriction site maps.Nucleic Acids Res.,10 (1982), 217\u2013227.","journal-title":"Nucleic Acids Res."},{"key":"BF01188582_CR22","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7124\/bc.000230","volume":"5","author":"P. A. Pevzner","year":"1988","unstructured":"Pevzner, P. A. Graphs of restrictions and DNA physical mapping.Biopolymers and Cell,5 (1988), 233\u2013237 (in Russian).","journal-title":"Biopolymers and Cell"},{"key":"BF01188582_CR23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/07391102.1989.10507752","volume":"7","author":"P. A. Pevzner","year":"1989","unstructured":"Pevzner, P. A. \u03b9-tuple DNA sequencing: a computer analysis.J. Biom. Struct. Dyn.,7 (1989), 63\u201373.","journal-title":"J. Biom. Struct. Dyn."},{"key":"BF01188582_CR24","first-page":"154","volume-title":"Computer Analysis of Genetic Texts","author":"P. A. Pevzner","year":"1990","unstructured":"Pevzner, P. A. DNA physical mapping. In M. D. Frank-Kamenetzky (ed.),Computer Analysis of Genetic Texts. Nauka, Moscow, 1990, pp. 154\u2013188 (in Russian)."},{"key":"BF01188582_CR25","doi-asserted-by":"crossref","unstructured":"Pevzner, P. A.DNA Physical Mapping, Flows in Networks and Minimum Cycles Mean in Graphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 8, 1992, pp. 99\u2013112.","DOI":"10.1090\/dimacs\/008\/07"},{"key":"BF01188582_CR26","unstructured":"Pevzner, P. A. (1994) MAPSUN: a DNA physical mapping computer algorithm (in preparation)."},{"key":"BF01188582_CR27","first-page":"788","volume":"21","author":"P. A. Pevzner","year":"1987","unstructured":"Pevzner, P. A., and Mironov, A. A. An efficient method for physical mapping of DNA molecules.Molek. Biol,21 (1987), 788\u2013796.","journal-title":"Molek. Biol"},{"key":"BF01188582_CR28","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1093\/nar\/12.1Part1.227","volume":"12","author":"G. Polner","year":"1984","unstructured":"Polner, G., Dorgai, L., and Orosz, L. PMAP, PMAPS: DNA physical map construction programs.Nucleic Acids Res.,12 (1984), 227\u2013236.","journal-title":"Nucleic Acids Res."},{"key":"BF01188582_CR29","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/0196-8858(91)90028-H","volume":"12","author":"W. Schmitt","year":"1991","unstructured":"Schmitt, W., and Waterman, M. Multiple solutions of DNA restriction mapping problem.Adv. in Appl. Math.,12 (1991), 412\u2013427.","journal-title":"Adv. in Appl. Math."},{"key":"BF01188582_CR30","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0004-3702(78)90013-9","volume":"11","author":"M. Stefik","year":"1978","unstructured":"Stefik, M. Inferring DNA structure from segmentation data.Artificial Intelligence,11 (1978), 85\u2013114.","journal-title":"Artificial Intelligence"},{"key":"BF01188582_CR31","first-page":"103","volume":"4","author":"P. Tuffery","year":"1988","unstructured":"Tuffery, P., Dessen, P., Mugnier, C., and Hazout, S. Restriction map construction using a \u201ccomplete sentences compatibility\u201d algorithm.CABIOS,4 (1988), 103\u2013110.","journal-title":"CABIOS"},{"key":"BF01188582_CR32","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E. Ukkonen","year":"1992","unstructured":"Ukkonen, E. Approximate string matching withq-grams and maximal matches.Theoret. Comput. Sci.,92 (1992), 191\u2013211.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01188582_CR33","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02460022","volume":"48","author":"M. S. Waterman","year":"1986","unstructured":"Waterman, M. S., and Griggs, J. R. Interval graphs and maps of DNA.Bull. Math. Biol.,48 (1986), 189\u2013195.","journal-title":"Bull. Math. Biol."},{"key":"BF01188582_CR34","first-page":"521","volume-title":"Restriction site mapping in CLP(\u211b)","author":"R. H. C. Yap","year":"1991","unstructured":"Yap, R. H. C. Restriction site mapping in CLP(\u211b).Proceedings of the 8th International Conference on Logic Programming, MIT Press, Cambridge, MA, 1991, pp. 521\u2013534."},{"key":"BF01188582_CR35","first-page":"147","volume-title":"Nucleic Acids and Protein Sequences Analysis, Practical Approaches","author":"G. Zehetner","year":"1987","unstructured":"Zehetner, G., Frischauf, A., and Lehrach, H. Approaches to restriction map determination. In M. J. Bishop and C. J. Rawlings (eds.),Nucleic Acids and Protein Sequences Analysis, Practical Approaches. IRL Press, Oxford, 1987, pp. 147\u2013164."},{"key":"BF01188582_CR36","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1093\/nar\/14.1.335","volume":"14","author":"G. Zehetner","year":"1986","unstructured":"Zehetner, G., and Lehrach, H. A computer program package for restriction map analysis and manipulation,Nucleic Acids Res.,14 (1986), 335\u2013349.","journal-title":"Nucleic Acids Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188582.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188582\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:33:56Z","timestamp":1586118836000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,2]]},"references-count":36,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,2]]}},"alternative-id":["BF01188582"],"URL":"https:\/\/doi.org\/10.1007\/bf01188582","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,2]]}}}