Software

PaNDA

Efficient Optimization of Phylogenetic Diversity in Networks.

By Niels Holtgrefe paper

SQUIRREL

Reconstructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments.

By Niels Holtgrefe paper

FHyNCH

Finding Hybridization Networks via Cherry-picking Heuristics, constructing rooted phylogenetic networks from rooted multifurcating trees with missing leaves.

By Esther Julien paper

Learn2CherryPick

Constructing rooted phylogenetic networks from any number of rooted binary trees via cherry picking and machine learning.

By Esther Julien paper

Scanwidth

Exact and heuristic algorithms for computing the scanwidth of a directed acyclic graph.

By Niels Holtgrefe paper

PhyloGNN

Solving the Tree Containment Problem Using Graph Neural Networks.

By Arkadiy Dushatskiy paper

TriLoNet

Constructing rooted level-1 phylogenetic networks from aligned DNA sequence data or trinet collections.

By James Oldman paper

TriL2Net

Constructing level-2 phylogenetic networks from trinets.

By Sjors Kole thesis paper

Finding the temporal hybridization number for sets of phylogenetic trees

Computing the temporal hybridization number for sets of phylogenetic trees.

By Sander Borst thesis paper

Computing Optimal Tree-Child Networks for Sets of Binary Phylogenetic Trees

Optimally reconstructing tree-child networks for sets of binary trees.

By Norbert Zeh paper

Treeduce

A preprocessing algorithm for hybridization number on any number of binary or nonbinary trees.

paper

The original download page is no longer online; the source file is available on request.

Compiling

With a Java compiler installed, run javac Treeduce.java in the folder containing the source.

Running

java Treeduce input.tree [k] [-s]

• input.tree — text file containing any number of trees in Newick format
• k — the value of the parameter (default is 1)
• -s — enable silent mode

The reduced trees are written in Newick format to a file called reduced.tree.

NonbinaryCycleKiller

A practical algorithm for constructing a phylogenetic network from two large (possibly multifurcating) trees.

paper

The original download page is no longer online; the source file is available on request.

Constructs a network displaying (refinements of) both input trees, aiming to minimise the reticulation number. Extends the original CycleKiller, which handled only binary trees.

Requirements

• A Java compiler.
• CPLEX — free for academic use.
• Optional: Dendroscope, to view the constructed networks.
• Optional: rSPR, only needed for the --rspr and --rsprapp options.

Compiling and running

javac -classpath jarpath NonbinaryCycleKiller.java

java -classpath jarpath;. -Djava.library.path=libpath NonbinaryCycleKiller test.tree

• test.tree — text file containing two trees in Newick format, one per line
• jarpath — path to cplex.jar
• libpath — path to the CPLEX shared library (often unnecessary)

The network is saved in e-Newick format to test-network.tree, which opens in Dendroscope.

Options

• --maf — FPT algorithm of MAF for the initial agreement forest (default)
• --mafapp — approximation algorithm of MAF
• --rspr / --rsprapp — FPT / approximation algorithm of rSPR (requires at least one binary input tree)
• --given af.txt — use the initial agreement forest in af.txt

The approximation algorithms are much faster than the FPT ones, though their worst-case guarantees are weaker. Worst-case approximation ratios:

	binary inputs	one binary, one nonbinary	nonbinary inputs
--maf	2	4	4
--mafapp	5	7	7
--rspr	2	4	N/A
--rsprapp	4	6	N/A

In practice the ratios are much smaller on essentially all data.

Additional functionality

Given an acyclic agreement forest, java NonbinaryCycleKiller trees.tree --given aaf.txt outputs a network displaying both trees and corresponding to that forest. The program can also find a directed feedback vertex set of a digraph via java NonbinaryCycleKiller outlists.txt --dfvs, where vertices are numbered 0…n-1 and line i lists the out-neighbours of vertex i-1, separated by spaces.

ILPEACE

Reconciling a binary gene tree with a binary undated species tree.

paper

The original download page is no longer online; the source file is available on request.

Finds an optimal reconciliation between a binary gene tree and a binary species tree.

Requirements

• CPLEX — free for academic use.
• Optional: Graphviz, to render the output.

Compiling and running

javac ReconciliationILP.java -classpath [path to cplex.jar]

java -Djava.library.path=[path to shared library] ReconciliationILP species.tree gene.tree

species.tree and gene.tree each contain one binary tree in Newick format.

Output

• G.dot — the gene tree with labelled nodes.
• S.dot — the species tree, each node labelled by the gene-tree nodes mapped to it; blue edges mark transfer (T or TL) events.
• network.txt — the species tree with transfer edges added, in e-Newick format.

With Graphviz installed, the dot-files are also converted to PDF.

MPNet

Computing the maximum parsimony score of a phylogenetic network.

paper

The original download page is no longer online; the source files are available on request.

Computes the softwired and hardwired parsimony score of a phylogenetic network using integer linear programming. Two versions exist: a CPLEX version (recommended, much faster, free for academic use) and a GLPK version (free, but considerably slower).

CPLEX version

Install CPLEX, then:

javac MPNet.java -classpath [path to cplex.jar]

java -Djava.library.path=[path to shared library] MPNet network.tree sequences.fasta

GLPK version

Download GLPK and place glpsol (on Windows, glpsol.exe plus the DLLs from its directory) in the folder containing MPNetGLPK.java, then:

javac MPNetGLPK.java

java MPNetGLPK network.tree sequences.fasta

Input

• network.tree — a network in e-Newick format.
• sequences.fasta — one taxon per line: a name, a space, then a character state or sequence of states. - and ? indicate gaps.

Output

Dot-files containing the networks with assigned character states, converted to PDF if Graphviz is installed. Labels on reticulation edges give the support for that edge.

Options

• --nolabels / --nostates — hide taxon labels / character states
• --softwired / --hardwired — compute only that score
• --silent — suppress intermediate results
• --rand k — randomly generate a single k-state character instead of reading a sequence file

Edge-support values roughly indicate the fraction of the genome inherited over that edge. For a reticulation edge e=(u,r), let s(u) be the number of characters for which u is the only parent of r sharing its state; the support of e is s(u) divided by the sum of s(p) over all parents p of r. Supports of all reticulation edges at a reticulation therefore sum to 1 unless all are 0, and a support is 0 exactly when the edge can be removed without increasing the parsimony score.

MAF

Maximum agreement forests for nonbinary trees.

paper

Version 1.2 (October 2012). The original download page is no longer online; the source file is available on request.

Implements both an approximation and an FPT algorithm. The approximation algorithm computes an agreement forest of two trees within a factor 4 of optimal — the best known guarantee that also works for nonbinary (not fully resolved) trees. The FPT algorithm computes a maximum agreement forest exactly. For binary trees, rSPR is faster and has a better approximation algorithm.

Compiling and running

javac MAF.java, then java MAF trees.txt, where trees.txt contains two trees in Newick format.

Optionally install Graphviz to view graphical representations of the constructed agreement forest.

CycleKiller

A practical algorithm for constructing a phylogenetic network from two large bifurcating trees.

By Steven Kelk paper

Cass

Combines any set of phylogenetic trees into a phylogenetic network representing all clusters of all input trees.

paper · Integrated into Dendroscope

LEV1ATHAN

A practical algorithm for reconstructing level-1 phylogenetic networks from triplet topologies.

By Steven Kelk paper

SIMPLISTIC

Constructs level-k phylogenetic networks from triplets and returns a network consistent with all input triplets.

By Steven Kelk paper

MARLON

Constructs a level-1 phylogenetic network with a minimum number of reticulations consistent with a dense set of triplets.

By Steven Kelk paper

LEVEL2

Constructs a level-2 phylogenetic network consistent with a dense set of triplets.

By Steven Kelk paper

Cass, Simplistic, and various other phylogenetic network methods are also available in the user-friendly software package Dendroscope.