A Software for Computing rSPR Distance Exactly or Approximately

A Software for Computing rSPR Distance and Hybridization Number Exactly or Approximately

The program and datasets in a single ZIP archive.

The ZIP archive contains a jar file named "rsprHN.jar" and a folder named "dataset". The dataset folder contains 18 subfolders each of which contains 20 text files. Each of the text files contains a pair of phylogenies with the same set of labeled leaves.
To run the programs, you should download the ZIP archieve, unzip it, go to the folder containing the jar file, and then type the following command in a terminal window:
java -jar -Djava.library.path=Path_to_Cplex_Library solver.jar [-Main_Option] [-Sub_Option] fileInNewickFormat
where Main_Option is a string in the set {rSPR, HN} , Sub_Option is a string in the set {single, single2, app1, app2, app3, app4} , and fileInNewickFormat contains two binary phylogenetic trees in Newick format such as (((1,4),3),2) and (((species1, species_3), cat),dog) ended with a semicolon. The name of each species must not contain: comma, parenthesis, or semicolon. There is no limit on the length of the name of each species.
Either rSPR or HN should be chosen as the main option: rSPR is for computing rSPR distance, while HN is for computing hybridization number. If the main options is rSPR, then it is unnecessary to specify java.library.path.
If no sub-option is given, then the program will use all available threads on your machine to compute the desired value specified by the main option exactly. On the other hand, if a sub-option is given, then the program does the following (depending on the sub-option):
- single: This sub-option forces the program to use a single thread to compute the desired value specified by the main option exactly, although CPLEX may use multiple threads.
- single2: This sub-option forces the program to use a single thread to compute the desired value specified by the main option exactly; CPLEX is also forced to use a single thread.
- app1: This sub-option forces the program to compute the desired value specified by the main option approximately, where our 2-approximation algorithm for rSPR distance is used as a subroutine.
- app2: This sub-option forces the program to compute the desired value specified by the main option approximately, where our 7/3-approximation algorithm for rSPR distance is used as a subroutine.
- app3: This sub-option forces the program to use our MCTS-based algorithm to compute the desired value specified by the main option approximately, where our 2-approximation algorithm for rSPR distance is used in the simulation step.
- app4: This sub-option forces the program to use our MCTS-based algorithm to compute the desired value specified by the main option approximately, where our 7/3-approximation algorithm for rSPR distance is used in the simulation step.

Example: You can either approximately or exactly compute the rSPR distance and hybridization number of the two phylogenies in the text file "1.txt" in the first subfolder of the dataset folder, as follows:

To compute the hybridization number exactly, please type the following command:
java -jar -Djava.library.path=Path_to_Cplex_Library solver.jar -HN -single dataset/1/1.txt
The above command will output several lines, where the last two lines show the hybridization number and the running time, respectively. On our machine used in the experiments, Path_to_Cplex_Library was /opt/ibm/ILOG/CPLEX_Studio1271/cplex/bin/x86-64_linux
To compute the hybridization number approximately, please type the following command:
java -jar -Djava.library.path=Path_to_Cplex_Library solver.jar -HN -app3 dataset/1/1.txt
The above command will output several lines, where the last two lines show the approximate hybridization number and the running time, respectively.
To compute the rSPR distance exactly via possibly multiple threads, please type the following command:
java -jar solver.jar -rSPR dataset/1/1.txt
The above command will output several lines, where the last two lines show the rSPR distance and the running time, respectively.
To compute the rSPR distance approximately, please type the following command:
java -jar solver.jar -rSPR -app3 dataset/1/1.txt
The above command will output several lines, where the last two lines show the approximate rSPR distance and the running time, respectively.