Source-linked AI summary
MOSAIK: A hash-based algorithm for accurate next-generation sequencing read mapping
Wan-Ping Lee, Michael Stromberg, Alistair Ward, Chip Stewart, Erik Garrison, Gabor T. Marth
TL;DR
Short-read sequencing creates a need for accurate, efficient alignment across diverse technologies and very large read volumes. MOSAIK addresses this with hash-based mapping and Smith-Waterman refinement, achieving PPVs of 99.5% for all alignments and 100.0% for high-confidence alignments on simulated data.
Problem
Reference-guided aligners must accurately process hundreds of millions of short reads while managing computational time and memory across diverse sequencing technologies.
Method
MOSAIK hashes overlapping reference k-mers, clusters read matches into candidate regions, and applies Smith-Waterman alignment for local refinement.
Results
99.5% PPV was achieved for all alignments and 100.0% for alignments with mapping qualities larger than 20 on simulated data.
Takeaways & Limitations
MOSAIK’s utility was demonstrated across existing sequencing technologies and in the 1000 Genomes Project.
Takeaways & Limitations
Improving computational performance can come at the expense of decreased sensitivity.
Abstract
from arXiv · showhide
This paper presents an accurate short-read mapper for next-generation sequencing data which is widely used in the 1000 Genomes Project, and human clinical and other species genome studies.
Introduction · Alignments from all sequencing technologies
MOSAIK is introduced as a sensitive, stable, and flexible reference-guided aligner designed for the diverse read characteristics and computational demands of current sequencing technologies. It applies a common algorithmic approach across major second- and third-generation platforms, while alignment rates vary with technology and read properties.
- Introduction: Short-read alignment is an early step in workflows for applications including genetic and epigenomic variant discovery, RNA-Seq, and ChIP-Seq.The resulting computational challenges arise alongside new opportunities from third-generation sequencing instruments.
- Introduction: Next-generation sequencing platforms generate hundreds of millions of reads per run, making alignment speed and memory management essential for practical analysis.These reads are typically a few hundred nucleotides or shorter.
- Introduction: MOSAIK is presented as a highly sensitive, stable, and flexible reference-guided aligner demonstrated across sequencing technologies in the 1000 Genomes Project.The introduction frames MOSAIK as addressing issues faced by genome researchers.
- Introduction: MOSAIK uses Smith-Waterman alignment and IUPAC ambiguity codes to reduce alignment artefacts and improve sensitivity and accuracy.The stated primary goal of mapping software is to minimize artefacts while increasing alignment sensitivity and accuracy.
- Alignments from all sequencing technologies: Sequencing technologies differ in library preparation, read and fragment lengths, base-quality assignments, error profiles, and output formats such as colorspace.AB SOLiD is identified as using a di-base colorspace encoding rather than conventional basespace.
- Alignments from all sequencing technologies: MOSAIK supports Illumina, Roche 454, AB SOLiD, Pacific Biosciences, and Ion Torrent reads using the same algorithmic approach.Because platform characteristics differ, the resultant alignment rates vary across technologies.
- Alignments from all sequencing technologies: Alignment-rate evaluations used simulated Illumina and Roche 454 reads, 1000 Genomes Illumina and AB SOLiD reads, and third-generation bacterial reads.The third-generation datasets comprised Ion Torrent E. coli reads and Pacific Biosciences V. cholerae reads.
- Alignments from all sequencing technologies: Reads with fewer sequencing errors generally align at higher rates, while longer and paired-end reads require more alignment time.Paired-end mapping performs additional mate-guided searches when one read cannot be mapped unambiguously, improving accuracy and reducing unaligned reads.
Highly accurate alignments on simulated data
On simulated 76- and 100-basepair Illumina paired-end reads from human chromosome 20, MOSAIK produced PPVs comparable to BWA and a relatively smooth ROC curve. Accuracy was evaluated using a 20bp tolerance window for read placement and mapping-quality cutoffs.
- Simulation design: 120 million simulated Illumina paired-end reads from chromosome 20 were generated at 76- and 100-basepair lengths with a 0.1% haplotype SNP rate.Reads were simulated from the Hg19 human genome using MASON and aligned against the entire human genome.
- Evaluation criteria: PPV was defined as correctly placed reads divided by total mapped reads, with incorrect placement assigned beyond a 20bp tolerant window.The 20bp window was chosen because most alignments contained fewer than 20bp clipped bases.
- Positive predictive value: MOSAIK and BWA had comparable PPVs across mapping-quality cutoffs in the simulated datasets.At each cutoff, PPV used only reads with mapping-quality values greater than or equal to that cutoff.
- ROC analysis: MOSAIK produced a relatively smooth ROC curve as mapped-read totals increased against incorrectly mapped-read counts.The curve represents alignments meeting progressively higher mapping-quality thresholds.
Mapping quality calibration
MOSAIK calibrates mapping qualities with a neural network using alignment, read-complexity, mapping-location, hash, and paired-end fragment-length features. Its assigned Phred scores closely match actual mapping qualities, and the network can be retrained for species-specific alignment properties.
- Neural-network calibration: MOSAIK computes mapping qualities with a neural network using alignment scores, read entropy, mapping locations, hashes, and paired-end fragment length.The neural network approximates the mapping-error function; paired-end fragment length is used for more precise calculations.
- Neural-network calibration: The default mapping-quality network was trained on simulated reads aligned to the human reference genome and their resulting MOSAIK behavior.Training features included best and second-best Smith-Waterman scores, read entropies, mapping counts, and hashes.
- Calibration accuracy: 0.9698 is MOSAIK’s average Pearson correlation between assigned and actual mapping qualities, compared with 0.9061 for BWA, 0.9207 for BOWTIE, and 0.8652 for STAMP.The comparison covered all investigated read lengths, and BOWTIE and MOSAIK were described as accurate across the full quality-score spectrum.
- Species-specific retraining: MOSAIK provides a retrainable mapping-quality pipeline to account for species-specific genome sequence content, repeat structure, low-complexity sequence, and genome size.For E. coli, 6 million simulated paired-end reads trained a neural network, followed by an independent 6 million-read evaluation set aligned to E. coli.
SNP and INDEL Analyses in the 1000 Genomes Project
The 1000 Genomes Project used MOSAIK alignments and FREEBAYES to analyze population-level human genetic variation. In 1,092 samples from 14 populations, analyses detected 33,324,407 autosomal SNPs, most of which were novel sites.
- Project scope: Phase I analyzed 1,092 individuals from 14 populations and included approximately 38 million SNPs, 1.4 million bi-allelic INDELs, and 14,000 large deletions.These calls were generated from approximately 966 billion reads and 64 trillion base pairs of human DNA.
- Variant calling: MOSAIK alignments supported SNP, MNP, and INDEL calling with FREEBAYES Bayesian variant-calling software.The passage identifies FREEBAYES as the software used to generate these variant calls.
- SNP results: 33,324,407 SNPs were detected in the autosomes of the 1,092 samples, and only 23.8% were previously known sites contained in dbSNP.The remaining detected sites were not previously known according to the passage.
- SNP results: The autosomal SNP transition/transversion ratio was 2.12, with ratios of 2.1 for novel sites and 2.17 for known sites.The passage also reports an Illumina exome ts/tv ratio of 3.18, with 3.09 for the truncated comparison.
Other SNP Studies
Beyond the 1000 Genomes Project, MOSAIK is widely used in human clinical genome studies and genome studies of other species, including cancer, model species, HIV, and parasites.
- Human clinical genome studies: MOSAIK is widely used in human clinical genome studies, including human cancer studies.The passage cites multiple cancer studies using MOSAIK.
- Other species genome studies: MOSAIK is also used for genome studies of other species, including model species, HIV, and parasites.The passage lists studies involving model species, HIV, and parasites.
Human mobile element insertion discovery
Augmenting the reference genome with known mobile element insertions enabled MOSAIK alignments to characterize their distribution in the human population. In the 1000 Genomes pilot phase, 7,380 MEI polymorphisms were detected, with FDRs of 2% for Alu, 17% for L1, and 27% for SVA insertions.
- Human mobile element insertion discovery: Augmenting the reference genome with known MEIs enabled MOSAIK alignments to provide information about their distribution in the human population.The project aimed to characterize larger structural variations in addition to short variants.
- Human mobile element insertion discovery: 7,380 MEI polymorphisms were detected from whole-genome sequencing data during the 1000 Genomes Project pilot phase.The sample set included 60 CEU, 59 YRI, and 60 CHB/JPT samples.
- Human mobile element insertion discovery: The FDRs for Alu, L1, and SVA insertions were 2%, 17%, and 27%, respectively.
- Human mobile element insertion discovery: In Phase I, the co-submitted TANGRAM software package was used to call MEIs.The supplied passage does not provide further Phase I results.
Overview
MOSAIK is a hash-based aligner that indexes overlapping reference k-mers in a constant-time lookup table, then uses matching read hashes to identify genomic positions and consolidate nearby matches into hash regions.
- Reference hashing: MOSAIK begins by splitting reference sequences into overlapping contiguous k-mers and storing each hash’s position in a hash table.The hash table guarantees O(1) lookups.
- Read mapping: MOSAIK hashes each read using the same hash size and looks up its hashes to obtain their genomic positions.This applies the reference index to read-derived hashes.
- Hash-region construction: Nearby hash positions are then consolidated into a hash region.The supplied passage introduces this consolidation step but ends before describing further details.
Processing Reference Sequences
MOSAIK supports very large reference collections, including more than 95,000 transcriptome sequences, while accommodating IUPAC ambiguity codes to reduce SNP-related alignment bias.
- Processing Reference Sequences: MOSAIK handles more than 95,000 individual reference sequences for human transcriptome alignment, with an aggregated reference-length limit of four billion bases.Available hash sizes range from 4-32.
- Processing Reference Sequences: MOSAIK supports the full set of IUPAC ambiguous nucleotide characters, reducing alignment bias when reference sequences contain SNPs.It substitutes each ambiguity code with all represented alternative bases and stores the resulting hashes.
Clustering Hashes
MOSAIK splits reads from multiple supported formats into overlapping hashes, queries their genomic positions, and clusters nearby positions with a modified AVL tree. The clustering algorithm accounts for sequencing errors so an alignment candidate region remains available despite hash-coordinate failures.
- MOSAIK supports SRF, FASTA, FASTQ, Bustard, and Gerald read formats.
- Reads are split into overlapping hashes whose genomic positions are queried from the stored reference hash table.
- A modified AVL tree clusters nearby hash positions while considering sequencing errors, preserving an alignment candidate region despite incorrect hash associations.A single sequencing error causes 15 overlapping hashes to lose association with the correct genomic coordinate, but an alignment candidate region remains in the AVL tree.
Applying Smith-Waterman Algorithm · Rescuing Paired-End Mates
MOSAIK applies Smith-Waterman alignment to candidate regions for accurate gapped-sequence alignment, while using a banded variant to improve performance. For paired-end reads, it searches near an aligned mate to rescue its unaligned partner using approximate fragment length, with fewer rescues needed for longer reads.
- Applying Smith-Waterman Algorithm: MOSAIK applies Smith-Waterman alignment to candidate regions against the reference genome.The algorithm is described as accurate for pairwise alignment and preferred for gapped sequences because it considers possible alignment frames and gaps.
- Applying Smith-Waterman Algorithm: Smith-Waterman has O(n^2) time complexity, which can impair performance on large volumes of short reads.
- Applying Smith-Waterman Algorithm: A banded Smith-Waterman implementation reduced runtimes by approximately 3x for Illumina data and 8x for Roche 454 data.
- Rescuing Paired-End Mates: Each mate is initially aligned individually before an aligned mate is used to rescue its unaligned partner.Rescue uses knowledge of the approximate fragment length from paired-end read generation.
- Rescuing Paired-End Mates: MOSAIK performs a local Smith-Waterman search in the region proximal to the aligned mate to rescue the unaligned mate.
- Rescuing Paired-End Mates: With increasing read length, fewer alignments are rescued because the aligner is less likely to miss a potential alignment.
Handling AB SOLiD reads · Known-Sequence Insertion Detections
MOSAIK handles AB SOLiD colorspace reads by aligning them in colorspace and converting alignments to basespace for BAM output. It also detects user-specified insertion sequences by prioritizing their hashes and marking supporting alignments with the ZA tag.
- Handling AB SOLiD reads: AB SOLiD reads are represented in colorspace rather than conventional basespace.Most downstream applications do not support colorspace.
- Handling AB SOLiD reads: MOSAIK aligns colorspace reads against a colorspace reference before converting alignments into basespace.The converted alignments are output to the BAM file.
- Handling AB SOLiD reads: The di-base quality conversion algorithm uses the minimum quality of the two qualities overlapping a nucleotide in basespace.
- Known-Sequence Insertion Detections: MOSAIK supports user-specified insertion sequences, including mobile element insertions.
- Known-Sequence Insertion Detections: When insertion sequences are provided, MOSAIK prioritizes their reference hashes before attempting alignment to the genome reference.
- Known-Sequence Insertion Detections: The BAM file receives a ZA tag indicating alignments of reads hitting the specified insertion sequences.
- Known-Sequence Insertion Detections: Reads from mobile element insertions can map to several locations because MEIs are repetitive elements.
Supplemental Methods
The supplemental methods describe MOSAIK’s alignment annotations, insertion-sequence targeting, hash-clustering behavior, and supplementary evaluations of mapping, variant calling, softclips, and short INDELs.
- Retraining Mapping Quality Neural Network: MOSAIK’s ZN tag records six alignment features: best and next-best Smith-Waterman scores, read entropy, longest perfect match, alignment count, and hash count.These tags were generated while aligning 6 million simulated paired-end E. coli reads with the “-zn” option.
- Detecting Specified Insertion Sequences: Users can target specified insertion sequences by giving them a shared FASTA prefix and enabling “-sref moblist,” which moves their hashes to the top.The method illustrates this with mobile element insertions carrying the prefix “moblist_”.
- Supplementary evaluations: Supplementary figures provide distributions of alignment softclips, mapping-quality positive predictive value for 100bp and 76bp reads, SNP-calling ROC curves, and short-INDEL test designs with read coverage.The SNP analyses compare FREEBAYES and SAMTOOLS using TP, FP, and FN definitions based on aligner calls and gold SNPs from simulated alignments.
- MOSAIK hash clustering: MOSAIK’s hash clustering consolidates successfully matched hashes into one AVL-tree alignment candidate region when reads align perfectly.Figure S5A depicts the uniquely and perfectly aligned-read case.
- MOSAIK hash clustering: Even when sequencing errors leave only one hash locating the proper reference position, MOSAIK retains an alignment candidate region in the AVL tree.This behavior is shown in Figure S5B.