EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

Fast and Memory-Efficient Dynamic Programming Approach for Large-Scale EHH-Based Selection Scans

Amatur Rahman iD, T Quinn Smith iD, Zachary A Szpiech iD

Molecular Biology and Evolution · 29.10.2025 · 42 (11)

DOI: 10.1093/molbev/msaf275 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Molecular Biology and Evolution, online erschienen am 27.10.2025. Verfasst von Amatur Rahman und 2 weiteren Autor:innen. Beteiligte Einrichtung: Department of Biology, The Pennsylvania State University, University Park, PA 16802, USA. Hauptthemen laut MEDLINE: Haplotypes, Homozygote, Selection, Genetic. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 40 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0). Gefördert von: NIGMS NIH HHS, National Institute of General Medical Sciences.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Haplotype-based statistics are widely used for finding genomic regions under positive selection. At the heart of many such statistics is the computation of extended haplotype homozygosity (EHH), which captures the decay of homozygosity away from a focal site. This computation, repeated for potentially millions of sites, is computationally demanding, as it involves tracking counts of unique haplotypes iteratively over long genomic distances and across many individuals. Because of these computational challenges, existing tools do not scale well when applied to large-scale population datasets, such as the 1,000 Genomes Project, or the UK Biobank with 500,000 individuals. Optimizing computation becomes crucial when data sets grow large, especially when handling large sample sizes or generating training data for machine learning algorithms. Here, we propose a dynamic programming algorithm that substantially improves runtime and memory usage over existing tools on both real and simulated data. On real phased data, we achieve 5–50x speedup with minimal memory footprint. Our simulations show an even more pronounced performance gap with large populations (up to 15x speedup and 46x memory reduction). EHH-based statistics designed for unphased genotypes run an order of magnitude faster, and multi-parameter support results in 20x runtime improvement. Source code and binaries are available at https://github.com/szpiech/selscan as selscan v2.1.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

HaplotypesHomozygoteSelection, GeneticHumansAlgorithmsSoftwareComputer SimulationModels, GeneticDynamic Programming

Stichwörter der Autor:innen

haplotypespopulation geneticspositive selectionsoftware

Autor:innen und Institutionen

  • Department of Biology, The Pennsylvania State University, University Park, PA 16802, USA.

ORCID-Profile: Amatur Rahman, T Quinn Smith, Zachary A Szpiech

Förderung

  • NIGMS NIH HHS
  • National Institute of General Medical Sciences

Zitieren

APA

Rahman, A., Smith, T. Q., & Szpiech, Z. A. (2025). Fast and Memory-Efficient Dynamic Programming Approach for Large-Scale EHH-Based Selection Scans. Molecular Biology and Evolution, 42(11). https://doi.org/10.1093/molbev/msaf275

Vancouver

Rahman A, Smith TQ, Szpiech ZA. Fast and Memory-Efficient Dynamic Programming Approach for Large-Scale EHH-Based Selection Scans. Molecular Biology and Evolution. 2025;42(11). doi:10.1093/molbev/msaf275

BibTeX
@article{Rahman2025,
  author = {Rahman, Amatur and Smith, T Quinn and Szpiech, Zachary A},
  title = {Fast and Memory-Efficient Dynamic Programming Approach for Large-Scale EHH-Based Selection Scans},
  journal = {Molecular Biology and Evolution},
  year = {2025},
  volume = {42},
  number = {11},
  doi = {10.1093/molbev/msaf275}
}
Kostenlos starten →