Mashtree: a rapid comparison of whole genome sequence files

1In the past decade, the number of publicly available bacterial genomes has increased dramatically. These genomes have been generated for impactful initiatives, especially in the field of genomic epidemiology. Genomes are sequenced, shared publicly, and subsequently analyzed for phylogenetic relatedness. If two genomes of epidemiological interest are found to be related, further investigation might be prompted. However, comparing the multitudes of genomes for phylogenetic relatedness is computationally expensive and, with large numbers, laborious. Consequently, there are many strategies to reduce the complexity of the data for downstream analysis, especially using nucleotide stretches of length k (kmers).

2One major kmer strategy is to reduce each genome to split kmers. With split kmer analysis, kmers on both sides of a variable site are recorded, and the variable nucleotide is identified. When comparing two or more genomes, the variable sites are compared. Split kmers have been implemented in software packages such as KSNP and SKA.

3Another major kmer strategy is to convert genomic data into manageable datasets, usually called sketches. Most notably, an algorithm called min-hash was implemented in the Mash package. In the min-hash algorithm, all kmers are recorded and transformed into integers using hashing and a Bloom filter. These hashed kmers are sorted and only the first several kmers are retained. The kmers that appear at the top of the sorted list are collectively called the sketch. Any two sketches can be compared by counting how many hashed kmers they have in common.

4Because min-hash creates distances between any two genomes, min-hash values can be used to rapidly cluster genomes into trees using the neighbor-joining algorithm. We implemented this idea in software called Mashtree, which quickly and efficiently generates large trees that would be too computationally intensive using other methods.

5Mashtree builds on two major algorithms that are already implemented in other software packages. The first is the min-hash algorithm, which is implemented in the software Mash. Mashtree uses Mash to create sketches of the genomes with the function mash sketch. We elected to keep most default Mash parameters but increased the sketch size (number of hashed kmers) from 1,000 to 10,000 to increase discriminatory power. Then, Mash is used to calculate the distances between genomes with mash dist. Mashtree records these distances into a pairwise distance matrix. Next, Mashtree calls the neighbor-joining (NJ) algorithm which is implemented in the software QuickTree. The Mash distance matrix is used with QuickTree with default options to generate a dendrogram. The workflow is depicted in Figure 1.

6Although Mashtree does not infer phylogeny, we have borrowed the ideas behind phylogenetic confidence values to yield confidence values for each parent node in the tree. There are two resampling methods implemented in Mashtree to assign support values to internal nodes: bootstrapping and jackknifing. Initially, both methods create a tree as depicted in Figure 1. Then, confidence values can be calculated for the tree using either the bootstrapping approach or the jackknifing approach (Figures 2 and 3).

7Mashtree has several other useful features. First, Mashtree can read any common sequence file type and can read gzip-compressed files (e.g., fastq, fastq.gz, fasta). This is a major advantage in being compatible with a wide variety of databases and with space-saving file compression. Second, Mashtree takes advantage of multithreading. The number of requested threads is used to determine how many genomes are sketched at the same time and how many sketches can be compared at the same time. When the number of threads requested outnumbers the number of operations that it can parallelize, Mashtree uses the multithreading already encoded in Mash sketches and distances. Third, Mashtree uses an SQLite database which can be used to cache results between runs.

8The Mashtree package is programmed in Perl, and is available in the CPAN repository. Documentation can be found at https://github.com/lskatz/mashtree.