Wednesday, September 20, 2006


Dukka Bahadur K.C.

Kyoto university Entry: April 1997

Graduation Date: March 2006

DegreeObtained : B.Eng, M.Inf., D.Inf.Research

Area: Bioinformatics

Current Address: Atlanta, USA

NEpal Add: Satdobato, Lalitpur



Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach
Full text
Pdf (252 KB)
ACM International Conference Proceeding Series; Vol. 55 archiveProceedings of the second conference on Asia-Pacific bioinformatics - Volume 29 table of contents
Dunedin, New Zealand
Pages: 191 - 200
Year of Publication: 2004
K. C. Dukka Bahadur
Kyoto University, Kyoto, Japan
Tatsuya Akutsu
Kyoto University, Kyoto, Japan
Etsuji Tomita
The University of Electro-Communications, Tokyo, Japan
Tomokazu Seki
The University of Electro-Communications, Tokyo, Japan
Australian Computer Society, Inc. Darlinghurst, Australia, Australia
Additional Information:
abstract references index terms collaborative colleagues peer to peer
Tools and Actions:
Find similar Articles Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref
Protein side-chain packing has an important application in homology modeling, protein structure prediction, protein design, protein docking problems and many more.Protein side-chain packing problem is computationally known to be NP-hard (Akutsu, 1997) (Chazelle, Kingsford & Singh, 2003) (Pierce & Winfree, 2002). In the field of computer science, the notion of reduction of a problem to other problems is quite often used to design algorithms and to prove the complexity of a certain problem. In this work, we have used this notion of reduction to solve protein side-chain packing problem.We have developed a deterministic algorithm based approach to solve protein side-chain packing problem based on clique-based algorithms. For this, we reduced this problem to the maximum clique finding problem. Moreover, in order to incorporate the interaction preferences between the atoms, we have then extended this approach to maximum edge-weight clique finding problem by assigning weights based on probability discriminatory function. We have then solved this clique finding problem by using the clique finding algorithm developed by two of the authors (Tomita & Seki, 2003) and its variants (Suzuki, Tomita & Seki 2002).We have tested this approach to predict the side-chain conformations of a set of proteins and have compared the results with other existing methods. We have found considerable improvement in terms of the size of the proteins and in terms of the efficiency and accuracy of the prediction.