HapTagger

HapTagger identifies tag single nucleotide polymorphisms (SNPs) using a haplotype-based framework to solve the Minimum Tagging Multihaplotype (MTMH) problem by selecting a minimal subset of SNPs that predict alleles of untyped SNPs.

Key Features:

• Haplotype-Based Framework: Uses haplotypes rather than individual SNPs to capture predictive relationships among variants across loci.
• Problem Decomposition: Decomposes the MTMH problem into three subproblems, two of which are NP-hard, and addresses them with exact and approximation algorithms.
• Efficiency and Performance: Identifies a smaller set of tag SNPs with improved computational efficiency and without requiring linkage disequilibrium (LD) statistics.
• Reconstruction Algorithm: Implements a specialized algorithm to infer alleles of untyped SNPs from the predictive haplotypes.
• Comparative Analysis: Benchmarks on real datasets and reports improved performance relative to existing methods, including Haploview (the HapMap project's official tagging tool).

Scientific Applications:

• Genetic Research: Enables large-scale genetic association and mapping studies by minimizing the number of genotyped tag SNPs required.
• Evolutionary Studies: Uses predictive haplotypes as signatures for recent positive selection or co-evolution.

Methodology:

The MTMH problem is decomposed into three subproblems (two NP-hard) and solved using a combination of exact and approximation algorithms, and a reconstruction algorithm is applied to infer alleles of untyped SNPs from haplotypes.