What is GEDEVO?GEDEVO, is a software tool for solving the network alignment problem. GEDEVO stands for Graph Edit Distance + EVOlution and it utilizes the evolutionary computing strategies for solving the so-called Graph Edit Distance problem (see also GEDEVO-M)
What is Network Alignment?
|Network Alignment is a computationally hard bioinformatic problem. It aims to find the "best" one-to-one correspondence between nodes from two input networks without using any external knowledge, such as sequence similarity. In GEDEVO the "best" alignment is the one, which has the lowest graph editing cost. Applied to Protein-Protein Interaction (PPI) networks, Network Alignment, finds its applications in the validation of interactions and the prediction of new ones, as well as for extracting conserved subnetworks in a set of given PPI networks. Network Alignment is a novel basis, in addition to DNA and amino acid sequence similarity, for further interspecies network analysis in drug development, including (functional) knowledge transfer between species.|
Illustration of GED
Transforming graph G1 graph into G2
delete edge e1 delete node n1
delete edge e2 insert edge e4
insert node n2 insert edge e3.
Cost of edit operations:
deletion/insertion of edges/nodes – 1,
substitution of nodes/edges – 0.
DownloadHere are the links to download GEDEVO:
source code repo (for GEDEVO and NABEECO; available from April, 2014)
How to run GEDEVO
- Start ./gedevo (or gedevo.exe for Windows) with no parameters for a short description of the command line parameters.
- See also example.sh for an example of GEDEVO with set parameters.
- GEDEVO accepts networks in .ntw and .sif formats (See README file for details).
- Command line example:
./gedevo --save example_out --no-save --groups mCMV EBV --ntw data/mCMV.ntw --ntw data/EBV.ntw --grsig data/mCMV.sigs mCMV --grsig data/EBV.sigs EBV --pop 200 --maxsame 300 --no-prematch --no-workfiles --undirected
CitationRashid Ibragimov, Maximilian Malek, Jiong Guo, Jan Baumbach: GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment. GCB 2013:68-79
Other network alignment tools
- GEDEVO-M (extension of GEDEVO approach to multiple network alignment)