Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4553
Main Title: Exploiting bounded signal flow for graph orientation based on cause–effect pairs
Author(s): Dorn, Britta
Hüffner, Falk
Krüger, Dominikus
Niedermeier, Rolf
Uhlmann, Johannes
Type: Article
Language: English
Language Code: en
Abstract: Background: We consider the following problem: Given an undirected network and a set of sender–receiver pairs, direct all edges such that the maximum number of "signal flows" defined by the pairs can be routed respecting edge directions. This problem has applications in understanding protein interaction based cell regulation mechanisms. Since this problem is NP-hard, research so far concentrated on polynomial-time approximation algorithms and tractable special cases. Results: We take the viewpoint of parameterized algorithmics and examine several parameters related to the maximum signal flow over vertices or edges. We provide several fixed-parameter tractability results, and in one case a sharp complexity dichotomy between a linear-time solvable case and a slightly more general NP-hard case. We examine the value of these parameters for several real-world network instances. Conclusions: Several biologically relevant special cases of the NP-hard problem can be solved to optimality. In this way, parameterized analysis yields both deeper insight into the computational complexity and practical solving strategies.
URI: urn:nbn:de:kobv:83-opus4-68778
http://depositonce.tu-berlin.de/handle/11303/4850
http://dx.doi.org/10.14279/depositonce-4553
Issue Date: 2011
Date Available: 20-Jul-2015
DDC Class: 570 Biowissenschaften; Biologie
Subject(s): Cell regulation
Maximum tree orientation
MTO
Protein-protein interaction
W-MTO
Weighted maximum tree orientation
Creative Commons License: https://creativecommons.org/licenses/by/2.0/
Journal Title: Algorithms for Molecular Biology
Publisher: BioMed Central
Publisher Place: London
Volume: 6
Article Number: 21
Publisher DOI: 10.1186/1748-7188-6-21
Notes: First published by BioMed Central Dorn, Britta ; Hüffner, Falk ; Krüger, Dominikus ; Niedermeier, Rolf ; Uhlmann, Johannes : Exploiting bounded signal flow for graph orientation based on cause–effect pairs. - In: Algorithms for Molecular Biology. - ISSN 1748-7188 (online). -6 (2011), art. 21. -doi:10.1186/1748-7188-6-21.
Appears in Collections:Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
dorn_etal.pdf1.35 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons