Identification and alignment of template switch mutations

Twitcher

Twitcher (template switch aligner) is a tool for identification and annotation of short-range template switch events. It builds on the ideas introduced in Löytynoja and Goldman (2017) and Löytynoja (2022), but includes a novel algorithm for optimal alignment of two sequences with any number of template switches. Twitcher works on VCF- and BAM-formatted data and can be directly incorporated in genome data analysis pipelines.

Twitcher operates in two stages:

  1. While reading the input (VCF or BAM; from stdin or a file), it extracts suspicious™ clusters of SNVs, MNVs and indels, e.g. more than 2 base changes within 10 bp window.
  2. It then reconstructs the haplotype for the mutation cluster and its context, and aligns that with the homologous region in the reference genome. If the mutation cluster can be better explained with one or more template switches, it outputs the new, reannotated VCF record and/or description of the mutation in CSV format.

Algorithm

Twitcher implements the original FPA algorithm but, by default, uses a novel tsalign algorithm. Conceptually, tsalign builds on the previous implementation and combines classical dynamic programming approaches with the possibility to jump between multiple matrices. However, the number of jumps (and independent template switch events) is not limited and also copy-events in forward orientation can be included. The flexibility comes with a cost, and tsalign solves a problem that is \(O(n^6)\) in time and memory in the worst case.

Computational speedups

To reduce the search space and time, we use the A* algorithm with a predictive heuristic to create a lower bound on the remaining alignment cost. In practice, the algorithm is sufficiently fast for analyses of complex sequences but it may fail on repetitive sequences with numerous equally good sub-solutions. That is mostly acceptable and mutations with true consequences are likely located in the complex regions. Furthermore, alternative mutation mechanisms explaining copy-number reductions and expansions exist, and having a template switch solution that could also explain them may be of little interest.

(In principle, polymerase “slippage” is a template switch and identifiable by Twitcher. As explained below, they are disabled by default.)

As the low-complexity regions have the highest space and time complexity, one may let Twitcher try aligning everything but set the memory limit sufficiently low it to fail on out-of-memory error with little delay. (OOM errors are typically less serious than they sound!) Alternatively, one may restrict the analyses to “complex” parts of the genome by providing target regions in a file. This is sometimes called a “positive mask” for the genome.

The underlying tsalign algorithm is very generic and another option for speeding up the analysis is to disable some mutation types and parameters. By default, forward copy events are disabled in Twitcher and, similarly to the original FPA tool, it only searches for reverse-complement copy events. tsalign also allows setting different mutation costs for various classes of sites and, by default, only some of these are enabled. The full scale of mutations – and the relative cost of events – can be adjusted through the cost model file, as explained in Aligner Costs.

Finally, the tsalign algorithm is accelerated by restricting the switch out and switch in events in the proximity of the mutation cluster. As we want to explain the cluster with a TSM, it is typically not necessary to allow switching between matrices elsewhere, and by default, the switch out/in isn only allowed in an interval immediately around the cluster. See Usage for details.

The greatest speed up for the tsalign algorithm is not to use it at all. Twitcher can build and utilise a database of known mutation clusters and retrieve the solution for a known pattern without the alignment step. This gives a massive acceleration in analyses of population data where individuals contain only few unique mutations and largely share the mutation patterns with others. A Twitcher DB can be considered a “panel” of known mutation clusters and be reutilised in production analyses. See Concepts -> Database.

Description of TSM events

The inferred template switch events are described using a novel TSIGAR format, which can be understood as an extension to the CIGAR format. The format is explained in more detail in Usage TSIGAR and Output -> TSIGAR.

Installation

Twitcher (and tsalign) are written in Rust and available through cargo install. Those not familiar with Rust may prefer the prebuilt binary.

Prebuilt binary (Linux, x86-64)

Every release ships a prebuilt binary for Linux:

curl -LO https://version.helsinki.fi/kraujasp/twitcher/-/releases/permalink/latest/downloads/binaries/twitcher-linux-x86_64
chmod +x twitcher-linux-x86_64
./twitcher-linux-x86_64 --version

The binary is built for x86-64-v3 (AVX2), so it needs a reasonably modern CPU. More detailed instructions are available in Installation.

From source

Twitcher is an open-source software and the code is available at https://version.helsinki.fi/kraujasp/twitcher/. It can be installed from source using cargo:

cargo install twitcher

cargo (version 1.96.0 or higher is required) is available e.g. via rustup. The clang C compiler is required to compile the underlying htslib bindings.

Instructions for building Twitcher locally are available in Installation.

Usage

Twitcher has two main commands analysis:

  • twitcher vcf — Analyse and re-annotate VCF files with template switch mutations
  • twitcher reads — Identify template switch mutations in sequencing reads

and one for visualisation:

  • twitcher -viz - Plot template switch explanation for an identified event

Quick Start

twitcher vcf input.vcf reference.fa -o output.vcf

This realigns identified mutation clusters and outputs inferred TSM events as single complex variants.

Detailed instructions for using the program are available in Usage and the subpages in Docs.