Code for Maximum Agreement Forest

Here, you can find a Python implementation of the algorithm described in the paper "A Duality-Based 2-Approximation Algorithm for Maximum Agreement Forest" by Neil Olver, Frans Schalekamp, Leen Stougie and Anke van Zuylen.

The code can be downloaded from here. Python 3 and the ETE Toolkit library are required.

Instead of downloading the code and installing all the required dependencies, you can also explore the code using a prepared online Jupyter notebook. Here you can run the algorithm step-by-step and see what it does, all within your browser and without installing anything. The notebook is available here. Note: your browser is likely to give warnings/errors due to a self-signed SSL certificate. You may need to allow a security exception in order to open the notebook.

An implementation of an older version of the algorithm (corresponding to the ICALP 2006 paper of Schalekamp, Van Zuylen and Van der Ster) written in Java can be found here.

An implementation of the compact LP formulation described in the paper, written in Java, can be found here. A python implementation will be added at a later date.