SuperDCA for genome-wide epistasis analysis

Santeri Puranen, Maiju Pesonen, Johan Pensar, Ying Xu, John A. Lees, Stephen D. Bentley, Nicholas J. Croucher, Jukka Corander, Erik AurellbioRxiv 2017 · DOI

TL;DR

This paper introduces SuperDCA, a novel computational method that significantly scales Direct Coupling Analysis (DCA) to analyze millions of genetic polymorphisms across entire bacterial genomes. SuperDCA enables the discovery of previously hidden epistatic interactions, providing new insights into bacterial evolution and adaptation without requiring phenotypic data.

What Problem Does This Paper Address?

Understanding how genetic variations interact (epistasis) is crucial for deciphering complex biological systems. Direct Coupling Analysis (DCA) has shown promise in identifying these interactions, particularly in protein structures and bacterial genomes. However, existing DCA methods struggle to handle the vast number of genetic polymorphisms (up to 10^5) found in bacterial genomes. This limitation prevents a comprehensive, genome-wide analysis of epistatic interactions, hindering our ability to understand evolutionary pressures and biological mechanisms at a systems level. The challenge lies in developing a computationally efficient and scalable method that can analyze these massive datasets to uncover subtle but biologically significant interactions.

Methods

The core innovation is SuperDCA, a significantly optimized and parallelized implementation of DCA based on the Potts model. Key advancements include:

  • Efficient Parameter Scoring: A new scoring principle is employed to speed up the calculation of interaction parameters.
  • Optimized C++ Code: Highly optimized and parallelized open-source C++ code is utilized.
  • Elimination of Subsampling: Unlike previous methods that relied on computationally intensive polymorphism subsampling, SuperDCA directly handles large numbers of polymorphisms.
  • Scalability Architecture: A new computational architecture exploits efficient parallelization and optimization to achieve scalability for up to 10^5 polymorphisms.
  • Phylogenetic Filtering: A refined version of phylogenetic ranking is used to filter out spurious couplings, focusing on biologically meaningful interactions and mitigating issues related to clonal inheritance and sampling bias.
  • Novel Data Structures: Space-efficient, block-wise ordered data structures and cache-friendly memory layouts are implemented to address memory bottlenecks and improve cache utilization.

Datasets

The study utilizes two large population samples of Streptococcus pneumoniae:

  • Maela population: Two variants were used: one with only bi-allelic SNPs (81045 loci, 3145 samples) and another with no restriction to bi-allelic sites (94028 loci, 3042 samples).
  • Massachusetts population: 78731 SNP loci were analyzed from 670 samples.

These datasets are publicly available and represent some of the largest bacterial population genomic datasets.

Key Insights and Ideas

  • Uncovering Hidden Interactions: SuperDCA can identify significant epistatic interactions that are missed by previous methods, including those that are not detectable by genome-wide association analysis (GWAS).
  • Beyond Phenotypic Data: The method demonstrates the power of inferring biological signals from genetic variation alone, without the need for phenotypic measurements.
  • Co-evolutionary Pressures: The analysis reveals how different populations experience distinct co-evolutionary pressures, potentially driven by ecological factors like antibiotic usage.
  • Systems Biology Potential: SuperDCA offers a powerful tool for understanding complex biological systems at a global level, applicable to a wide range of organisms.

Key Results

  • Scalability: SuperDCA achieves an 18-fold performance increase over earlier methods on a single compute node, enabling inference of 1.4*10^11 parameters for a 94028 SNP dataset in under 8 days, compared to an estimated 170 days for previous methods.
  • Biological Discoveries: The analysis of Streptococcus pneumoniae revealed novel insights into:
  • Antibiotic Resistance: Identified strong couplings between penicillin-binding protein (PBP) genes (pbp2x, pbp2b, pbp1a), suggesting co-evolutionary mechanisms in antibiotic resistance.
  • Cold Tolerance and Transmission: Discovered significant epistatic links between cold resistance genes (rnr, glpF1, lytC) and identified seasonal patterns in allele frequencies, suggesting a link between cold tolerance and transmission seasonality.
  • Improved Filtering: The phylogenetic ranking effectively filters out noise and highlights biologically relevant couplings, showing a clear shift in mutual information for PBP-related couplings.
  • GWAS Complementarity: SuperDCA can uncover signals of selection not detectable by GWAS, providing a complementary approach to understanding adaptation.

Limitations and Future Work

  • Computational Limits: While SuperDCA is highly scalable, analyzing entire bacterial genomes with 10^6 sites will still require further computational strategies to manage the quadratic increase in complexity.
  • Future Research: The authors suggest investigating how Potts model inference can be performed reliably for even larger datasets without a quadratic increase in complexity. They also highlight the potential for SuperDCA to provide vital clues for evolutionary processes under different ecological conditions in natural populations, warranting further experimental work to elucidate the mechanistic roles of coupled variations.

Summary updated

Abstract

Abstract The potential for genome-wide modeling of epistasis has recently surfaced given the possibility of sequencing densely sampled populations and the emerging families of statistical interaction models. Direct coupling analysis (DCA) has earlier been shown to yield valuable predictions for single protein structures, and has recently been extended to genome-wide analysis of bacteria, identifying novel interactions in the co-evolution between resistance, virulence and core genome elements. However, earlier computational DCA methods have not been scalable to enable model fitting simultaneously to 10 4 -10 5 polymorphisms, representing the amount of core genomic variation observed in analyses of many bacterial species. Here we introduce a novel inference method (SuperDCA) which employs a new scoring principle, efficient parallelization, optimization and filtering on phylogenetic information to achieve scalability for up to 10 5 polymorphisms. Using two large population samples of Streptococcus pneumoniae , we demonstrate the ability of SuperDCA to make additional significant biological findings about this major human pathogen. We also show that our method can uncover signals of selection that are not detectable by genome-wide association analysis, even though our analysis does not require phenotypic measurements. SuperDCA thus holds considerable potential in building understanding about numerous organisms at a systems biological level. Author Summary Recent work has demonstrated the emerging potential in statistical genome-wide modeling to uncover co-selection and epistatic interactions between polymorphisms in bacterial chromosomes from densely sampled population data. Here we develop the Potts model based approach further into a fully mature computational method which can be applied to most existing bacterial population genomic data sets in a straightforward manner. Our advances are relying on more efficient parameter scoring, highly optimized and parallelized open source C++ code, which does not rely on the computation-intensive polymorphism subsampling approximations used earlier. By analyzing the two largest available population samples of Streptococcus pneumoniae (the pneumococcus), we highlight several biological discoveries related to the survival of the pneumococcus and co-evolution of penicillin-binding loci, which were not uncovered by the earlier analyses. Our method holds considerable potential for building understanding about numerous organisms at a systems biological level.
BibTeX
@misc{puranen2017superdca,
  author = {Santeri Puranen and Maiju Pesonen and Johan Pensar and Ying Xu and John A. Lees and Stephen D. Bentley and Nicholas J. Croucher and Jukka Corander and Erik Aurell},
  title = {{SuperDCA for genome-wide epistasis analysis}},
  year = {2017},
  doi = {10.1101/182527},
  howpublished = {bioRxiv},
}
Figure