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

Tatsuya AKUTSU; Morihiro HAYASHIDA; Dukka Bahadur K.C.; Etsuji TOMITA; Jun'ichi SUZUKI; Katsuhisa HORIMOTO

doi:10.1093/ietfec/e89-a.5.1215

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

Tatsuya AKUTSU, Morihiro HAYASHIDA, Dukka Bahadur K.C., Etsuji TOMITA, Jun'ichi SUZUKI, Katsuhisa HORIMOTO

Full Text Views

0

Share
Cite this

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

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://globals.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 -