According to this answer[0] it seems it's actually NP-Hard, my bad. Haven't seen the proof though, and I'm not an expert.

[0] https://cs.stackexchange.com/questions/128493/is-protein-fol...