witch-msa 1.0.10

News

• (NEW, v1.0.8) Supported reading gzipped backbone alignment files. E.g., -b backbone.fasta.gz.

• Added new parameter option to allow users to specify a customized config file to override main.config. Use -c <user config file>. An example can be found at examples/user.config. For example usage please see Scenario E.

• Now support PyPI installation! Please install the latest release with pip install witch-msa.

Method Overview

WITCH is a new multiple sequence alignment (MSA) tool that combines techniques from UPP and MAGUS. It aims to solve alignment problems, particularly when input sequences contain fragments. The whole pipeline can be described as follows:

1. Given a set of unaligned sequences S, pick at most 1,000 “full-length” sequences to form a backbone alignment B and a backbone tree T (Full-length sequences refer to sequences of lengths that are within 25% of the median length).

2. Create an ensemble of HMMs (eHMM, see UPP for more details) from B and T.

3. For each remaining unaligned sequence, align it to high-ranked HMMs to obtain a set of weighted support alignments; then, merge the support alignments using Graph Clustering Merger (GCM, an alignment merger technique introduced in MAGUS).

4. Transitively add the merged alignment of each query to B, and report the final alignment on S.

For a more detailed explanation of the WITCH algorithm, please refer to the publication below:

(Important) Software Output Explanation

By default, WITCH will write two alignment files to the output directory:

1. <name>.fasta: The final alignment with the original input sequences. In this file, some columns may contain lowercase letters, representing “insertions” that do not have any homologous pairs. They are compressed to neighbor columns to save space, so that you may see lowercase letters from different rows appear in the same column–They should not be considered aligned!!

2. <name>.masked.fasta: The final alignment with the lowercase letters removed (i.e., sequences can be different from their inputs). This file is useful for any downstream biological analyses that rely on homologous pairs, such as phylogenetic tree estimation, phylogenetic placement, etc.

Additionally, WITCH will write logs to the following files:

1. <outdir>/log.txt: Main log output file.

2. <outdir>/debug.txt: Record command usage.

3. <outdir>/error.txt: Record runtime errors. Only when errors occurred.

4. <outdir>/runtime_breakdown.txt: Record runtime usage of each step.

Installation

This section lays out the necessary steps to run WITCH. WITCH was originally tested on Python 3.7 and passed builds on Python 3.8 to 3.12.

Now, the program fully supports Linux and macOS systems. We provide necessary binary executables for both systems, but you can supplement your own by changing the paths in the main.config file. In cases of conflicting installations (e.g., different versions of MAFFT), please supplement with the version on your system. If you experience any difficulty running WITCH, please contact Chengze Shen (chengze5@illinois.edu).

For the macOS system on the latest chips (e.g., M1/M2), you may need to compile and supply your own binaries for WITCH to run successfully. That is, change the paths of binaries in main.config (or use -c /path/to/user/config to avoid changing the default config file) to the ones on your system.

# 1. Install with pip (--user if no root access)
pip3 install witch-msa [--user]

# 2. After installation, users can run WITCH with either "witch-msa" or "witch.py" anywhere in the system.
#    First time running WITCH will create the config file at ~/.witch_msa/main.config
witch-msa [-h]   # or,
witch.py [-h]

python>=3.7
cython>=0.29
configparser>=5.0.0
DendroPy>=4.4.0
numpy>=1.15
psutil>=5.0
tqdm>=4.0.0

# 1. Install via GitHub repo
git clone https://github.com/c5shen/WITCH.git

# 2. Install all requirements
# If you do not have root access, use "pip3 install -r requirements.txt --user"
cd WITCH
pip3 install -r requirements.txt

# 3. (Optional) Run setup.py to set up main.config. Please refer to "witch_msa/default.config"
#    Additionally, software binaries available in the user's environment will be prioritized for usage.
#    Use "-c" if want to install to WITCH/.witch_msa/main.config
#    Default is to ~/.witch_msa/main.config
python3 setup.py config [-c]

# 4. Execute the WITCH python script with -h to see allowed commandline parameter settings and
#    example usages.
python3 witch.py [-h]

Usage

The general command to run WITCH:

python3 witch.py -i [unaligned sequence file] -d [output directory] -o [output filename]

Default behavior: WITCH will pick at most 1,000 sequences from the input around the median length as the backbone sequences. Then, it uses MAGUS to align the backbone sequences and FastTree2 to estimate a tree. It uses UPP decomposition strategy to generate an eHMM, and uses HMMSearch to calculate bit scores between HMMs and unaligned sequences. Bit scores are used to calculate weights, and each unaligned sequence is aligned to top k=10 HMMs ranked by weights.

python3 witch.py -i examples/data/unaligned_all.txt \
   -d scenarioA_output -o aligned.fasta

python3 witch.py -i examples/data/unaligned_all.txt \
   -d scenarioB_output -o aligned.fasta -w 0 -k 10

python3 witch.py -b examples/data/backbone.aln.fasta \
   -q examples/data/unaligned_frag.txt -d scenarioC_output \
   -o aligned.fasta

python3 witch.py -b examples/data/backbone.aln.fasta \
   -e examples/data/backbone.tre -q examples/data/unaligned_frag.txt \
   -d scenarioD_output -o aligned.fasta \
   --save-weight 1 --keep-decomposition 1

TODO list

1. Add the last missing checkpoint systems (for initial HMMBuild and HMMSearch steps).

2. Add a sanity check for each step so that runtime errors are easier to identify.

python3 witch.py -b examples/data/backbone.aln.fasta \
   -e examples/data/backbone.tre -q examples/data/unaligned_frag.txt \
   -d scenarioE_output -o aligned.fasta \
   --save-weight 1 --keep-decomposition 1 \
   --config-file user.config