Protein Structure Alignment Using a Graph Matching Technique

Tatsuya Akutsu (

Department of Computer Science, Gunma University
1-5-1 Tenjin-cho, Kiryu 376 Japan


This paper proposes new algorithms for protein structure alignment. Protein structure alignment is, given two three-dimensional protein structures, to find spatially equivalent residue pairs. Each algorithm consists of the following two steps: first an initial superposition is computed; then a structure alignment is computed and refined using bipartite graph matching. The proposed algorithms are shown to be useful through an experimental comparison with a previous alignment algorithm.