Source-linked AI summary
Selscan: an efficient multi-threaded program to perform EHH-based scans for positive selection
Zachary A Szpiech, Ryan D Hernandez
TL;DR
Growing genomic datasets require faster implementations of haplotype-based scans for recent or ongoing positive selection. The paper presents selscan, a multi-threaded implementation of EHH, iHS, and XPEHH, and reports order-of-magnitude speedups while maintaining close agreement with existing programs.
Problem
Growing numbers of individuals and loci create a need for fast, efficient implementations of haplotype-based selection statistics.
Method
selscan implements EHH, iHS, and XPEHH using phased genotypes, genetic-map integration, normalization, and shared-memory parallelism across independently computed sites.
Results
At least an order-of-magnitude speedups over ihs and xpehh, and nearly 2x over rehh, were reported for large datasets, with close agreement in unstandardized scores.
Takeaways & Limitations
selscan supports genome-wide EHH-based scans and large-scale simulation studies on very large genetic datasets.
Takeaways & Limitations
The statistics require phased haplotypes and a genetic or physical map, and missing genotypes must be dropped or imputed.
Abstract
from arXiv · showhide
Haplotype-based scans to detect natural selection are useful to identify recent or ongoing positive selection in genomes. As both real and simulated genomic datasets grow larger, spanning thousands of samples and millions of markers, there is a need for a fast and efficient implementation of these scans for general use. Here we present selscan, an efficient multi-threaded application that implements Extended Haplotype Homozygosity (EHH), Integrated Haplotype Score (iHS), and Cross-population Extended Haplotype Homozygosity (XPEHH). selscan accepts phased genotypes in multiple formats, including TPED, and performs extremely well on both simulated and real data and over an order of magnitude faster than existing available implementations. It calculates iHS on chromosome 22 (22,147 loci) across 204 CEU haplotypes in 353s on one thread (33s on 16 threads) and calculates XPEHH for the same data relative to 210 YRI haplotypes in 578s on one thread (52s on 16 threads). Source code and binaries (Windows, OSX and Linux) are available at https://github.com/szpiech/selscan .
1 Introduction
selscan implements EHH-based statistics for detecting recent or ongoing positive selection, addressing the need for efficient analysis as genomic datasets expand. The paper defines the statistics and their calculations, including haplotype-homozygosity integration, normalization, and practical truncation rules.
- Extended Haplotype Homozygosity: EHH-based statistics use phased genotypes to identify putative regions of recent or ongoing positive selection under a hard-sweep model.The model predicts extended haplotype homozygosity when selection acts faster than recombination or mutation breaks up the haplotype.
- Motivation: The implementation responds to growing datasets by providing a fast and efficient publicly available approach to calculating these statistics.The paper evaluates selscan after introducing concise definitions of the statistics and their calculations.
- Extended Haplotype Homozygosity: EHH measures homozygosity among distinct haplotypes extending from a locus of interest to a marker, using observed haplotype counts.For core-haplotype analyses, the calculation is restricted to chromosomes carrying the selected core haplotype.
- Integrated Haplotype Score: iHS compares integrated haplotype homozygosity for ancestral and derived haplotypes by tracking EHH decay and integrating with trapezoidal quadrature.The unstandardized score uses upstream and downstream genetic distances, followed by genome-wide normalization in frequency bins.
- Practical calculation rules: EHH-based integrations use practical stopping and data-quality rules, including an EHH threshold of 0.05, gap scaling, chromosome-boundary checks, and a 0.05 minor-allele-frequency cutoff for iHS.Large gaps can abort an iHS calculation, while lower-density data receive distance scaling to reduce possible spurious signals.
- Cross-population Extended Haplotype Homozygosity: XPEHH calculates integrated haplotype homozygosity separately for two populations and compares the resulting values after genome-wide normalization.The integrations are truncated when pooled-population EHH falls below 0.05, with gap handling performed as for iHS.
2 Performance
selscan was evaluated on simulated and real genomic data for iHS and XPEHH, showing substantially faster runtimes while closely matching existing implementations.
- Evaluation design: selscan was compared with rehh, ihs, and xpehh using simulated datasets and the real CEU22 and CEUYRI22 datasets.The evaluations covered runtime and agreement of unstandardized scores.
- iHS performance: At least an order of magnitude faster than ihs, and up to 1.8x faster than rehh, selscan calculated iHS scores on large datasets using one thread.Runtime comparisons used genetic maps for ihs and selscan; rehh used a physical map.
- Score agreement: Pearson’s r = 0.9946 for CEU22 unstandardized iHS scores showed excellent agreement between selscan and ihs.The authors attributed slight score variance to an undocumented difference in ihs calculations and described its effect as negligible.
- XPEHH performance: At least an order of magnitude faster than xpehh, selscan calculated XPEHH scores using one thread.Table 2 summarizes runtimes across datasets with varying sample sizes.
- Score agreement: Pearson’s r = 0.9999 for CEUYRI22 unstandardized XPEHH scores showed strong agreement between selscan and xpehh.The comparison used the same real-data evaluation framework described for the runtime analysis.
3 Conclusions
selscan accelerates EHH-based scans through optimized calculations and multithreading, with computational costs that scale with sample number and SNP density.
- Conclusions: At least an order of magnitude faster than ihs and xpehh, and nearly 2x faster than rehh, selscan improved large-dataset runtimes through calculation optimizations.The reported speedups apply to large datasets.
- Conclusions: Multithreading partitions independent site-score calculations across threads while preserving access to the complete dataset.This shared-memory design targets computers with multiple cores.
- Conclusions: O(ND2) is the reported empirical complexity for rehh, ihs, and selscan, whereas xpehh is O(N 2D2).N denotes haploid sample number and D denotes SNP locus density.
- Conclusions: selscan requires phased haplotypes and a genetic or physical map in TPED format, with missing genotypes dropped or imputed.The authors position it for large whole-genome sequencing and GWAS datasets.
4 Acknowlegements
The authors acknowledge testing assistance and partial support from the National Institutes of Health and the Sloan Foundation.
- Acknowledgements: Trevor Pemberton and Paul Verdu assisted with testing the Windows binaries.The work was partially supported by multiple National Institutes of Health grants and a Sloan Foundation Research Fellowship.