Technical Summary: AirLift

Problem Statement

Reference genomes are inherently imperfect representations of the average healthy individual of a species due to errors in sequencing technologies and assembly algorithms. With improvements in sequencing technologies and assembly tools, reference genomes are progressively updated (e.g., the update of the human reference genome from GRCh37 to GRCh38, as well as recent Telomere-to-Telomere assemblies). To ensure the accuracy of downstream genomic analyses, such as variant discovery, read sets must be mapped to the latest reference genome.

Currently, the standard approach is to re-run the entire analysis pipeline and map all reads completely from scratch to the new reference genome. This process is computationally intensive; for example, aligning 300 million short reads to the human genome can take approximately 75 hours. Given that the volume of genomic data doubles every eight months and highly specific reference genomes for diverse populations are emerging, the necessity to map read sets to multiple references exacerbates this computational burden.

Existing "remapping" tools (e.g., UCSC LiftOver, CrossMap) attempt to accelerate this process by using chain files to translate coordinates from an old to a new reference based on conserved regions. However, these tools suffer from three critical limitations:

1. Lack of Completeness: They cannot remap reads located in "deprecated" regions (deleted in the new reference) or "new" regions (inserted in the new reference), leading to significant loss of genomic coverage (e.g., the absence of >7% of gene annotations when switching from hg16 to hg38).
2. Inaccuracy: They frequently map reads to positions in the new reference that do not align well with the read sequence, particularly when large insertions exist in the new reference, resulting in error rates that exceed acceptable thresholds.
3. Incompatibility with Downstream Analyses: Many tools produce outputs (e.g., BED files or BAMs with erroneous CIGAR strings) that are incompatible with standard variant discovery pipelines such as GATK.

Methodology: AirLift

AirLift is a methodology and tool that provides a fast, comprehensive, and accurate end-to-end solution for BAM-to-BAM remapping. It leverages the similarity between two reference genomes to minimize the need for full alignment while ensuring that all reads are processed.

Core Concepts: Reference Genome Regions

AirLift divides regions between an old and a new reference genome into four types:

1. Conserved Regions: Sequences that are exactly identical in both references.
2. Updated Regions: Sequences in the old reference that map to similar (but not identical) sequences in the new reference.
3. Deprecated Regions: Sequences in the old reference that have no corresponding area in the new reference (deletions).
4. New Regions: Sequences in the new reference that have no corresponding area in the old reference (insertions).

The AirLift Index

The core of AirLift is a preprocessed AirLift Index, created via an eight-step process involving global alignment and seed extraction. This index consists of two lookup tables (LUTs):

• LUT for Conserved Regions: Maps exact matches between the old and new references.
• LUT for Updated Regions: Maps approximate matches (within a defined error rate) between the old and new references.

Crucially, the creation of the LUT for updated regions uses a conservative error rate of 2e (where e is the acceptable alignment error rate, typically 5%). This ensures that any read mapped to an updated region in the old reference with an error rate e will find a corresponding potential position in the new reference, even if the sequence difference between the two references is up to 2e.

Remapping Procedure

AirLift processes each read in a BAM file based on its original mapping position in the old reference:

1. Reads from Conserved Regions: If the read is mapped to a conserved region, AirLift uses the LUT for conserved regions (via a tool named FastRemap) to immediately transfer the coordinates to the new reference. No re-alignment is performed.
2. Reads from Updated Regions: If the read is mapped to an updated region, AirLift queries the LUT for updated regions to identify candidate positions in the new reference. It then performs a full alignment (using BWA-MEM) only against these specific candidate positions to find the best match within the error threshold e.
3. Reads from Deprecated Regions: If the read is mapped to a deprecated region, it is marked as unmapped in the new reference, as no corresponding sequence exists.
4. Previously Unmapped Reads: Reads that were unmapped in the old reference are fully aligned to the new and updated regions of the new reference genome using a full mapper (BWA-MEM).

This hybrid approach ensures that the majority of reads (those in conserved regions) are processed immediately, while only a small fraction requiring complex handling undergoes full alignment.

Key Contributions

• First Comprehensive BAM-to-BAM Remapper: AirLift is the first tool to offer an end-to-end solution that outputs BAM files compatible with downstream analysis tools (such as GATK) for all reads, including those in deprecated and new regions.
• High Accuracy: By using a conservative error rate of 2e during index creation and re-aligning reads in updated regions, AirLift avoids the high error rates associated with simple coordinate shifting.
• Speed: It significantly reduces execution time by avoiding full remapping for reads in conserved regions, which constitute the majority of the genome.

Results

The authors evaluated AirLift against state-of-the-art remapping tools (CrossMap, LiftOver) and the baseline of full remapping with BWA-MEM across human, C. elegans, and yeast reference genomes.

• Execution Time: AirLift achieves a speedup of 2.76× to 27.4× compared to full remapping. The speedup is highest for human genomes (up to 27.4× for hg17→hg38), where conserved regions are large, and lower for yeast, where conserved regions are smaller relative to the total genome.
• Accuracy (Variant Discovery): Using GATK HaplotypeCaller, AirLift demonstrates precision and recall for SNP and indel detection comparable to full remapping. For example, when remapping human reads from hg19 to hg38, AirLift achieved a precision of 97.05% and a recall of 96.39% for SNPs against the ground truth, compared to 97.73%/99.25% for full mapping.
• Completeness: Unlike CrossMap and LiftOver, which miss significant proportions of annotations (e.g., 4.47% of genes when lifting hg19 to hg38), AirLift processes the entire read set and ensures that no genomic regions are ignored.
• Memory Usage: The peak memory requirement of AirLift is comparable to full remapping (BWA-MEM), as it uses BWA-MEM for the portion of reads in updated regions, which still demands significant memory.

Significance

The work claims that AirLift is a viable, powerful alternative to full remapping for researchers updating genomic studies to new reference versions. By eliminating the need to re-run computationally intensive pipelines from scratch while maintaining high accuracy and completeness, AirLift enables the rapid adaptation of large-scale genomic datasets to the latest reference genomes. This is of particular importance given the increasing frequency of reference genome updates and the growing volume of genomic data, as it allows researchers to maintain current analyses without prohibitively high computational costs. The tool is open source and provides a complete BAM-to-BAM workflow enabling immediate downstream analysis.