[Bioc-devel] graph: maximum acyclic subgraph / minimum feedback edge set

Ludwig Geistlinger Ludwig.Geistlinger at bio.ifi.lmu.de
Tue May 24 15:13:03 CEST 2016


I would like to transform a directed graph with cycles, e.g. a gene
regulatory network, into a DAG. In particular, I would like to do that by
removing a minimal set of edges.

This problem is known to be NP-hard


but, apparently, several approximation algorithms for the problem have
been developed.

However, when screening e.g. through the manuals of the graph, igraph, and
ggm packages, I do not find functionality for that.

I wonder, whether developers on the mailing list, dealing with graphs and
networks, can point me to an R implementation of the desired

Thx & Best,

Dipl.-Bioinf. Ludwig Geistlinger

Lehr- und Forschungseinheit für Bioinformatik
Institut für Informatik
Ludwig-Maximilians-Universität München
Amalienstrasse 17, 2. Stock, Büro A201
80333 München

Tel.: 089-2180-4067
eMail: Ludwig.Geistlinger at bio.ifi.lmu.de

More information about the Bioc-devel mailing list