La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Bicolored Path Embedding Problems Inspired by Protein Folding Models Problèmes d'intégration de chemins bicolores inspirés des modèles de repliement de protéines

Tianfeng FENG, Ryuhei UEHARA, Giovanni VIGLIETTA

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.623-633
Date de publication
2022/03/01
Publicisé
2021/12/07
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2021EDP7206
Type de manuscrit
PAPER
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

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)

Mots-clés

Table des matières