Calculation of IBD probabilities with dense SNP or sequence data

Jonathan M. Keith, Allan F. McRae, David L. Duffy, Kerrie Mengersen, Peter M. VisscherGenetic 2008 · DOI

TL;DR

This paper introduces a novel, computationally efficient method for calculating Identity by Descent (IBD) probabilities using dense SNP or sequence data. By modeling founder haplotypes as a Markov chain and incorporating genotyping error detection, their approach significantly outperforms existing tools like Merlin in speed and scalability, while maintaining comparable accuracy, especially for future large-scale genomic studies.

What Problem Does This Paper Address?

Accurately estimating the probability that two individuals share 0, 1, or 2 alleles identical by descent (IBD) at specific genetic locations is crucial for identifying genes associated with diseases and quantitative traits. Historically, genetic markers were sparse enough that researchers could assume alleles at different locations were independent (in linkage equilibrium). However, the explosion of high-throughput genotyping technologies, particularly dense Single Nucleotide Polymorphism (SNP) arrays and the upcoming era of individual genome sequencing, generates vast amounts of data. Existing algorithms struggle with this density, either becoming computationally intractable or yielding inaccurate IBD estimates due to unaddressed linkage disequilibrium (LD) between closely spaced markers. This paper tackles the challenge of developing a method that can handle this dense data efficiently and accurately, accounting for the reality of LD and potential genotyping errors.

Methods

The core innovation lies in a new model for founder haplotypes, treating them as a Markov chain. This means the allele at a given locus is probabilistically dependent on the allele at the previous locus, effectively capturing linkage disequilibrium (LD) within founder populations. This is a departure from previous methods that often assumed independence.

Key methodological components include:

  • Markov Chain for Founder Haplotypes: Instead of assuming independence, the model uses a Markov chain to describe the probabilities of allele transitions along a haplotype. This allows for the modeling of LD.
  • Incorporation of Genotyping Errors: The model explicitly includes a two-parameter error model that accounts for the possibility of observed genotypes differing from true genotypes. This is a significant advantage, as it allows the algorithm to detect likely errors.
  • Linear Scaling Algorithm: The computational time and memory requirements of their algorithm scale linearly with the number of markers. This is a critical improvement over existing methods like Merlin, which scale supralinearly, making them impractical for whole-genome dense data.
  • Dynamic Programming: Similar to the Lander-Green algorithm, their method utilizes dynamic programming for efficient computation.

Datasets

The paper evaluates their method using three datasets:

  • Data Set 1: Simulated Sibling Genotypes: Real parental haplotypes from the International HapMap Project (chromosome 7) were used to simulate sibling genotypes. This dataset allowed for direct comparison with known IBD status.
  • Data Set II: Simulated Individual Sequencing: A large-scale simulation using the ms program generated data mimicking the scale expected from individual sequencing projects (1,000 parental haplotypes, over 1 million markers). This dataset was crucial for testing scalability.
  • Data Set III: Australian Twins: SNP genotype data from 169 Australian families (specifically, a pair of dizygotic twins from chromosome 15) was used. This dataset, while less dense, demonstrated the impact of LD even in moderately sized datasets.

Key Insights and Ideas

  • LD is Not Optional for Dense Data: The results strongly confirm that ignoring linkage disequilibrium (LD) in founder haplotypes can lead to significant errors in IBD probability calculations, especially as marker density increases.
  • Genotyping Errors are Detectable: The explicit inclusion of a genotyping error model is a powerful feature, allowing the algorithm to flag potential errors that might otherwise lead to misinterpretations of IBD status.
  • Scalability is Paramount: The linear scaling of their algorithm is a game-changer for future genomic studies. Existing methods simply cannot cope with the sheer volume of data from whole-genome sequencing.
  • Markov Chains Capture LD Effectively: Modeling founder haplotypes as a Markov chain provides a computationally feasible way to capture LD, achieving accuracy comparable to more complex methods.

Key Results

  • Speed: The new algorithm (MCIBD) was orders of magnitude faster than Merlin with clusters. For Data Set II, MCIBD ran in ~9.5 hours, while Merlin with clusters was terminated after 150 hours without producing output. Even compared to Merlin without clusters, MCIBD was faster (~4 min vs. ~7 min on Data Set I).
  • Accuracy: MCIBD achieved accuracy comparable to Merlin with clusters, particularly in correctly assigning high probabilities to true IBD states. While Merlin with clusters showed slightly superior performance in some specific analyses (e.g., Figure 3), MCIBD's performance was still very strong and significantly better than Merlin without accounting for LD.
  • Scalability: MCIBD scales linearly with the number of markers, whereas Merlin scales supralinearly. This is demonstrated by the successful analysis of over a million markers in Data Set II.
  • Genotyping Error Detection: In Data Set III, the algorithm identified a region with likely genotyping errors where other methods struggled to assign a consistent IBD status.

Limitations and Future Work

  • Markov Model vs. Block Model: The authors acknowledge that their Markov model for LD might not capture long-range LD as effectively as Merlin's cluster-based block model. They suggest that improving accuracy might involve incorporating more complex dependencies or exploring higher-order Markov chains.
  • Pedigree Size: The current implementation is described for nuclear families with two offspring, though it's stated to be generalizable. Future work includes extending the method to larger pedigrees, potentially using Markov Chain Monte Carlo (MCMC) approaches.
  • Sequencing Error Fluctuations: For future whole-genome sequencing data, they plan to account for variations in sequencing error rates that might depend on sequence context (e.g., repetitiveness, nucleotide composition).
  • Interleaving Markov Chains: Exploring the use of multiple, interleaved Markov chains with transition probabilities calculated for non-adjacent markers is another avenue for future research.

Summary updated

Abstract

The probabilities that two individuals share 0, 1, or 2 alleles identical by descent (IBD) at a given genotyped marker locus are quantities of fundamental importance for disease gene and quantitative trait mapping and in family-based tests of association. Until recently, genotyped markers were sufficiently sparse that founder haplotypes could be modelled as having been drawn from a population in linkage equilibrium for the purpose of estimating IBD probabilities. However, with the advent of high-throughput single nucleotide polymorphism genotyping assays, this is no longer a reasonable assumption. Indeed, the imminent arrival of individual sequencing will enable high-density single nucleotide polymorphism genotyping on a scale for which current algorithms are not equipped. In this paper, we present a simple new model in which founder haplotypes are modelled as a Markov chain. Another important innovation is that genotyping errors are explicitly incorporated into the model. We compare results obtained using the new model to those obtained using the popular genetic linkage analysis package Merlin, with and without using the cluster model of linkage disequilibrium that is incorporated into that program. We find that the new model results in accuracy approaching that of Merlin with haplotype blocks, but achieves this with orders of magnitude faster run times. Moreover, the new algorithm scales linearly with number of markers, irrespective of density, whereas Merlin scales supralinearly. We also confirm a previous finding that ignoring linkage disequilibrium in founder haplotypes can cause errors in the calculation of IBD probabilities.
BibTeX
@inproceedings{keith2008calculation,
  author = {Jonathan M. Keith and Allan F. McRae and David L. Duffy and Kerrie Mengersen and Peter M. Visscher},
  title = {{Calculation of IBD probabilities with dense SNP or sequence data}},
  booktitle = {Genetic},
  year = {2008},
  doi = {10.1002/gepi.20324},
}
Figure