IEICE TRANSACTIONS on Fundamentals
Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1215-1222
- Publication Date
- 2006/05/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e89-a.5.1215
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tatsuya AKUTSU, Morihiro HAYASHIDA, Dukka Bahadur K.C., Etsuji TOMITA, Jun'ichi SUZUKI, Katsuhisa HORIMOTO, "Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints" in IEICE TRANSACTIONS on Fundamentals,
vol. E89-A, no. 5, pp. 1215-1222, May 2006, doi: 10.1093/ietfec/e89-a.5.1215.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1215/_p
Copy
@ARTICLE{e89-a_5_1215,
author={Tatsuya AKUTSU, Morihiro HAYASHIDA, Dukka Bahadur K.C., Etsuji TOMITA, Jun'ichi SUZUKI, Katsuhisa HORIMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints},
year={2006},
volume={E89-A},
number={5},
pages={1215-1222},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1215},
ISSN={1745-1337},
month={May},}
Copy
TY - JOUR
TI - Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1215
EP - 1222
AU - Tatsuya AKUTSU
AU - Morihiro HAYASHIDA
AU - Dukka Bahadur K.C.
AU - Etsuji TOMITA
AU - Jun'ichi SUZUKI
AU - Katsuhisa HORIMOTO
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1215
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - 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.
ER -
English
