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

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.