Elsevier

Biosystems

Volume 15, Issue 3, 1982, Pages 259-273
Biosystems

Computer-assisted sequencing, interval graphs, and molecular evolution

Dedicated to Sidney W. Fox on the occasion of his 70th birthday.
https://doi.org/10.1016/0303-2647(82)90010-7Get rights and content

Abstract

In 1945, Fox developed the strategy for sequencing long proteins by using overlapping fragments. We show how the formal mathematical technique for the construction of interval graphs (Gilmore and Hoffman, 1964) is useful both pedagogically for understanding the underlying logic of sequencing linear molecules and is more amenable to automation because of its algorithmic nature. We also present a computer program, that employs the interval graph algorithm, which can be used to sequence proteins when given digest data. An example is given to illustrate all the steps involved in the algorithmic processing of the data. The need for such developments with respect to molecular evolution is discussed.

References (60)

  • S. Benzer

    On the topology of genetic fine structure

  • S. Benzer

    On the topography of the genetic fine structure

  • S. Benzer

    The fine structure of the gene

    Sci. Am.

    (1962)
  • S.A. Bernhard et al.

    Automatic determination of amino acid sequences

    IBM J. Res. Dev.

    (1963)
  • M.O. Bertman et al.

    Group graph of the genetic code

    J. Hered.

    (1979)
  • C. Bron et al.

    Algorithm 457 — Finding all cliques of an undirected graph

    Commun. Assoc. Comput. Mach.

    (1973)
  • V.W. Bryant et al.

    Transitive graphs

    J. London Math. Soc.

    (1975)
  • N. Christofides

    Graph theory: An algorithmic approach

  • J.E. Cohen

    Food webs and niche space

    (1978)
  • J.E. Cohen et al.

    The probability of an interval graph, and why it matters

  • M.B. Cozzens

    Higher and multi-dimensional analogues of interval graphs

  • L.R. Croft

    Introduction to protein sequence analysis

    (1980)
  • S.D. Daubert et al.

    Computer simulation of the determination of amino acid sequences in polypeptides

    J. Chem. Educ.

    (1977)
  • M.O. Dayhoff

    Computer aids to protein sequence determination

    J. Theor. Biol.

    (1964)
  • M.O. Dayhoff
  • M.O. Dayhoff et al.

    A computer program for complete sequence analysis of large proteins from mass spectrophotometry data of a single sample

    Comput. Biol. Med.

    (1971)
  • R.G. Duggleby et al.

    A computer program for determining the size of DNA restriction fragments

    Anal. Biochem.

    (1981)
  • P. Erdos

    On cliques in graphs

    Israel J. Math.

    (1966)
  • S. Even et al.

    Permutation graphs and transitive graphs

    J. Assoc. Comput. Mach.

    (1972)
  • L. Festinger

    The analysis of sociograms using matrix algebra

    Hum. Relat.

    (1949)
  • Cited by (0)

    Present address: 17E Pembroke Circle, Wappingers Falls, NY 12590, U.S.A.

    View full text