MAF: Maximum Agreement Forests for nonbinary trees
Implements an approximation and an FPT algorithm from this paper.
The approximation algorithm computes an agreement forest of two trees that is at most a factor 4 from optimum. This is the best known approximation algorithm that works for nonbinary (not completely resolved) trees.
The FPT algorithm computes a maximum agreement forest (MAF).
For binary trees, the program rSPR is faster and has a better approximation algorithm.
Version 1.2 (October 2012)
Download the source file "MAF.java"
Download some example input files.
Type "javac MAF.java" in a terminal window to compile the source on your computer.
(Optional) Download Graphviz to be able to see graphical respresentations of the constructed agreement forest. (Graphviz might already be installed on your computer.)
Type "java MAF trees.txt" to run the program.
For this input file, the program constructs this (optimal) maximum agreement forest.
For larger examples, see here.
Input and output files
The program will produce the following output files for the approximation algorithm:
The program will produce the following output files for the FPT algorithm:
While the algorithm is running, these files will contain the best solution found so far, unless cluster reductions have been applied.
All dot files will also be converted to pdf files if Graphviz is installed.
The input trees are not required to have identical leaf sets. Leaves that appear in only one tree will not be put in any component of the constructed agreement forests.
The FPT algorithm seems to be fast enough for trees that have, after applying cluster reductions, an agreement forest of size at most 14. For other data, the approximation algorithm can be used.
Leo van Iersel, Steven Kelk, Nela Lekić and Leen Stougie, Computing nonbinary agreement forests, arXiv:1210.3211 [math.CO] (2012).
For any questions, do not hesitate to contact: