Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Sign Assignment Problems on Protein Networks
verfasst von : Shay Houri, Roded Sharan
Erschienen in: Algorithms in Bioinformatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In a maximum sign assignment problem one is given an undirected graph and a set of signed source-target vertex pairs. The goal is to assign signs to the graph’s edges so that a maximum number of pairs admit a source-to-target path whose aggregate sign (product of its edge signs) equals the pair’s sign. This problem arises in the annotation of physical interaction networks with activation/repression signs. It is known to be NP-complete and most previous approaches to tackle it were limited to considering very short paths in the network. Here we provide a sign assignment algorithm that solves the problem to optimality by reformulating it as an integer program. We apply our algorithm to sign physical interactions in yeast and measure our performance using edges whose activation/repression signs are known. We find that our algorithm achieves high accuracy (89%), outperforming a state-of-the-art method by a significant margin.