Bicolored Path Embedding Problems Inspired by Protein Folding Models

• FENG Tianfeng

  School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)

• UEHARA Ryuhei

  School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)

• VIGLIETTA Giovanni

  School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)

Abstract

In this paper, we introduce a path embedding problem inspired by the well-known hydrophobic-polar (HP) model of protein folding. A graph is said bicolored if each vertex is assigned a label in the set {red, blue}. For a given bicolored path P and a given bicolored graph G, our problem asks whether we can embed P into G in such a way as to match the colors of the vertices. In our model, G represents a protein's “blueprint,” and P is an amino acid sequence that has to be folded to form (part of) G. We first show that the bicolored path embedding problem is NP-complete even if G is a rectangular grid (a typical scenario in protein folding models) and P and G have the same number of vertices. By contrast, we prove that the problem becomes tractable if the height of the rectangular grid G is constant, even if the length of P is independent of G. Our proof is constructive: we give a polynomial-time algorithm that computes an embedding (or reports that no embedding exists), which implies that the problem is in XP when parameterized according to the height of G. Additionally, we show that the problem of embedding P into a rectangular grid G in such a way as to maximize the number of red-red contacts is NP-hard. (This problem is directly inspired by the HP model of protein folding; it was previously known to be NP-hard if G is not given, and P can be embedded in any way on a grid.) Finally, we show that, given a bicolored graph G, the problem of constructing a path P that embeds in G maximizing red-red contacts is Poly-APX-hard.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E105.D (3), 623-633, 2022-03-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• bicolored grid graph
• embedding problem
• HP (hydrophobic-polar) model
• Hamiltonian path problem
• protein folding problem

Details

• CRID: 1390291767485371776
• NII Article ID: 130008165624
• DOI: 10.1587/transinf.2021edp7206
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E105.D/3/E105.D_2021EDP7206/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed