Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Protein Side-chain Packing Problem: A Maximum Edge-weight Clique Algorithmic Approach

Dukka, B.K.C., Akutsu, T., Seki, T. and Tomita, E.

    Protein side-chain packing has an important application in homology modelling, protein structure prediction, protein design, protein docking problems qnd 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 tow of the authors (Tomita & Seki, 2003) and its variants (Suzuki, Tomita & Seki 2202). 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.
Cite as: Dukka, B.K.C., Akutsu, T., Seki, T. and Tomita, E. (2004). Protein Side-chain Packing Problem: A Maximum Edge-weight Clique Algorithmic Approach. In Proc. Second Asia-Pacific Bioinformatics Conference (APBC2004), Dunedin, New Zealand. CRPIT, 29. Chen, Y.-P. P., Ed. ACS. 191-200.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS
 

 

ACS Logo© Copyright Australian Computer Society Inc. 2001-2014.
Comments should be sent to the webmaster at crpit@scem.uws.edu.au.
This page last updated 16 Nov 2007