MIKE: an ultrafast, assembly-, and alignment-free approach for phylogenetic tree construction

Abstract

Motivation: Constructing a phylogenetic tree requires calculating the evolutionary distance between samples or species via large-scale resequencing data, a process that is both time-consuming and computationally demanding. Striking the right balance between accuracy and efficiency is a significant challenge.

Results: To address this, we introduce a new algorithm, MIKE (MinHash-based k-mer algorithm). This algorithm is designed for the swift calculation of the Jaccard coefficient directly from raw sequencing reads and enables the construction of phylogenetic trees based on the resultant Jaccard coefficient. Simulation results highlight the superior speed of MIKE compared to existing state-of-the-art methods. We used MIKE to reconstruct a phylogenetic tree, incorporating 238 yeast, 303 Zea, 141 Ficus, 67 Oryza, and 43 Saccharum spontaneum samples. MIKE demonstrated accurate performance across varying evolutionary scales, reproductive modes, and ploidy levels, proving itself as a powerful tool for phylogenetic tree construction.

Availability and implementation: MIKE is publicly available on Github at https://github.com/Argonum-Clever2/mike.git.

Figure 1.

The process of simulating data and overview of MIKE algorithm. (a) The process of simulating data. Four sets of monoploid datasets were simulated, including haploid, autotetraploid, allotetraploid, and polyploid. Beginning with the same ancestral chromosomes, some regions are designated as conservative (no mutations) and others as non-conservative (allowing mutations). Polyploids can generate new genomes through processes such as whole-genome duplication (WGD) and hybridization. The polyploid datasets were simulated with six ploidy levels: diploid, tetraploid, hexaploid, octoploid, dodecaploid, and hexadecaploid. Each dataset is designed to undergo mutations in each generation, resulting in the generation of n different offspring in the process. (b) The overview of MIKE algorithm. First, the sequencing reads are divided into k-mers, with k set to 21 by default. A mapping is defined to represent each character using 2 bits, where A, C, G, and T correspond to 00, 01, 10, and 11, respectively. Each k-mer is split into two parts, defined as a prefix and a suffix, $k_{\mathrm{pre}}$ and $k_{\mathrm{suf}}$. Subsequently, k-mers with the same $k_{\mathrm{pre}}$ are grouped together. Within each group, a random shuffled permutation $\mathrm{\pi }$ with a numerical range of $[1,\mathrm{ }\max (k_{\mathrm{suf}}\left)\right]$ is applied. All $k_{\mathrm{suf}}$ values for each group are marked with either 0 or 1 to create one-hot vectors, where a value is marked as 1 if the $k_{\mathrm{suf}}$ occurs and 0 if it does not. These vectors are then multiplied by the permutation $\mathrm{\pi }$ and the smallest non-zero value $h_{\mathrm{\pi }}\left(c\right)$ is selected as the representative feature value for that group, known as the minhash fingerprint. This minhash fingerprint can effectively represent the original sequencing data

Figure 2.

Computational efficiencies. (a) The process of simulating data. (b) Four sets of monoploid datasets were simulated, including haploid, autotetraploid, allotetraploid, and polyploid

Figure 3.

The phylogenetic tree of Ficus. (a, b) The phylogenetic tree constructed using MIKE for 141 samples of the genus Ficus. (c) The phylogenetic tree for 22 species selected from the subgenus Sycomorus of the genus Ficus, constructed using both MIKE and CallSNPs through BIONJ methods

Figure 4.

The phylogenetic tree constructed using MIKE for 303 samples of the genus Zea

Figure 5.

The phylogenetic tree constructed using MIKE for 42 samples of S.spontaneum