Reconciliation ILP

Can be used to find an optimal reconciliation between a binary gene tree and a binary species tree.

Reference

Leo van Iersel, Celine Scornavacca and Steven Kelk. Exact Reconciliation of undated trees. arXiv:1410.7004 [q-bio.PE] (2014).

Installation

Download the source file "ReconciliationILP.java".

Install CPLEX, which is free for academic use, see IBM academic initiative.

(Optional) Install Graphviz.

Open a terminal window and navigate to the folder of ReconciliationILP.java.

Type "javac ReconciliationILP.java -classpath [path to cplex.jar]" to compile the source on your computer, where [path to cplex.jar] is the location of cplex.jar on your computer.

Type "java -Djava.library.path=[path to shared library] ReconciliationILP species.tree gene.tree" to run the program. Here, [path to shared library] should indicate the path to the shared library, usually the path to cplex.jar will work.

Input files

  • "species.tree" should contain a binary species tree in newick format;

  • "gene.tree" should contain a binary gene tree in newick format.

Output files

  • The program will construct a dot-file "G.dot" containing the gene tree with labelled nodes.

  • The program will construct a dot-file "S.dot" containing the species tree. Here, each node is labelled by the nodes of the gene tree that are mapped to it. In addition, blue transfer edges show where there are transfer events (T or TL events).

  • If Graphviz is installed, the program will also convert the dot-files to pdf-files.

  • The program will also construct a phylogenetic network in a file "network.txt" in e-newick format (consisting of the species tree with transfer edges added to it).

Example

For input files species.tree and gene.tree, the program generates the following files:

Options

java ReconciliationILP species.tree gene.tree [c_s c_d c_t c_sl c_tl] [--i k] [--supp]

trees.txtnewick file containing first a species tree then a gene tree
c_scost of a speciation event (default 0)
c_dcost of a duplication event (default 1)
c_tcost of a transfer event (default 1)
c_slcost of a speciation and loss event (default 0)
c_tlcost of a transfer and loss event (default 1)
--i kset maximum number of events per vertex of gene tree to k (default: height of species tree)
--suppsuppress progress of CPLEX