Graph-Based Imputation Methods and Their Applications to Single Donors and Families

Area of Science:

• Immunogenetics
• Computational Biology
• Transplantation Science

Background:

• Hematopoietic Stem Cell (HSCT) and organ transplant success heavily relies on Human Leukocyte Antigen (HLA) allele matching between donor and recipient.
• Low-resolution HLA typing and missing/ambiguous alleles necessitate accurate imputation methods for high-resolution haplotype determination.
• Existing imputation algorithms require predefined haplotype frequencies, necessitating a robust phasing step for both imputation and frequency generation.

Purpose of the Study:

• To develop novel algorithms for accurate HLA haplotype and genotype imputation.
• To improve HLA phasing and imputation by leveraging graph structures and incorporating multi-racial and familial information.
• To enhance HLA haplotype frequency estimation through cross-racial information sharing.

Main Methods:

• Developed a graph-based approach to explicate candidate HLA phases and resolve ambiguity using partial and consistent haplotypes.
• Introduced GRIMM (Graph Imputation and Matching) for HLA imputation, extended to MR-GRIMM (Multi-Race GRIMM) for combining multi-racial data.
• Proposed GRAMM (GRaph-bAsed faMily iMputation) for family pedigree data and MR-GRIMME (MR-GRIMM EM) integrating an expectation-maximization algorithm for haplotype frequency estimation.

Main Results:

• The developed algorithms (MR-GRIMM, GRAMM, MR-GRIMME) demonstrated significantly improved accuracy over existing methods.
• MR-GRIMM achieved high accuracy in matching predictions, while GRAMM excelled in imputing family members with minimal phasing errors.
• MR-GRIMME provided higher likelihoods for haplotype frequency estimation compared to current algorithms, effectively sharing information across races.

Conclusions:

• Novel graph-based algorithms offer substantial improvements in HLA imputation accuracy and haplotype frequency estimation.
• The integration of multi-racial and familial data enhances imputation performance, crucial for diverse donor pools and family-based studies.
• These tools (MR-GRIMM, MR-GRIMME, GRAMM) are available as accessible servers and standalone versions, facilitating broader application in transplantation and genetic research.