Most parsimonious haplotype allele sharing determination

Zhipeng Cai, Hadi Sabaa, Yining Wang, Randy Goebel, Zhiquan Wang, Jiaofen Xu, Paul Stothard, Guohui LinBMC Bioinformatics 2009 · OpenReview

TL;DR

This paper introduces two novel algorithms, iLinker and xPedPhase, for accurately and efficiently determining haplotype allele sharing status in pedigree genotype data. This is crucial for improving the power and interpretability of genome-wide association studies (GWASs), especially for complex quantitative traits, by reducing statistical degrees of freedom and capturing the combined effects of linked genetic variants.

What Problem Does This Paper Address?

Genome-wide association studies (GWASs) have been successful in identifying genetic variants associated with diseases, but their power, particularly for quantitative traits, remains limited. A promising strategy to enhance GWASs is to use haplotypes, which are blocks of linked single nucleotide polymorphisms (SNPs), to better capture the correlation structure of the genome and the combined effects of causal variants. However, accurately determining haplotype allele sharing status among individuals in a pedigree is a significant challenge. This paper addresses the need for robust methods to unambiguously determine this sharing status, which is essential for unlocking the full potential of haplotype-based association studies.

Methods

The authors present two distinct parsimonious haplotyping algorithms:

  • iLinker: This algorithm is based on a rule-based, greedy approach. It repeatedly runs a haplotyping algorithm on the smallest nuclear families within a pedigree, aiming to minimize the total number of crossover breakpoints required to explain the genotype data. It can handle missing genotype data and has an error correction step.
  • xPedPhase: This method extends the PedPhase algorithm. It focuses on identifying maximal zero-recombination chromosomal regions and then determines haplotype allele sharing within these regions. Its objective is to minimize the number of crossover sites, or equivalently, the number of maximal zero-recombination chromosomal regions. This approach aims for a more parsimonious representation of haplotype sharing.

Both methods aim to deterministically and accurately infer haplotype allele sharing status, even for small pedigrees.

Datasets

The study utilizes simulated genotype data for evaluation. The simulations are based on:

  • Real, unrelated chromosome 1 genotype data: Obtained from GeneChip Human Mapping 10 K Xba and 50 K Xba arrays.
  • Simulated pedigrees: Ten pedigrees of two or three generations, with sizes ranging from 4 to 13 individuals, were used.
  • Simulated mutation regions: For case-control association study simulations, specific "mutation regions" were assigned to simulate disease inheritance patterns.

The study generated 500 simulated 10 K genotype datasets and 500 simulated 50 K genotype datasets for comprehensive testing.

Key Insights and Ideas

  • Parsimony is key: Both algorithms prioritize parsimony in explaining the observed genotype data, either by minimizing breakpoints (iLinker) or by minimizing the number of zero-recombination regions (xPedPhase). This parsimonious approach is crucial for robust inference.
  • Haplotype sharing is determinable: The study demonstrates that, even with medium-density SNP data and in the presence of missing data (for iLinker), haplotype allele sharing status can be determined with high accuracy in pedigrees.
  • SNP density matters: Higher SNP density (50K vs. 10K) generally leads to improved performance in both breakpoint recovery and haplotype allele sharing recovery, highlighting the benefit of dense marker data.
  • iLinker's robustness: iLinker's ability to handle missing genotype data and its error correction step make it a more robust choice in real-world scenarios where data imperfections are common.
  • xPedPhase's precision: xPedPhase, while computationally more intensive and less tolerant of missing data, offers a slightly more parsimonious determination of shared regions, which can be advantageous.

Key Results

  • Breakpoint Recovery: Both iLinker and xPedPhase achieved high precision and recall in breakpoint recovery. For 10K datasets, iLinker averaged 98.4% precision and 96.4% recall, while xPedPhase achieved 91.2% precision and 97.8% recall. On 50K datasets, xPedPhase achieved 95.7% precision and 98.3% recall, and iLinker achieved 99.6% precision and 97.2% recall.
  • Mutation Region Recovery: xPedPhase demonstrated slightly higher mutation region recovery accuracies (97.2% on 10K, 99.0% on 50K) compared to iLinker (95.4% on 10K, 98.8% on 50K).
  • Shared Region Recovery: The correlation coefficients between simulated and discovered shared regions were very high (e.g., 0.99981 and 0.99989 for xPedPhase on 10K data), indicating excellent recovery.
  • Missing Data Impact: iLinker showed good performance even with up to 3% missing genotype data, with only a slight drop in recall.
  • Computational Cost: iLinker ran in seconds, while xPedPhase could take minutes to hours, especially for larger regions or denser data, posing a computational challenge.

Limitations and Future Work

  • Computational Complexity of xPedPhase: The cubic time complexity of the underlying zero-recombination haplotyping algorithm in xPedPhase limits its scalability to very large chromosomal regions or datasets. The authors suggest implementing a linear-time algorithm for zero-recombination haplotyping as a future direction.
  • Missing Data Tolerance: xPedPhase does not tolerate missing genotype data or errors, unlike iLinker.
  • Simulation Artifacts: The simulation process for mutation regions could lead to situations where a "diseased" allele is not unique, making it difficult for any algorithm to recover.
  • Future Work: The authors envision extending their programs for use in quantitative trait locus (QTL) identification and quantitative association studies, particularly in species with less dense SNP arrays like cattle and soybean. They also aim to develop a novel linear-time zero-recombination haplotyping algorithm.

Summary updated

Abstract

Background The "common disease – common variant" hypothesis and genome-wide association studies have achieved numerous successes in the last three years, particularly in genetic mapping in human diseases. Nevertheless, the power of the association study methods are still low, in particular on quantitative traits, and the description of the full allelic spectrum is deemed still far from reach. Given increasing density of single nucleotide polymorphisms available and suggested by the block-like structure of the human genome, a popular and prosperous strategy is to use haplotypes to try to capture the correlation structure of SNPs in regions of little recombination. The key to the success of this strategy is thus the ability to unambiguously determine the haplotype allele sharing status among the members. The association studies based on haplotype sharing status would have significantly reduced degrees of freedom and be able to capture the combined effects of tightly linked causal variants. Results For pedigree genotype datasets of medium density of SNPs, we present two methods for haplotype allele sharing status determination among the pedigree members. Extensive simulation study showed that both methods performed nearly perfectly on breakpoint discovery, mutation haplotype allele discovery, and shared chromosomal region discovery. Conclusion For pedigree genotype datasets, the haplotype allele sharing status among the members can be deterministically, efficiently, and accurately determined, even for very small pedigrees. Given their excellent performance, the presented haplotype allele sharing status determination programs can be useful in many downstream applications including haplotype based association studies.
BibTeX
@article{cai2009most,
  author = {Zhipeng Cai and Hadi Sabaa and Yining Wang and Randy Goebel and Zhiquan Wang and Jiaofen Xu and Paul Stothard and Guohui Lin},
  title = {{Most parsimonious haplotype allele sharing determination}},
  journal = {BMC Bioinformatics},
  year = {2009},
  url = {https://openreview.net/forum?id=T3VQhomzxN},
}
Figure