Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.12.2019 | Original Article | Ausgabe 1/2019

Network Modeling Analysis in Health Informatics and Bioinformatics 1/2019

On the parameterized complexity of the problem of inferring protein–protein interaction directions based on cause–effect pairs

Zeitschrift:
Network Modeling Analysis in Health Informatics and Bioinformatics > Ausgabe 1/2019
Autor:
Mehdy Roayaei

Abstract

We consider the following problem: given an undirected (mixed) network and a set of ordered source–target pairs, or cause–effect pairs, direct all edges so as to maximize the number of pairs that admit a directed source–target path. This is called the maximum graph orientation problem, and has applications in understanding interactions in protein–protein interaction networks. Since this problem is NP-hard, we take the parameterized complexity viewpoint and study the parameterized (in)tractability of the problem with respect to various parameters on both undirected and mixed networks. In the undirected case, we determine the parameterized complexity of the problem (for non-fixed and fixed paths) with respect to the number of satisfied pairs. Also, we present an exact algorithm which outperforms the previous algorithms on trees with bounded number of leaves. In the mixed case, we present polynomial-time algorithms for the problem on paths and cycles, and an FPT algorithm with respect to the combined parameter number of arcs and number of pairs on general graphs.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe​​​​​​​




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2019

Network Modeling Analysis in Health Informatics and Bioinformatics 1/2019 Zur Ausgabe

Premium Partner

    Bildnachweise