Point matching under non-uniform distortions and protein side chain packing based on an efficient maximum clique algorithm.
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.
Dukka
Bahadur K C
BK
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan. dukka@kuicr.kyoto-u.ac.jp
Akutsu
Tatsuya
T
Tomita
Etsuji
E
Seki
Tomokazu
T
Fujiyama
Asao
A
D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods; D003627:Data Interpretation, Statistical; D015180:Electrophoresis, Gel, Two-Dimensional / Q000379:methods; D006801:Humans; D017434:Protein Structure, Tertiary; D016415:Sequence Alignment / Q000379:methods; D020539:Sequence Analysis, Protein / Q000379:methods*