Skip to main content
SpringerLink
Log in

Interval graphs and maps of DNA

  • Published:
Bulletin of Mathematical Biology Aims and scope Submit manuscript

Abstract

A special class of interval graphs is defined and characterized, and an algorithm is given for their construction. These graphs are motivated by an important representation of DNA called restriction maps by molecular biologists. Circular restriction maps are easily included.

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.

Institutional subscriptions

Similar content being viewed by others

Literature

  • Benzer, S. 1959. “On the topology of genetic fine structure.”Proc. natn. Acad. Sci. U.S.A. 45, 1607–1620.

    Article  Google Scholar 

  • Booth, K. S. and G. S. Leuker. 1976. “Testing for the consecutive ones property, interval graphs, and graph planarity using PO algorithms.”J. Comput. Syst. Sci. 13, 335–379.

    MATH  Google Scholar 

  • Danna, K. J., G. H. Sack and D. Nathans. 1973. “Studies of Simian Virus 40 DNA. VII. A cleavage map of the SV40 genome.”J. molec. Biol. 78, 363–376.

    Article  Google Scholar 

  • Fitch, W. M., T. F. Smith, and W. W. Ralph. 1983. “Mapping the order of DNA restriction fragments.”Gene 22, 19–29.

    Article  Google Scholar 

  • Fulkerson, D. R. and O. A. Gross. 1964. “Incidence matrices with the consecutive 1s property.”Bull. Am. math. Soc. 70, 681–684.

    Article  MATH  MathSciNet  Google Scholar 

  • Gilmore, P. C. and A. J. Hoffman. 1964. “A characterization of comparability graphs and of interval graphs.”Can. J. Math. 16, 539–548.

    MATH  MathSciNet  Google Scholar 

  • Golumbic, M. C. 1980.Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press.

    MATH  Google Scholar 

  • Jungck, J. R., G. Dick and A. G. Dick. 1982. “Computer-assisted sequencing, interval graphs, and molecular evolution.”Bio-Syst. 15, 259–273.

    Google Scholar 

  • Lekkerkerker, C. G. and J. C. Boland. 1962. “Representation of a finite graph by a set of intervals on the real line.”Fund. Math. 51, 45–64.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departments of Mathematics and of Biological Sciences, University of Southern California, 90089-1113, Los Angeles, CA, USA

    Michael S. Waterman

  2. Department of Mathematics and Statistics, University of South Carolina, 29208, SC, USA

    Jerrold R. Griggs

Authors
  1. Michael S. Waterman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jerrold R. Griggs
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by a grant from the System Development Foundation.

Supported by an NSF grant and through a grant from the System Development Foundation.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Waterman, M.S., Griggs, J.R. Interval graphs and maps of DNA. Bltn Mathcal Biology 48, 189–195 (1986). https://doi.org/10.1007/BF02460022

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation