CUTTER - CUDA Technology based TransitivE Reduction of Networks
CUTTER, short for CUDA Technology based TransitivE Reduction, is a parallel CUDA implementation of unweighted and weighted transitive reduction that can be used to reduce diverse networks, e.g., biological/genetic networks. The Compute Unified Device Architecture (CUDA) is Nvidia's C-based approach to program General Purpose Graphics Processing Units (GPUs) - an example of massively parallel many-core systems available in many desktop computer systems.
Literature about Related Work
... is discussed in our paper (to appear).
More about CUDA can be found on http://www.nvidia.com/object/cuda_home.html.
Questions about CUTTER or do you want to tell us about your usage scenario? Please contact Dragan Bosnacki (mainly for biology issues) or Anton Wijs (mainly for algorithmic and implementation issues).
Source Code and Documentation
CUTTER Executable for Microsoft Windows
- CUTTER executable, tested on Windows 7. See the documentation above for the details concerning the file formats. Make sure to install the latest NVIDIA driver, CUDA toolkit, and CUDA SDK for Windows.
Data for Reduction Quality Experiments
- For these experiments, we used the five networks from the "InSilico_Size_100" subchallenge and the corresponding evaluation scripts of the DREAM 4 benchmark (freely downloadable there after registration).
- For the generation of the initial perturbation graphs from the raw data, we reused the method from Klamt et al. described in "TRANSWESD: inferring cellular networks with transitive reduction", Bioinformatics, 26:2160–2168, 2010 (online version here). They provided us with their MatLab implementation that we of course cannot publish here. If needed, please contact them directly. The parameter values used by us are theta = 0 and Gamma = 2.6.
- To compare with, we used the reduction method from Klamt et al. as also described in the above mentioned paper. Its implementation became part of their tool CellNetAnalyzer (CNA, Version 9.6, Revision 375, MatLab function "CNATranswesd", freely downloadable there). For the corresponding parameters we used epsilon = 0.95 (corresponds to the parameter called alpha from their paper), fullcheck = 0 and pathexact = 0.
- For our own transitive reduction method, we used the parameters 0.43 as lower threshold and an upper threshold of 1.0 in these experiments.
- Furthermore, in case it could be helpful for you, we provide our MatLab glue code used to perform the different steps necessary from reading the raw data to producing "submission" files for the DREAM evaluation scripts.
Data for Run Time Experiments
Experiments with scale-free graphs:
- For these experiments, we used five graphs for each of the sizes 1,000, 2,500 and 10,000 nodes and in both versions, unweighted and weighted (for weighted, we generated only one graph of size 10,000 as this took already two weeks). The unweighted graphs and the small weighted graphs used are available for download here. The bigger weighted graphs cannot be made available for download here due to space limitations. Please contact one of the authors to obtain a copy of them, if needed.
- We provide a file with all the individual results (Excel, PDF) for all runs on all graphs that led to the averages published in the paper.
- The unweighted graphs were first generated with the Scale Free Algorithm. On this basis, the weighted graphs were produced using SynTReN (freely downloadable there) which produces p-values for the graphs by simulating its dynamic behaviour.
Experiments with Erdős-Rényi graphs:
- For these experiments, we used ten graphs for each of the sizes 1,000 and 2,500 nodes in both unweighted and weighted versions. For each configuration, five of these graphs were relatively sparse, and five were dense, in order to investigate the effect of graph density on the performance of the transitive reduction algorithms. The sparse unweighted graphs, dense unweighted graphs, sparse weighted graphs, and dense weighted graphs used are available for download here.
- We provide files with all the individual runtime results for the sparse graphs (Excel, PDF) and the dense graphs (Excel, PDF).
- The unweighted graphs were first generated with the Erdős-Rényi Algorithm. On this basis, the weighted graphs were produced using SynTReN (freely downloadable there) which produces p-values for the graphs by simulating its dynamic behaviour.