uDance version 1.6.5

https://github.com/balabanmetin/uDance-data

uDance is highly-scalable end-to-end workflow for inferring phylogenomic trees or updating existing ones. The input to uDance is a backbone tree, a set of DNA xor amino-acid multiple sequence alignments (MSAs) of backbone sequences, and new (query) sequences. Alternatively, when a backbone tree is not available, uDance can select a set of backbone species with high diversity to reconstruct a backbone tree. At a high level, uDance inserts the query sequences on the backbone tree independently and then refines the tree locally in different parts. The backbone is allowed to change based on the new information provided by the query sequences, but uDance also outputs an incremental tree with the backbone relationships fixed for users that require consistency between updates in their analyses. Since uDance aims for automatic analyses of large data, it has many built-in quality control and filtering strategies; it may decide a set of query sequences cannot be confidently put in the output tree (i.e., are unplacable) and some backbones need to be removed. When more sequences become available, the output from the previous iteration can be used as the input in the next iteration to incrementally grow the tree.

• Linux or OS X Intel (OS X Apple chip is not supported because some dependencies does not support this architecture)
• Anaconda

1. Clone the repository
2. cd uDance
3. bash install.sh
4. conda activate udance

• Pull docker image.
  docker pull niemasd/udance:latest
• Run docker image.
  docker run -it --rm -v $PWD:/uDance/udance_test -w /uDance niemasd/udance:latest
  This command will mount the current directory to /uDance/udance_test in the container and set the working directory as /uDance.

You can run uDance on the test dataset with 10 gene multiple sequence alignments, 99 backbone sequences, and 146 query sequences using the following command. The command should complete in several minutes using 4 CPU cores:

snakemake -c 4 --configfile config.yaml --snakefile udance.smk all

The specification of the run is defined in the config file config.yaml. In the config.yaml, the working directory is specified using the field workdir. Input multiple sequence alignments should be located under <workdir>/alignments. For example, for the test dataset, the working directory is datasmall and the input alignments are located at datasmall/alignments.

If there is an input backbone tree as well, it should be locate it at <workdir>/backbone.nwk and backbone field in the config file should be set to "tree".

uDance workflow is implemented using Snakemake. Below is the diagram of the rule graph showing the relationship between each stage in the workflow.

Brief summary of each rule:

Note that genetreeinfer and refine rules is used in two separate parts of the workflow: once to obtain the backbone tree (de-novo) and once on every the partition created after phylogenetic placement.

uDance writes its output under the directory <workdir>/output. The workflow outputs three phylogenies: <workdir>/output/udance.maxqs.nwk, <workdir>/output/udance.incremental.nwk, and <workdir>/output/udance.updates.nwk. incremental tree guarantees that the backbone topology is fixed in the output tree. maxqs tree is the "best" one inferred by uDance and the location of backbone sequences might change after insertion of query sequences. We will shortly come back to the exact definition of these three output trees.

uDance workflow also outputs many intermediate files. These intermediate files can be useful for user for debugging as well as to supplement the downstream analysis. All paths below are given in relative to the output directory <workdir>/output.

1. trimmed containes trimmed input MSAs.
2. backbone.nwk is the backbone file. If there is an input backbone tree, it's identical to the input backbone tree. Otherwise, backbone sequences are selected using Mainlines algorithm and selected sequence IDs are written to backbone/0/species.txt. Gene trees for the selected sequences are found in the directory backbone/0/<gene>. This directory contains subdirectories named 1 to k, where k is the number of starting trees for the inference of the gene tree for this gene. backbone/0/<gene>/<i>/shrunk.fasta.treefile is the inferred maximum likelihood tree for the gene using the starting tree i. The highest likelihood tree among all k starts is backbone/0/<gene>/bestTree.nwk and relative-path to the starting tree that yielded the highest likelihood is backbone/0/<gene>/bestTreename.txt. All gene trees in newick format are written to backbone/0/astral_input.trees, one line per tree. This file is provided to ASTRAL as the input. No constraint tree is used during the estimation of the backbone tree. ASTRAL's output file (a newick tree) is backbone/0/astral_output.updates.nwk.
3. placement contains the backbone and query alignments and the backbone tree used at the placement stage. placement.jplace is the jplace file output by APPLES-2.
4. The partitions created by uDance are located under the directory udance. This directory contains subdirectories named 0 to p-1, where p is the number of partitions designated for the uDance run. atasmall/output/udance/<partition>/species.txt contains the list of backbone, query, and outgroup sequences in the partition. The organization of the partition is almost identical to the "partition" backbone/0 given in the item 2 above but there are a few differences. datasmall/output/udance/<partition>/astral_constraint.nwk and datasmall/output/udance/<partition>/raxml_constraint.nwk are the two kinds of constraint trees used in ASTRAL stage. The former results in an ASTRAL tree (datasmall/output/udance/<partition>/astral_output.incremental.nwk) that retains the backbone tree topology and the latter allows topological changes aming the backbone sequences (datasmall/output/udance/<partition>/astral_output.updates.nwk).
5. (continued) The spanning tree of partitions of the placement tree is available at datasmall/output/udance/color_spanning_tree.nwk. This can be regarded as the hierarchy or relative positions of the partitions. datasmall/output/udance/outgroup_map.json is a dictionary where, for each partition, we list the outgroup sequences (stored in keys children and up). These two files are used during stitching ASTRAL output trees of the partitions.

Metin Balaban

Yueyu Jiang

Niema Moshiri

1.6.5

• Dockerfile added

• Bug fix for raxml-ng gene tree inference. raxml-ng (v1.2.1) should work now

1.6.4

• Do not transfer branch supports after ASTRAL branch length estimation

• Important bug fix. Now uDance allows using IQTREE-2 for gene tree topology inference

1.6.3

• Cluster size can be automatically set

• Bug fix

1.6.2

• Backbone filtering can be turned on or off

1.6.1

• Benchmarks directives are used in udance.smk

1.6.0

• Skip a partition (return backbone) if the number of placements is it less than a desired number

• Bug fixes

1.5.1:

• Output tree may have branch lengths in substitution unit if desired.

1.5.0:

• uDance uses ASTRAL version 5.17.2, which supports both multithreading and constrained search.

1.4.1:

• Performance improvements in placement_prep

• Keep placement_prep intermediate files.

1.4.0:

• Stitching algorithm outputs a new tree named maxqs which picks the best one of the two ASTRAL trees for each partition.

1.3.3:

• Default decompose edge threshold changed

• Bug fixes

• Large cluster pruning strategy is changed to serial search (instead of binary)

1.3.2:

• Expose backbone selection strategy to the user

• Expose gene tree filtering parameters at refine stage to the user

1.3.1:

• Getting rid of pruning thresholds (automated finding)

1.3.0:

• Pruning Large partitions

• Changes in TreeCluster logic disallowing formation of very small partitions

1.2.1:

• APPLES2 excludes sequences that are placed on internal nodes.

• Filtered backbone sequences are no longer added to the query set.

• Set min_placements: 9999999 to only filter out low quality backbone sequences and return.

• Set config["mainlines_config"]["n"] to number of species in the dataset and config["backbone"] to "de-novo". Then run snakemake with target {outdir}/backbone.nwk. This will do species tree inference without divide and conquer.