Protein threading with profiles and constraints
Authors:
- E. TomitaETE. Tomita
- J. SuzukiJSJ. Suzuki
- 30 November 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 537-544
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.Keywords
This publication has 18 references indexed in Scilit:
- An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique2003
- RAPTOR: OPTIMAL PROTEIN THREADING BY LINEAR PROGRAMMINGJournal of Bioinformatics and Computational Biology, 2003
- Clique is hard to approximate within n/sup 1-ε/2002
- The longest common subsequence problem for sequences with nested arc annotationsJournal of Computer and System Sciences, 2002
- A General Edit Distance between RNA StructuresJournal of Computational Biology, 2002
- A Computational Method for NMR-Constrained Protein ThreadingJournal of Computational Biology, 2000
- High throughput protein fold identification by using experimental constraints derived from intramolecular cross-links and mass spectrometryProceedings of the National Academy of Sciences, 2000
- The Longest Common Subsequence Problem for Arc-Annotated Sequences2000
- Global Optimum Protein Threading with Gapped Alignment and Empirical Pair Score FunctionsJournal of Molecular Biology, 1996
- The protein threading problem with sequence amino acid interaction preferences is NP-completeProtein Engineering, Design and Selection, 1994