Skip to main content
SpringerLink
Log in

DNA physical mapping and alternating Eulerian cycles in colored graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

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, Schmitt and Waterman [SW] 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 Ukkonen's conjecture on word transformations preservingq-gram composition.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Abrham, J., and Kotzig, A. Transformations of Eulerian tours.Ann. Discrete Math.,8 (1980), 65–69.

    Article  MATH  MathSciNet  Google Scholar 

  2. Allison, L., and Yee, C. N. Restriction site mapping is in separation theory.CABIOS,4 (1988), 97–101.

    Google Scholar 

  3. Bellon, B. Construction of restriction maps.CABIOS,4 (1988), 111–115.

    Google Scholar 

  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.

    Google Scholar 

  5. Dix, T. I., and Kieronska, D. H. Errors between sites in restriction site mapping.CABIOS,4 (1988), 117–123.

    Google Scholar 

  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.

    Article  Google Scholar 

  7. Ebert, J. Computing Eulerian trails.Inform. Process. Lett.,28 (1988), 93–97.

    Article  MATH  MathSciNet  Google Scholar 

  8. Fitch, W. M., Smith, T. F., and Ralph, W. W. Mapping the order of DNA restriction fragments,Gene,22 (1983), 19–29.

    Article  Google Scholar 

  9. Ford, I. R., and Fulkerson, D. R.Flows in Networks. Princeton University Press, Princeton, NJ, 1962.

    MATH  Google Scholar 

  10. Goldstein, L., and Waterman, M. S. Mapping DNA by stochastic relaxation.Adv. in Appl. Math.,8 (1987), 194–207.

    Article  MATH  MathSciNet  Google Scholar 

  11. Grigorjev, A. V., and Mironov, A. A. Mapping DNA by stochastic relaxation: a new approach to fragment sizes.CABIOS,6 (1990), 107–111.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  16. Kotzig A. Moves without forbidden transitions in a graph.Mat. casopis,18 (1968), 76–80.

    MathSciNet  Google Scholar 

  17. Krawczak, M. Algorithms for the restriction site mapping of DNA molecules.Proc. Nat. Acad. Sci. USA,85 (1988), 7298–7301.

    Article  MathSciNet  Google Scholar 

  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.

    Article  MATH  MathSciNet  Google Scholar 

  20. Nolan, G. P., Maina, C. V., and Szalay, A. A. Plasmid mapping computer program.Nucleic Acids Res.,12 (1984), 717–729.

    Article  Google Scholar 

  21. Pearson, W. Automatic construction of restriction site maps.Nucleic Acids Res.,10 (1982), 217–227.

    Article  Google Scholar 

  22. Pevzner, P. A. Graphs of restrictions and DNA physical mapping.Biopolymers and Cell,5 (1988), 233–237 (in Russian).

    Google Scholar 

  23. Pevzner, P. A. ι-tuple DNA sequencing: a computer analysis.J. Biom. Struct. Dyn.,7 (1989), 63–73.

    Google Scholar 

  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).

    Google Scholar 

  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.

  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.

    Google Scholar 

  28. Polner, G., Dorgai, L., and Orosz, L. PMAP, PMAPS: DNA physical map construction programs.Nucleic Acids Res.,12 (1984), 227–236.

    Article  Google Scholar 

  29. Schmitt, W., and Waterman, M. Multiple solutions of DNA restriction mapping problem.Adv. in Appl. Math.,12 (1991), 412–427.

    Article  MATH  MathSciNet  Google Scholar 

  30. Stefik, M. Inferring DNA structure from segmentation data.Artificial Intelligence,11 (1978), 85–114.

    Article  Google Scholar 

  31. Tuffery, P., Dessen, P., Mugnier, C., and Hazout, S. Restriction map construction using a “complete sentences compatibility” algorithm.CABIOS,4 (1988), 103–110.

    Google Scholar 

  32. Ukkonen, E. Approximate string matching withq-grams and maximal matches.Theoret. Comput. Sci.,92 (1992), 191–211.

    Article  MATH  MathSciNet  Google Scholar 

  33. Waterman, M. S., and Griggs, J. R. Interval graphs and maps of DNA.Bull. Math. Biol.,48 (1986), 189–195.

    MATH  MathSciNet  Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  36. Zehetner, G., and Lehrach, H. A computer program package for restriction map analysis and manipulation,Nucleic Acids Res.,14 (1986), 335–349.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, The Pennsylvania State University, 16802, University Park, PA, USA

    P. A. Pevzner

Authors
  1. P. A. Pevzner
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by E. W. Myers.

This research was supported in part by the National Science Foundation under Grants DMS 90-05833 and CCR-93-08567 and the National Institute of Health under Grant GM-36230.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pevzner, P.A. DNA physical mapping and alternating Eulerian cycles in colored graphs. Algorithmica 13, 77–105 (1995). https://doi.org/10.1007/BF01188582

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01188582

Key words

Search

Navigation