THE PROTEIN THREADING PROBLEM WITH SEQUENCE AMINO-ACID INTERACTION PREFERENCES IS NP-COMPLETE

Authors
Citation
Rh. Lathrop, THE PROTEIN THREADING PROBLEM WITH SEQUENCE AMINO-ACID INTERACTION PREFERENCES IS NP-COMPLETE, Protein engineering, 7(9), 1994, pp. 1059-1068
Citations number
38
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Biology
Journal title
ISSN journal
0269-2139
Volume
7
Issue
9
Year of publication
1994
Pages
1059 - 1068
Database
ISI
SICI code
0269-2139(1994)7:9<1059:TPTPWS>2.0.ZU;2-U
Abstract
In recent protein structure prediction research there has been a great deal of interest in using amino acid interaction preferences (e.g. co ntact potentials or potentials of mean force) to align ('thread') a pr otein sequence to a known structural motif. An important open question is whether a polynomial time algorithm for finding the globally optim al threading is possible. We identify the two critical conditions gove rning this question: (i) variable-length gaps are admitted into the al ignment, and (ii) interactions between amino acids from the sequence a re admitted into the score function. We prove that if both these condi tions are allowed then the protein threading decision problem (does th ere exist a threading with a score less than or equal to K?) is NP-com plete (in the strong sense, i.e. is not merely a number problem) and t he related problem of finding the globally optimal protein threading i s NP-hard. Therefore, no polynomial time algorithm is possible (unless P = NP). This result augments existing proofs that the direct protein folding problem is NP-complete by providing the corresponding proof f or the 'inverse' protein folding problem. It provides a theoretical ba sis for understanding algorithms currently in use and indicates that c omputational strategies from other NP-complete problems may be useful for predictive algorithms.