8000 minimap2/tex/minimap2.tex at v2.12 · Geehome/minimap2 · GitHub
[go: up one dir, main page]

Skip to content

Latest commit

 

History

History
724 lines (644 loc) · 36.8 KB

minimap2.tex

File metadata and controls

724 lines (644 loc) · 36.8 KB
banding, our implementation is slower than Edlib~\citep{Sosic:2017aa}, but with
a 1000bp band, it is considerably faster. When performing global alignment
between anchors, we expect the alignment to stay close to the diagonal of the
DP matrix. Banding is applicable most of the time.
\subsubsection{The Z-drop heuristic}
With global alignment, minimap2 may force to align unrelated sequences between
two adjacent anchors. To avoid such an artifact, we compute accumulative
alignment score along the alignment path and break the alignment where the
score drops too fast in the diagonal direction. More precisely, let $S(i,j)$ be
the alignment score along the alignment path ending at cell $(i,j)$ in the DP
matrix. We break the alignment if there exist $(i',j')$ and $(i,j)$, $i'<i$ and
$j'<j$, such that
\[
S(i',j')-S(i,j)>Z+e\cdot|(i-i')-(j-j')|
\]
where $e$ is the gap extension cost and $Z$ is an arbitrary threshold.
This strategy is first used in BWA-MEM. It is similar to X-drop employed in
BLAST~\citep{Altschul:1997vn}, but unlike X-drop, it would not break the
alignment in the presence of a single long gap.
When minimap2 breaks a global alignment between two anchors, it performs local
alignment between the two subsequences involved in the global alignment, but
this time with the one subsequence reverse complemented. This additional
alignment step may identify short inversions that are missed during chaining.
\subsubsection{Filtering out misplaced anchors}
Due to sequencing errors and local homology, some anchors in a chain may be
wrong. If we blindly align regions between two misplaced anchors, we will
produce a suboptimal alignment. To reduce this artifact, we filter out
anchors that lead to a $>$10bp insertion and a $>$10bp deletion at the same
time, and filter out terminal anchors that lead to a long gap towards the ends
of a chain. These heuristics greatly alleviate the issues with misplaced
anchors, but they are unable to fix all such errors. Local misalignment is a
limitation of minimap2 which we hope to address in future.
\subsection{Aligning spliced sequences}
The algorithm described above can be adapted to spliced alignment. In this
mode, the chaining gap cost distinguishes insertions to and deletions from the
reference: $\gamma_c(l)$ in Eq.~(\ref{eq:chain-gap}) takes the form of
\[
\gamma_c(l)=\left\{\begin{array}{ll}
0.01\cdot\bar{w}\cdot l+0.5\log_2 l & (l>0) \\
\min\{0.01\cdot\bar{w}\cdot|l|,\log_2|l|\} & (l<0)
\end{array}\right.
\]
Similarly, the gap cost function used for DP-based alignment is changed to
\[
\gamma_a(l)=\left\{\begin{array}{ll}
q+l\cdot e & (l>0) \\
\min\{q+|l|\cdot e,\tilde{q}\} & (l<0)
\end{array}\right.
\]
In alignment, a deletion no shorter than $\lceil(\tilde{q}-q)/e\rceil$ is
regarded as an intron, which pays no cost to gap extensions.
To pinpoint precise splicing junctions, minimap2 introduces reference-dependent
cost to penalize non-canonical splicing:
\begin{equation}\label{eq:splice}
\left\{\begin{array}{l}
H_{ij} = \max\{H_{i-1,j-1}+s(i,j),E_{ij},F_{ij},\tilde{E}_{ij}-a(i)\}\\
E_{i+1,j}= \max\{H_{ij}-q,E_{ij}\}-e\\
F_{i,j+1}= \max\{H_{ij}-q,F_{ij}\}-e\\
\tilde{E}_{i+1,j}= \max\{H_{ij}-d(i)-\tilde{q},\tilde{E}_{ij}\}\\
\end{array}\right.
\end{equation}
Let $T$ be the reference sequence. $d(i)$ is computed as
\[d(i)=\left\{\begin{array}{ll}
0 & \mbox{if $T[i+1,i+3]$ is ${\tt GTA}$ or ${\tt GTG}$} \\
p/2 & \mbox{if $T[i+1,i+3]$ is ${\tt GTC}$ or ${\tt GTT}$} \\
p & \mbox{otherwise}
\end{array}\right.\]
where $T[i,j]$ extracts a substring of $T$ between $i$ and $j$ inclusively.
$d(i)$ penalizes non-canonical donor sites with $p$ and less frequent Eukaryotic
splicing signal ${\tt GT[C/T]}$ with $p/2$~\citep{Irimia:2008aa}. Similarly,
\[a(i)=\left\{\begin{array}{ll}
0 & \mbox{if $T[i-2,i]$ is ${\tt CAG}$ or ${\tt TAG}$} \\
p/2 & \mbox{if $T[i-2,i]$ is ${\tt AAG}$ or ${\tt GAG}$} \\
p & \mbox{otherwise}
\end{array}\right.\]
models the acceptor signal. Eq.~(\ref{eq:splice}) is close to an equation in
\citet{Zhang:2006aa} except that we allow insertions immediately followed by
deletions and vice versa; in addition, we use the Suzuki-Kasahara diagonal
formulation in actual implementation.
If RNA-seq reads are not sequenced from stranded libraries, the read strand
relative to the underlying transcript is unknown. By default, minimap2 aligns
each chain twice, first assuming ${\tt GT}$--${\tt AG}$ as the splicing signal
and then assuming ${\tt CT}$--${\tt AC}$, the reverse complement of ${\tt
GT}$--${\tt AG}$, as the splicing signal. The alignment with a higher score is
taken as the final alignment. This procedure also infers the relative strand of
reads that span canonical splicing sites.
In the spliced alignment mode, minimap2 further increases the density of
minimizers and disables banded alignment. Together with the two-round DP-based
alignment, spliced alignment is several times slower than genomic DNA
alignment.
\subsection{Aligning short paired-end reads}
During chaining, minimap2 takes a pair of reads as one fragment with a gap of
unknown length in the middle. It applies a normal gap cost between seeds on the
same read but is a more permissive gap cost between seeds on different reads.
More precisely, the gap cost during chaining is ($l\not=0$):
\[
\gamma_c(l)=\left\{\begin{array}{ll}
0.01\cdot\bar{w}\cdot |l|+0.5\log_2 |l| & \mbox{if two seeds on the same read} \\
\min\{0.01\cdot\bar{w}\cdot|l|,\log_2|l|\} & \mbox{otherwise}
\end{array}\right.
\]
After identifying primary chains (Section~\ref{sec:primary}), we split each
fragment chain into two read chains and perform alignment for each read as in
Section~\ref{sec:genomic}. Finally, we pair hits of each read end to find
consistent paired-end alignments.
\end{methods}
\section{Results}
Minimap2 is implemented in the C programming language and comes with APIs in
both C and Python. It is distributed under the MIT license, free to both
commercial and academic uses. Minimap2 uses the same base algorithm for all
applications, but it has to apply different sets of parameters depending on
input data types. Similar to BWA-MEM, minimap2 introduces `presets' that
modify multiple parameters with a simple invocation. Detailed settings
and command-line options can be found in the minimap2 manpage. In addition to
the applications evaluated in the following sections, minimap2 also retains
minimap's functionality to find overlaps between long reads and to search
against large multi-species databases such as \emph{nt} from NCBI.
\subsection{Aligning long genomic reads}\label{sec:long-genomic}
\begin{figure}[!tb]
\centering
\includegraphics[width=.5\textwidth]{roc-color.pdf}
\caption{Evaluation on aligning simulated reads. Simulated reads were mapped
to the primary assembly of human genome GRCh38. A read is considered correctly
mapped if its longest alignment overlaps with the true interval, and the
overlap length is $\ge$10\% of the true interval length. Read alignments are
sorted by mapping quality in the descending order. For each mapping quality
threshold, the fraction of alignments (out of the number of input reads) with
mapping quality above the threshold and their error rate are
plotted along the curve. (a) long-read alignment evaluation. 33,088 $\ge$1000bp
reads were simulated using pbsim~\citep{Ono:2013aa} with error profile sampled
from file `m131017\_060208\_42213\_*.1.*' downloaded at
\href{http://bit.ly/chm1p5c3}{http://bit.ly/chm1p5c3}. The N50 read length is
11,628. Aligners were run under the default setting for SMRT reads.
Kart outputted all alignments at mapping quality 60, so is not shown in the
figure. It mapped nearly all reads with 4.1\% of alignments being wrong, less
accurate than others. (b) short-read alignment evaluation. 10 million pairs of
150bp reads were simulated using mason2~\citep{Holtgrewe:2010aa} with option
`\mbox{--illumina-prob-mismatch-scale 2.5}'. Short-read aligners were run under
the default setting except for changing the maximum fragment length to
800bp.}\label{fig:eval}
\end{figure}
As a sanity check, we evaluated minimap2 on simulated human reads along with
BLASR~(v1.MC.rc64; \citealp{Chaisson:2012aa}),
BWA-MEM~(v0.7.15; \citealp{Li:2013aa}),
GraphMap~(v0.5.2; \citealp{Sovic:2016aa}),
Kart~(v2.2.5; \citealp{Lin:2017aa}),
minialign~(v0.5.3; \href{https://github.com/ocxtal/minialign}{https://github.com/ocxtal/minialign}) and
NGMLR~(v0.2.5; \citealp{Sedlazeck169557}). We excluded rHAT~\citep{Liu:2016ab}
and LAMSA~\citep{Liu:2017aa} because they either
crashed or produced malformatted output. In this evaluation, minimap2 has
higher power to distinguish unique and repetitive hits, and achieves overall
higher mapping accuracy (Fig.~\ref{fig:eval}a). Minimap2 and
NGMLR provide better mapping quality estimate: they rarely give repetitive hits
high mapping quality. Apparently, other aligners may
occasionally miss close suboptimal hits and be overconfident in wrong mappings.
On run time, minimap2 took 200 CPU seconds, comparable to minialign and Kart, and is over
30 times faster than the rest. Minimap2 consumed 6.8GB memory at the peak,
more than BWA-MEM (5.4GB), similar to NGMLR and less than others.
On real human SMRT reads, the relative performance and fraction of mapped reads reported by
these aligners are broadly similar to the metrics on simulated data. We are
unable to provide a good estimate of mapping error rate due to the lack of the
truth. On ONT $\sim$100kb human reads~\citep{Jain128835}, BWA-MEM failed.
Kart, minialign and minimap2 are over 70 times faster than others. We have also
examined tens of $\ge$100bp INDELs in IGV~\citep{Robinson:2011aa} and can
confirm the observation by~\citet{Sedlazeck169557} that BWA-MEM often breaks
them into shorter gaps. The issue is much alleviated with minimap2, thanks
to the 2-piece affine gap cost.
\subsection{Aligning long spliced reads}
We evaluated minimap2 on SIRV control data~(AC:SRR5286959;
\citealp{Byrne:2017aa}) where the truth is known. Minimap2 predicted 59\,918
introns from 11\,018 reads. 93.8\% of splice juctions are precise. We examined
wrongly predicted junctions and found the majority were caused by clustered
splicing signals (e.g. two adjacent ${\tt GT}$ sites). When INDEL sequencing
errors are frequent, it is difficult to find precise splicing sites in this
case. If we allow up to 10bp distance from true splicing sites, 98.4\% of
aligned introns are approximately correct. It is worth noting that for SIRV, we
asked minimap2 to model the ${\tt GT..AG}$ splicing signal only without extra
bases. This is because SIRV does not honor the evolutionarily prevalent signal
${\tt GT[A/G]..[C/T]AG}$~\citep{Irimia:2008aa}.
\begin{table}[!tb]
\processtable{Evaluation of junction accuracy on 2D ONT reads}
{\footnotesize\label{tab:intron}
\begin{tabular}{p{3.1cm}rrrr}
\toprule
& GMAP & minimap2 & SpAln & STAR\\
\midrule
Run time (CPU min) & 631 & 15.9 & 2\,076 & 33.9 \\
Peak RAM (GByte) & 8.9 & 14.5 & 3.2 & 29.2\vspace{1em}\\
\# aligned reads & 103\,669 & 104\,199 & 103\,711 & 26\,479 \\
\# chimeric alignments & 1\,904 & 1\,488 & 0 & 0 \\
\# non-spliced alignments & 15\,854 & 14\,798 & 17\,033 & 10\,545\vspace{1em}\\
\# aligned introns & 692\,275 & 693\,553 & 692\,945 & 78\,603 \\
\# novel introns & 11\,239 & 3\,113 & 8\,550 & 1\,214 \\
\% exact introns & 83.8\% & 94.0\% & 87.9\% & 55.2\% \\
\% approx. introns & 91.8\% & 96.9\% & 92.5\% & 82.4\% \\
\botrule
\end{tabular}
}{Mouse cDNA reads (AC:SRR5286960; R9.4 chemistry) were mapped to the primary assembly of mouse
genome GRCm38 with the following tools and command options: minimap2 (`-ax
splice'); GMAP (`-n 0 --min-intronlength 30 --cross-species'); SpAln (`-Q7 -LS
-S3'); STARlong (according to
\href{http://bit.ly/star-pb}{http://bit.ly/star-pb}). The alignments were
compared to the EnsEMBL gene annotation, release 89. A predicted intron
is \emph{novel} if it has no overlaps with any annotated introns. An intron
is \emph{exact} if it is identical to an annotated intron. An intron is
\emph{approximate} if both its 5'- and 3'-end are within 10bp around the ends
of an annotated intron. Chimeric alignments are defined in the SAM spec~\citep{Li:2009ys}.}
\end{table}
We next aligned real mouse reads~\citep{Byrne:2017aa} with GMAP~(v2017-06-20;
\citealp{Wu:2005vn}), minimap2, SpAln~(v2.3.1; \citealp{Iwata:2012aa}) and
STAR~(v2.5.3a; \citealp{Dobin:2013kx}). In general, minimap2 is more
consistent with existing annotations (Table~\ref{tab:intron}): it finds
more junctions with a higher percentage being exactly or approximately correct.
Minimap2 is over 40 times faster than GMAP and SpAln. While STAR is close to
minimap2 in speed, it does not work well with noisy reads.
We have also evaluated spliced aligners on a human Nanopore Direct RNA-seq
dataset (\href{http://bit.ly/na12878ont}{http://bit.ly/na12878ont}). Minimap2
aligned 10 million reads in $<$1 wall-clock hour using 16 CPU cores. 94.2\% of
aligned splice junctions consistent with gene annotations. In comparison,
GMAP under option `-k 14 -n 0 --min-intronlength 30 --cross-species' is 160
times slower; 68.7\% of GMAP junctions are found in known gene annotations. The
percentage increases to 84.1\% if an aligned junction within 10bp from an
annotated junction is considered to be correct. On a public Iso-Seq dataset
(human Alzheimer brain from
\href{http://bit.ly/isoseqpub}{http://bit.ly/isoseqpub}), minimap2 is also
faster at higher junction accuracy in comparison to other aligners in
Table~\ref{tab:intron}.
We noted that GMAP and SpAln have not been optimized for noisy reads. We are
showing the best setting we have experimented, but their developers should be
able to improve their accuracy further.
%\begin{table}[!tb]
%\processtable{Evaluation of junction accuracy on SMRT Iso-Seq reads}
%{\footnotesize
%\begin{tabular}{lrrrr}
%\toprule
% & GMAP & minimap2 & SpAln & STAR \\ % one GMAP thread took 14 days to align a tiny fraction of reads
%\midrule
%Run time (CPU min) & - & 243 & 2,352 & 1,647 \\
%\# aligned reads & 1,113,502 & 1,123,025 & 1,094,092 & 682,452 \\
%\# chimeric alignments & 48,927 & 33,091 & 0 & 0 \\
%\# non-spliced alignments & 334,097 & 339,081 & 291,447 & 272,536 \vspace{1em}\\
%\# aligned introns & 8,922,221 & 9,071,755 & 9,208,564 & 3,029,121 \\
%\# novel introns & 48,927 & 42,773 & 82,230 & 17,791 \\
%\% exact introns & 90.6\% & 94.9\% & 91.7\% & 84.7\% \\
%\% approx. introns & 94.0\% & 96.9\% & 93.4\% & 93.8\% \\
%\botrule
%\end{tabular}
%}{}
%\end{table}
\subsection{Aligning short genomic reads}
We evaluated minimap2 along with Bowtie2~(v2.3.3; \citealt{Langmead:2012fk}), BWA-MEM and
SNAP (v1.0beta23; \citealt{Zaharia:2011aa}). Minimap2 is 3--4 times as fast as Bowtie2 and
BWA-MEM, but is 1.3 times slower than SNAP. Minimap2 is more accurate on this
simulated data set than Bowtie2 and SNAP but less accurate than BWA-MEM
(Fig.~\ref{fig:eval}b). Closer investigation reveals that BWA-MEM achieves
a higher accuracy partly because it tries to locally align a read in a small
region close to its mate. If we disable this feature, BWA-MEM becomes slightly
less accurate than minimap2. We might implement a similar heuristic
in minimap2 in future.
To evaluate the accuracy of minimap2 on real data, we aligned human reads
(AC:ERR1341796) with BWA-MEM and minimap2, and called SNPs and small INDELs
with GATK HaplotypeCaller v3.5~\citep{Depristo:2011vn}. This run was sequenced
from experimentally mixed CHM1 and CHM13 cell lines. Both of them are homozygous
across the whole genome and have been \emph{de novo} assembled with SMRT reads
to high quality. This allowed us to construct an independent truth variant
dataset~\citep{Li223297} for
ERR1341796. In this evaluation, minimap2 has higher SNP false negative rate
(FNR; 2.6\% of minimap2 vs 2.3\% of BWA-MEM), but fewer false positive SNPs per
million bases (FPPM; 7.0 vs 8.8), similar INDEL FNR (11.2\% vs 11.3\%) and
similar INDEL FPPM (6.4 vs 6.5). Minimap2 is broadly comparable to BWA-MEM in the
context of small variant calling.
\subsection{Aligning long-read assemblies}
Minimap2 can align a SMRT assembly (AC:GCA\_001297185.1) against GRCh38 in 7
minutes using 8 CPU cores, over 20 times faster than nucmer from
MUMmer4~\citep{Marcais:2018aa}. With the paftools.js script from the minimap2
package, we called 2.67 million single-base substitutions out of 2.78Gbp
genomic regions. The transition-to-transversion ratio (ts/tv) is 2.01. In
comparison, using MUMmer4's dnadiff pipeline, we called 2.86 million
substitutions in 2.83Gbp at ts/tv=1.87. Given that ts/tv averaged across the
human genome is about 2 but ts/tv averaged over random errors is 0.5, the
minimap2 callset arguably has higher precision at lower sensitivity.
The sample being assembled is a female. Minimap2 still called 201 substitutions
on the Y chromosome. These substitutions all come from one contig aligned at
96.8\% sequence identity. The contig could be a segmental duplication
absent from GRCh38. In constrast, dnadiff called 9070 substitutions on the Y
chromosome across 73 SMRT contigs. This again implies our minimap2-based
pipeline has higher precision.
\section{Discussions}
Minimap2 is a versatile mapper and pairwise aligner for nucleotide sequences.
It works with short reads, assembly contigs and long noisy genomic and RNA-seq
reads, and can be used as a read mapper, long-read overlapper or a full-genome
aligner. Minimap2 is also accurate and efficient, often outperforming other
domain-specific alignment tools in terms of both speed and accuracy.
The capability of minimap2 comes from a fast base-level alignment algorithm and
an accurate chaining algorithm. When aligning long query sequences, base-level
alignment is often the performance bottleneck. The Suzuki-Kasahara algorithm
greatly alleviates the bottleneck and enables DP-based splice alignment
involving $>$100kb introns, which was impractically slow ten years ago. The
minimap2 chaining algorithm is fast and highly accurate by itself. In fact,
chaining alone is more accurate than all the other long-read mappers in
Fig.~\ref{fig:eval}a (data not shown). This accuracy helps to reduce downstream
base-level alignment of candidate chains, which is still several times slower than
chaining even with the Suzuki-Kasahara improvement. In addition, taking a
general form, minimap2 chaining can be adapted to non-typical data types such as
spliced reads and multiple reads per fragment. This gives us the opportunity to
extend the same base algorithm to a variety of use cases.
Modern mainstream aligners often use a full-text index, such as suffix array or
FM-index, to index reference sequences. An advantage of this approach is that
we can use exact seeds of arbitrary lengths, which helps to increase seed
uniqueness and reduce unsuccessful extensions. Minimap2 indexes reference
k-mers with a hash table instead. Such fixed-length seeds are inferior to
variable-length seeds in theory, but can be computed much more efficiently in
practice. When a query sequence has multiple seed hits, we can afford to skip
highly repetitive seeds without affecting the final accuracy. This further
alleviates the concern with the seeding uniqueness. At the same time, at low
sequence identity, it is rare to see long seeds anyway. Hash table is the ideal
data structure for mapping long noisy sequences.
\section*{Acknowledgements}
We owe a debt of gratitude to H. Suzuki and M. Kasahara for releasing their
masterpiece and insightful notes before formal publication. We thank M.
Schatz, P. Rescheneder and F. Sedlazeck for pointing out the limitation of
BWA-MEM. We are also grateful to minimap2 users who have greatly helped to
suggest features and to fix various issues.
\paragraph{Funding\textcolon} NHGRI 1R01HG010040-01
\bibliography{minimap2}
\end{document}
0