protein threading with profiles and constraints Export

@inproceedings{Akutsu-NOE-threading, abstract = {We consider the protein threading problem with profiles in which constraints on distances between residues are given. Though it is known that protein threading with profiles can be solved efficiently using dynamic programming, 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). The results show that constraints are useful to improve the alignment accuracy. These 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.}, author = {Akutsu, T. and Hayashida, M. and Tomita, E. and Suzuki, J.}, booktitle = {The Fourth IEEE Symposium on Bioinformatics and Bioengineering (BIBE)}, citeulike-article-id = {531004}, citeulike-linkout-0 = {http://dx.doi.org/http://doi.ieeecomputersociety.org/10.1109/BIBE.2004.1317389}, citeulike-linkout-1 = {http://csdl.computer.org/dl/proceedings/bibe/2004/2173/00/21730537.pdf}, doi = {http://doi.ieeecomputersociety.org/10.1109/BIBE.2004.1317389}, keywords = {constrained, distance, threading}, month = {May}, pages = {537--544}, posted-at = {2006-03-05 03:45:57}, priority = {2}, title = {protein threading with profiles and constraints}, url = {http://dx.doi.org/http://doi.ieeecomputersociety.org/10.1109/BIBE.2004.1317389}, year = {2004} }

TY - CONF ID - Akutsu-NOE-threading L3 - citeulike-article-id:531004 N2 - We consider the protein threading problem with profiles in which constraints on distances between residues are given. Though it is known that protein threading with profiles can be solved efficiently using dynamic programming, 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). The results show that constraints are useful to improve the alignment accuracy. These 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. EP - 544 TI - protein threading with profiles and constraints T2 - The Fourth IEEE Symposium on Bioinformatics and Bioengineering (BIBE) SP - 537 KW - constrained KW - distance KW - threading AU - Akutsu, T AU - Hayashida, M AU - Tomita, E AU - Suzuki, J PY - 2004/05// UR - http://dx.doi.org/http://doi.ieeecomputersociety.org/10.1109/BIBE.2004.1317389 ER -