The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans cet article, nous introduisons un problème d’intégration de chemin inspiré du modèle hydrophobe-polaire (HP) bien connu du repliement des protéines. Un graphique est dit bicolore si chaque sommet se voit attribuer une étiquette dans l'ensemble {rouge, bleu}. Pour un chemin bicolore donné P et un graphique bicolore donné G, notre problème demande si nous pouvons intégrer P développement G de manière à correspondre aux couleurs des sommets. Dans notre modèle, G représente le « plan » d'une protéine, et P est une séquence d'acides aminés qui doit être pliée pour former (une partie de) G. Nous montrons d’abord que le problème d’incorporation de chemins bicolores est NP-complet même si G est une grille rectangulaire (un scénario typique dans les modèles de repliement de protéines) et P et G ont le même nombre de sommets. En revanche, nous prouvons que le problème devient résoluble si la hauteur de la grille rectangulaire G est constante, même si la longueur de P est indépendant de G. Notre preuve est constructive : nous donnons un algorithme en temps polynomial qui calcule un plongement (ou signale qu'aucun plongement n'existe), ce qui implique que le problème est dans XP lorsqu'il est paramétré en fonction de la hauteur de G. De plus, nous montrons que le problème de l’intégration P dans une grille rectangulaire G de manière à maximiser le nombre de contacts rouge-rouge est NP-difficile. (Ce problème est directement inspiré du modèle HP de repliement des protéines ; il était auparavant connu pour être NP-difficile si G n'est pas donné, et P peut être intégré de n'importe quelle manière sur une grille.) Enfin, nous montrons que, étant donné un graphe bicolore G, le problème de la construction d'un chemin P qui s'intègre dans G maximiser les contacts rouge-rouge est Poly-APX-hard.
Tianfeng FENG
Japan Advanced Institute of Science and Technology (JAIST)
Ryuhei UEHARA
Japan Advanced Institute of Science and Technology (JAIST)
Giovanni VIGLIETTA
Japan Advanced Institute of Science and Technology (JAIST)
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Tianfeng FENG, Ryuhei UEHARA, Giovanni VIGLIETTA, "Bicolored Path Embedding Problems Inspired by Protein Folding Models" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 623-633, March 2022, doi: 10.1587/transinf.2021EDP7206.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7206/_p
Copier
@ARTICLE{e105-d_3_623,
author={Tianfeng FENG, Ryuhei UEHARA, Giovanni VIGLIETTA, },
journal={IEICE TRANSACTIONS on Information},
title={Bicolored Path Embedding Problems Inspired by Protein Folding Models},
year={2022},
volume={E105-D},
number={3},
pages={623-633},
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.},
keywords={},
doi={10.1587/transinf.2021EDP7206},
ISSN={1745-1361},
month={March},}
Copier
TY - JOUR
TI - Bicolored Path Embedding Problems Inspired by Protein Folding Models
T2 - IEICE TRANSACTIONS on Information
SP - 623
EP - 633
AU - Tianfeng FENG
AU - Ryuhei UEHARA
AU - Giovanni VIGLIETTA
PY - 2022
DO - 10.1587/transinf.2021EDP7206
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - 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.
ER -