DIMACS Seminar on Math and CS in Biology


The Application of the Algorithm for Finding Maximal Common Subtopologies to Protein Structures


Ina Koch
Institute for Algorithms and Scientific Computing, SCAI
GMD - German National Research Center for Information Technology
D-53754 Sankt Augustin, Germany


CoRE Building, Conference Room 433
Busch Campus, Rutgers University


Friday, March 22, 1996
* Note unusual time and date. If you would like to meet with Dr Koch, please send mail to durandd@dimacs.rutgers.edu.


Protein structures are complex structures which can be described at the four different structural levels as the primary, secondary, tertiary, and quarternarystructure. The primary structure is modeled as string usually. The secondary andtertiary structure are often modeled as undirected graphs [1][2][3][4][5].

For classification and motif search in proteins it is useful to consider the secondary structure. It can be modeled according to the participating secondary structure elements as an "alpha", "beta", or "alpha-beta" graph. In this graph, the vertices correspond to alpha-helices or/and beta-strands, and the edges represent spatial and/or topological neighborhoods between the vertices. The representation as undirected labeled graphs is useful for a unique well-defined description at a certain structural level and for applying effective graph-theoretical algorithms, for example for substructure search or maximal common subgraph search.

We developed an algorithm which finds all maximal common subtopologies in a set of protein structures in a reasonable amount of time and space. In this talk, I discuss the application of our algorithm to protein structures focusing on biological aspects.

[1] Mitchell,E.M. and Artymiuk,P.J. and Rice,D.W., and Willett,P. 1989. J.Mol.Biol. 212, 151--166.
[2] Brint,A.T. and Davies,H.M. and Mitchell,E.M., and Willett,P. 1989. J.Mol.Graphics 7, 48--53.
[3] Grindley,H.M. and Artymiuk,P.J. and Rice,D.W., and Willett,P. 1990. J.Mol.Biol. 229, 707--721.
[4] Kaden,F. and Koch,I., and Selbig,J. 1990. J.theor.Biol. 147, 85--100.
[5] Koch,I. and Kaden,F., and Selbig,J. 1992. PROTEINS: Str., Funct., and Gen. 12, 314--323.

Document last modified on March 19, 1996