LEVEL2: A fast algorithm for constructing level-2 phylogenetic networks from dense sets of rooted triplets

Introduction

LEVEL2 is an implementation in Java of the algorithm of Leo van Iersel, Judith Keijsper, Steven Kelk and Leen Stougie which constructs level-2 phylogenetic networks from rooted triplets. The code was written, and is maintained, by Steven Kelk.

Latest version

NOTE: As of January 28th 2009 the latest release of LEVEL2 will be available from Sourceforge under a GNU Public Licence. Please follow this link for the most recent release. There you can download the Java source and all the most recent documentation and examples.

How to run the algorithm

The following instructions assume a UNIX environment. There are no fundamental reasons however why the algorithm will not work under another operating system environment as long as Java and the graph drawing package DOT are available in that environment. (Please contact Steven Kelk if you are interested in an output format for a package other than DOT.)

1. It is advisable that you first compile Level2.java on your own computer, using the Java compiler javac. This will create a file Level2.class in the directory.
2. Ensure that the file lev2lookup.txt is in the same directory as your Level2.class file. This file is read by LEVEL2 at the initialisation phase, the algorithm cannot function without it.
3. Create a file of triplet data. LEVEL2 assumes that the species are numbered 1 through n and that there are no missing species. Some examples of triplet data files can be found below.
4. Run the algorithm with and direct the output to a file. For example, with the command java Level2 yourtripletdat.txt > output
5. If the algorithm could not find a level-0, level-1 or level-2 network for those triplets, this will be reported in the output file. Otherwise, the file output can be fed into the graph drawing package DOT, which in turn can produce images in various formats. For example, to get DOT to produce a postscript file from your data, try dot -Tps < output > mynetwork.ps. Other output formats are possible by adjusting the -T switch.
6. The code is still in development. If for some reason you encounter a bug or a problem, please inform the author! At the moment internal error reporting is minimal, many error messages simply report an error and an error number, this will be improved in future versions.

The "yeast" dataset

From real yeast data, obtained from the Fungal Biodiversity Center in Utrecht (Netherlands), the following triplets were generated, producing the following 21-leaf level-2 network (scalable EPS version is here.) Biological analysis of this data will appear in a future publication.

Other examples

Some more examples can be found in this directory. Note that the networks generated by LEVEL2 are always planar, but that sometimes DOT will draw the network in non-planar fashion. This is something which will hopefully be addressed in a future version.

Miscellaneous

For a detailed analysis of the algorithm, please consult our article. For a summary of the algorithm see the following powerpoint presentation (summer 2007).