On the approximation of protein threading
Tatsuya Akutsu, Satoru Miyano · 1997
In this paper, we study the protein threading problem, which was proposed for finding a folded 3D protein structure from an amino acid sequence.Since this problem was already proved to be NP-hard by Lathrop, we study polynomial time approximation algorithms.First we show that the protein threading problem is MAX SNP-hard.Next we show that the protein threading problem can be approximated within a factor 4 for a special case in which a graph representing interaction between residues (amino acids) is planar.This case corresponds to a P-sheet substructure, which appears in most protein structures.