论文标题
固定角度正交链的计算复杂性
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
论文作者
论文摘要
在聚合物科学，分子生物学和拼图的背景下，对固定角链和树木的平面/平面构型进行了很好的研究。在本文中，我们专注于一种简单的固定角度链接：每个边缘具有单位长度（等边），每个接头的固定角度为$ 90^\ circ $（正交）或$ 180^\ circ $（直）。当链接形成路径（开放链）时，它始终具有平面配置，即Zig-Zag，它可以在左右转弯之间交替$ 90^\ circ $ angles。但是，当连接形成一个周期（封闭链）或被迫躺在固定尺寸的盒子里时，我们证明了扁平问题（确定是否存在平面非交叉配置）是NP完整的。 回到开放的链条，我们转向蛋白质折叠的疏水 - 综合性（HP）模型，其中每个顶点都标记为H或P，目标是找到一种折叠，以最大化H-H邻接的数量。在研究良好的HP模型中，关节角度未固定。我们介绍和分析固定角度的HP模型，该模型是由现实世界蛋白激励的。我们证明，即使链子只有两个H顶点，我们也证明了找到具有最大H-H邻接的固定角度正交等边链的平面非交叉配置的强烈NP完整性。 （实际上，这使我们迫使链条被关闭。）
Planar/flat configurations of fixed-angle chains and trees are well studied in the context of polymer science, molecular biology, and puzzles. In this paper, we focus on a simple type of fixed-angle linkage: every edge has unit length (equilateral), and each joint has a fixed angle of $90^\circ$ (orthogonal) or $180^\circ$ (straight). When the linkage forms a path (open chain), it always has a planar configuration, namely the zig-zag which alternating the $90^\circ$ angles between left and right turns. But when the linkage forms a cycle (closed chain), or is forced to lie in a box of fixed size, we prove that the flattening problem -- deciding whether there is a planar noncrossing configuration -- is strongly NP-complete. Back to open chains, we turn to the Hydrophobic-Hydrophilic (HP) model of protein folding, where each vertex is labeled H or P, and the goal is to find a folding that maximizes the number of H-H adjacencies. In the well-studied HP model, the joint angles are not fixed. We introduce and analyze the fixed-angle HP model, which is motivated by real-world proteins. We prove strong NP-completeness of finding a planar noncrossing configuration of a fixed-angle orthogonal equilateral open chain with the most H--H adjacencies, even if the chain has only two H vertices. (Effectively, this lets us force the chain to be closed.)
