Seedability: optimizing alignment parameters for sensitive sequence comparison

Abstract

Motivation: Most sequence alignment techniques make use of exact k-mer hits, called seeds, as anchors to optimize alignment speed. A large number of bioinformatics tools employing seed-based alignment techniques, such as $\mathrm{Minimap2}$, use a single value of k per sequencing technology, without a strong guarantee that this is the best possible value. Given the ubiquity of sequence alignment, identifying values of k that lead to more sensitive alignments is thus an important task. To aid this, we present $\mathrm{Seedability}$, a seed-based alignment framework designed for estimating an optimal seed k-mer length (as well as a minimal number of shared seeds) based on a given alignment identity threshold. In particular, we were motivated to make $\mathrm{Minimap2}$ more sensitive in the pairwise alignment of short sequences.

Results: The experimental results herein show improved alignments of short and divergent sequences when using the parameter values determined by $\mathrm{Seedability}$ in comparison to the default values of $\mathrm{Minimap2}$. We also show several cases of pairs of real divergent sequences, where the default parameter values of $\mathrm{Minimap2}$ yield no output alignments, but the values output by $\mathrm{Seedability}$ produce plausible alignments.

Availability and implementation: https://github.com/lorrainea/Seedability (distributed under GPL v3.0).

Figure 1.

Step 1 of estimating $e_{s_i,s_j}$.

Figure 2.

Step 2 of estimating $e_{s_i,s_j}$.

Figure 3.

(a) The average alignment identities (i.e. the total alignment identity score divided by the total number of pairs) output for the 100 pairs of sequences when using the default $\mathsf{Minimap2} (\kappa ,w)$ values in comparison to the $(\kappa ,w)$ values determined by $\mathsf{Seedability}$. For the preset options, we have used: (i) the default preset option map-ont, if the average sequence length is ≥1000; or (ii) the preset option sr, if the average sequence length is <1000. (b) The number of mapped alignments when using the default $\mathsf{Minimap2}\hspace{0.17em}\hspace{0.17em}(\kappa ,w)$ values in comparison to the $(\kappa ,w)$ values determined by $\mathsf{Seedability}$. For the preset options, we have used: (i) the default preset option map-ont, if the average sequence length is ≥1000; or (ii) the preset option sr, if the average sequence length is <1000.

Figure 4.

The number of alignments that have an alignment length at least 90% of the original sequence length when using the default $\mathsf{Minimap2}$$(\kappa ,w)$ values in comparison to the $(\kappa ,w)$ values determined by $\mathsf{Seedability}$. For the preset options, we have used: (i) the default preset option map-ont, if the average sequence length is ≥1000; or (ii) the preset option sr, if the average sequence length is <1000.

Figure 5.

The average time in ms required when using preset option map-ont for (a) $\mathsf{Seedability}$ to compute (t, k), (b) $\mathsf{Minimap2}$ to compute an alignment using default parameter values, and (c) $\mathsf{Minimap2}$ to compute an alignment using the $(\kappa ,w)$ values determined by $\mathsf{Seedability}$.

Figure 6.

The average peak memory in MB required when using preset option map-ont for (a) $\mathsf{Seedability}$ to compute (t, k), (b) $\mathsf{Minimap2}$ to compute an alignment using default parameter values and (c) $\mathsf{Minimap2}$ to compute an alignment using the $(\kappa ,w)$ values determined by $\mathsf{Seedability}$.

Figure 7.

Human gene versus ortholog alignment produced by $\mathsf{Minimap2}$ when using $(\kappa =4,w=3)$ determined by $\mathsf{Seedability}$ in comparison to no output alignment produced when using the default $(\kappa ,w)$ values of $\mathsf{Minimap2}$.

Figure 8.

(a) The number of mapped sequences when using the default $(\kappa ,w)$ values of $\mathsf{Minimap2}$. (b) The number of mapped sequences when using the $(\kappa ,w)$ values determined by $\mathsf{Seedability}$ from Table 1.