将蛋白质链拟合到立方晶格是NP完全问题。

Fitting protein chains to cubic lattice is NP-complete.

作者信息

Manuch Ján, Gaur Daya Ram

机构信息

School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada.

出版信息

J Bioinform Comput Biol. 2008 Feb;6(1):93-106. doi: 10.1142/s0219720008003308.

DOI:10.1142/s0219720008003308

PMID:18324748

Abstract

It is known that folding a protein chain into a cubic lattice is an NP-complete problem. We consider a seemingly easier problem: given a three-dimensional (3D) fold of a protein chain (coordinates of its C(alpha) atoms), we want to find the closest lattice approximation of this fold. This problem has been studied under names such as "lattice approximation of a protein chain", "the protein chain fitting problem", and "building of protein lattice models". We show that this problem is NP-complete for the cubic lattice with side close to 3.8 A and coordinate root mean square deviation.

摘要

已知将蛋白质链折叠成立方晶格是一个NP完全问题。我们考虑一个看似更简单的问题：给定一条蛋白质链的三维（3D）折叠结构（其Cα原子的坐标），我们想要找到该折叠结构最接近的晶格近似。这个问题已经在诸如“蛋白质链的晶格近似”、“蛋白质链拟合问题”以及“蛋白质晶格模型构建”等名称下进行了研究。我们表明，对于边长接近3.8埃且坐标均方根偏差的立方晶格，这个问题是NP完全的。