×

DNA physical mapping and alternating Eulerian cycles in colored graphs. (English) Zbl 0840.92011

Summary: Small-scale DNA physical mapping (such as the Double Digest Problem or DDP) is an important and difficult problem in computational molecular biology. When enzyme sites are modeled by a random process, the number of solutions to DDP is known to increase exponentially as the length of DNA increases. However, the overwhelming majority of solutions are very similar and can be transformed into each other by simple transformations. Recently, W. Schmitt and M. S. Waterman [Adv. Appl. Math. 12, No. 4, 412-427 (1991; Zbl 0760.92007)]introduced equivalence classes on the set of DDP solutions and raised an open problem to completely characterize equivalent physical maps.
We study the combinatorics of multiple solutions and the cassette transformations of Schmitt and Waterman. We demonstrate that the solutions to DDP are closely associated with alternating Eulerian cycles in colored graphs and study order transformations of alternating cycles. We prove that every two alternating Eulerian cycles in a bicolored graph can be transformed into each other by means of order transformations. Using this result we obtain a complete characterization of equivalent physical maps in the Schmitt-Waterman problem. It also allows us to prove E. Ukkonen’s [Theor. Comput. Sci. 92, No. 1, 191-211 (1992; Zbl 0747.68026)]conjecture on word transformations preserving \(q\)-gram composition.

MSC:

92C40 Biochemistry, molecular biology
68R10 Graph theory (including graph drawing) in computer science
05C90 Applications of graph theory
68R15 Combinatorics on words
05C15 Coloring of graphs and hypergraphs

Software:

DNASUN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abrham, J., and Kotzig, A. Transformations of Eulerian tours.Ann. Discrete Math.,8 (1980), 65–69. · Zbl 0453.05045 · doi:10.1016/S0167-5060(08)70852-5
[2] Allison, L., and Yee, C. N. Restriction site mapping is in separation theory.CABIOS,4 (1988), 97–101.
[3] Bellon, B. Construction of restriction maps.CABIOS,4 (1988), 111–115.
[4] 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–198.
[5] Dix, T. I., and Kieronska, D. H. Errors between sites in restriction site mapping.CABIOS,4 (1988), 117–123.
[6] 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–716. · Zbl 05435438 · doi:10.1093/nar/12.1Part2.703
[7] Ebert, J. Computing Eulerian trails.Inform. Process. Lett.,28 (1988), 93–97. · Zbl 0658.68076 · doi:10.1016/0020-0190(88)90170-6
[8] Fitch, W. M., Smith, T. F., and Ralph, W. W. Mapping the order of DNA restriction fragments,Gene,22 (1983), 19–29. · doi:10.1016/0378-1119(83)90060-4
[9] Ford, I. R., and Fulkerson, D. R.Flows in Networks. Princeton University Press, Princeton, NJ, 1962. · Zbl 0106.34802
[10] Goldstein, L., and Waterman, M. S. Mapping DNA by stochastic relaxation.Adv. in Appl. Math.,8 (1987), 194–207. · Zbl 0638.92005 · doi:10.1016/0196-8858(87)90013-3
[11] Grigorjev, A. V., and Mironov, A. A. Mapping DNA by stochastic relaxation: a new approach to fragment sizes.CABIOS,6 (1990), 107–111.
[12] 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–226.
[13] Hall, M., Jr.,Combinatorial Theory. Toronto, 1967.
[14] Ho, S. T. S., Allison, L., and Yee, C. N. Restriction site mapping for three or more enzymes.CABIOS,6 (1990), 195–204.
[15] 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–82.
[16] Kotzig A. Moves without forbidden transitions in a graph.Mat. casopis,18 (1968), 76–80. · Zbl 0155.31901
[17] Krawczak, M. Algorithms for the restriction site mapping of DNA molecules.Proc. Nat. Acad. Sci. USA,85 (1988), 7298–7301. · doi:10.1073/pnas.85.19.7298
[18] 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).
[19] 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–185. · Zbl 0776.92006 · doi:10.1006/aama.1993.1009
[20] Nolan, G. P., Maina, C. V., and Szalay, A. A. Plasmid mapping computer program.Nucleic Acids Res.,12 (1984), 717–729. · Zbl 05436477 · doi:10.1093/nar/12.1Part2.717
[21] Pearson, W. Automatic construction of restriction site maps.Nucleic Acids Res.,10 (1982), 217–227. · Zbl 05436574 · doi:10.1093/nar/10.1.217
[22] Pevzner, P. A. Graphs of restrictions and DNA physical mapping.Biopolymers and Cell,5 (1988), 233–237 (in Russian).
[23] Pevzner, P. A. {\(\iota\)}-tuple DNA sequencing: a computer analysis.J. Biom. Struct. Dyn.,7 (1989), 63–73.
[24] Pevzner, P. A. DNA physical mapping. In M. D. Frank-Kamenetzky (ed.),Computer Analysis of Genetic Texts. Nauka, Moscow, 1990, pp. 154–188 (in Russian).
[25] 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–112. · Zbl 0784.92013
[26] Pevzner, P. A. (1994) MAPSUN: a DNA physical mapping computer algorithm (in preparation).
[27] Pevzner, P. A., and Mironov, A. A. An efficient method for physical mapping of DNA molecules.Molek. Biol,21 (1987), 788–796.
[28] Polner, G., Dorgai, L., and Orosz, L. PMAP, PMAPS: DNA physical map construction programs.Nucleic Acids Res.,12 (1984), 227–236. · Zbl 05436657 · doi:10.1093/nar/12.1Part1.227
[29] Schmitt, W., and Waterman, M. Multiple solutions of DNA restriction mapping problem.Adv. in Appl. Math.,12 (1991), 412–427. · Zbl 0760.92007 · doi:10.1016/0196-8858(91)90028-H
[30] Stefik, M. Inferring DNA structure from segmentation data.Artificial Intelligence,11 (1978), 85–114. · doi:10.1016/0004-3702(78)90013-9
[31] Tuffery, P., Dessen, P., Mugnier, C., and Hazout, S. Restriction map construction using a ”complete sentences compatibility” algorithm.CABIOS,4 (1988), 103–110.
[32] Ukkonen, E. Approximate string matching withq-grams and maximal matches.Theoret. Comput. Sci.,92 (1992), 191–211. · Zbl 0747.68026 · doi:10.1016/0304-3975(92)90143-4
[33] Waterman, M. S., and Griggs, J. R. Interval graphs and maps of DNA.Bull. Math. Biol.,48 (1986), 189–195. · Zbl 0585.92015
[34] Yap, R. H. C. Restriction site mapping in CLP().Proceedings of the 8th International Conference on Logic Programming, MIT Press, Cambridge, MA, 1991, pp. 521–534.
[35] 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–164.
[36] Zehetner, G., and Lehrach, H. A computer program package for restriction map analysis and manipulation,Nucleic Acids Res.,14 (1986), 335–349. · Zbl 05437403 · doi:10.1093/nar/14.1.335
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.