Related Experiment Videos
Point matching under non-uniform distortions and protein side chain packing based on an efficient maximum clique
Bahadur K C Dukka1, Tatsuya Akutsu, Etsuji Tomita
1Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan. dukka@kuicr.kyoto-u.ac.jp
Genome Informatics. International Conference on Genome Informatics
|October 23, 2003
Summary
We developed maximum clique algorithms to solve complex computational biology problems like protein alignment. These algorithms efficiently find optimal solutions for moderately sized problems and approximate solutions for larger ones.
Area of Science:
- Computational Biology
- Bioinformatics
- Algorithm Development
Background:
- NP-hard problems in computational biology, such as spot matching in 2D gel electrophoresis, protein structure alignment, and protein side-chain packing, lack efficient optimal solutions.
- Existing methods may struggle with the computational complexity of these biological data analysis tasks.
Purpose of the Study:
- To develop novel maximum clique-based algorithms for solving NP-hard problems in computational biology.
- To provide efficient computational tools for analyzing biological data, including 2D gel electrophoresis images and protein structures.
Main Methods:
- Developed algorithms based on direct reductions to the maximum clique problem.
- Implemented pre-processing techniques to reduce graph sizes for improved efficiency.
- Utilized heuristics to approximate solutions for large-scale instances.
Main Results:
- Optimal solutions were found for problem instances up to 50-150 points or residues on a standard PC.
- Pre-processing techniques effectively reduced graph sizes, enhancing algorithm performance.
- Heuristics enabled approximate solutions for many realistic, larger instances.
Conclusions:
- Maximum clique-based algorithms offer an effective approach for tackling NP-hard problems in computational biology.
- The developed algorithms provide a practical means for achieving optimal or approximate solutions in protein structure analysis and gel electrophoresis image processing.
- This work contributes efficient computational strategies for key bioinformatics challenges.