Skip Navigation

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 2006 E89-A(5):1215-1222; doi:10.1093/ietfec/e89-a.5.1215
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Request Permissions
Google Scholar
Right arrow Articles by AKUTSU, T.
Right arrow Articles by HORIMOTO, K.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Copyright © 2006 The Institute of Electronics, Information and Communication Engineers

Special Section on Discrete Mathematics and Its Applications -- Papers

Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints*

Tatsuya AKUTSU1, Morihiro HAYASHIDA1, Dukka BAHADUR K.C.1, Etsuji TOMITA2, Jun'ichi SUZUKI2 and Katsuhisa HORIMOTO3

1 The authors are with the Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji-shi, 611-0011 Japan. E-mail: takutsu{at}kuicr.kyoto-u.ac.jp, 2 The authors are with the Graduate School of Electro-communications, The University of Electro-Communications, Chofu-shi, 182-8585 Japan., 3 The author is with the Human Genome Center, Institute of Medical Science, The University of Tokyo, Tokyo, 108-8639 Japan.

The protein threading problem with profiles is known to be efficiently solvable using dynamic programming. In this paper, we consider a variant of the protein threading problem with profiles in which constraints on distances between residues are given. We prove that protein threading with profiles and constraints is NP-hard. Moreover, we show a strong hardness result on the approximation of an optimal threading satisfying all the constraints. On the other hand, we develop two practical algorithms: CLIQUETHREAD and BBDPTHREAD. CLIQUETHREAD reduces the threading problem to the maximum edge-weight clique problem, whereas BBDPTHREAD combines dynamic programming and branch-and-bound techniques. We perform computational experiments using protein structure data in PDB (Protein Data Bank) using simulated distance constraints. The results show that constraints are useful to improve the alignment accuracy of the target sequence and the template structure. Moreover, these results also show that BBDPTHREAD is in general faster than CLIQUETHREAD for larger size proteins whereas CLIQUETHREAD is useful if there does not exist a feasible threading.

Key Words: maximum edge weight clique, dynamic programming, protein threading, profiles, distance constraints

Manuscript received August 13, 2005. Manuscript revised November 2, 2005. Final manuscript received December 15, 2005.

* A preliminary version of the paper was presented at IEEE 4th Symp. Bioinformatics and Bioengineering (BIBE2004).


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.