Point Matching Under Non-Uniform Distortions and Protein Side Chain Packing Based on an Efficient Maximum Clique Algorithm

Dukka Bahadur K. C.[1] (dukka@kuicr.kyoto-u.ac.jp)
Tatsuya Akutsu[1] (takutsu@kuicr.kyoto-u.ac.jp)
Etsuji Tomita[2] (tomita@ice.uec.ac.jp)
Tomokazu Seki[2] (seki-t@ice.uec.ac.jp)
Asao Fujiyama[3] (afujiyam@nii.ac.jp)

[1]Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan
[2]Graduate School of Electro-Communications, The University of Electro-Communications, Tokyo 182-8585, Japan
[3]National Institute of Informatics, Tokyo 101-8430, Japan

Abstract

We developed maximum clique-based algorithms for spot matching for two-dimensional gel electrophoresis images, protein structure alignment and protein side-chain packing, where these problems are known to be NP-hard. Algorithms based on direct reductions to the maximum clique can find optimal solutions for instances of size (the number of points or residues) up to 50〜150 using a standard PC. We also developed pre-processing techniques to reduce the sizes of graphs. Combined with some heuristics, many realistic instances can be solved approximately.

[ Full-text PDF | Table of Contents ]