# DIMACS Seminar on Math and CS in Biology

## Title:

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

## Speaker:

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

## Place:

- CoRE Building, Conference Room 433
- Busch Campus, Rutgers University

## Time:

- 1:30 PM - NOTE UNUSUAL TIME AND DATE
- 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.
## Abstract:

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