GRIMM-II: A Two-Stage Real-Time Algorithm for Nine-Locus HLA Imputation and Matching with Up to Three Mismatches

GRIMM-II is a scalable, real-time, two-stage algorithm that enables efficient nine-locus HLA imputation and the identification of hematopoietic stem cell donors with up to three mismatches, significantly expanding the pool of suitable candidates for transplantation while maintaining high accuracy and computational speed.

The Gist

Imagine you are trying to find a perfect key to open a very special, complex lock. This lock is the human immune system, and the "key" is a donor's tissue type (called HLA) for a life-saving stem cell transplant.

For decades, doctors only looked at five specific teeth on the key to see if it fit. If the teeth matched perfectly, the transplant worked. If they didn't, the patient's body would reject the new cells, or the new cells would attack the body (a dangerous condition called Graft-versus-Host Disease).

However, finding a perfect match is like finding a needle in a haystack, especially for people from diverse ethnic backgrounds. In recent years, doctors have realized that keys with a few slightly bent teeth (mismatches) can still work, especially if they use special medicine (like cyclophosphamide) to calm the immune system down. They can even tolerate up to three "bent teeth" instead of demanding a perfect match.

The problem? The old computer programs used to search for donors were built for the "perfect match only" era. They were too slow and too rigid to scan millions of donors to find those "good enough" keys with up to three mismatches, especially when looking at nine different teeth on the key instead of just five.

Enter GRIMM-II: The Super-Organized Librarian

The authors of this paper created a new, super-fast computer system called GRIMM-II. Think of it as a highly organized, super-smart librarian who can instantly find the right books (donors) in a library with 8 million books (donors), even if you only remember a few words of the title.

Here is how it works, using simple analogies:

1. The Two-Stage Search (The "Filter" and the "Deep Dive")

Imagine you are looking for a specific person in a massive crowd of 8 million people.

• Old Way: You walk up to every single person, ask their full name, birthday, and address, and check if they match your description. This takes forever.
• GRIMM-II Way:
  • Stage 1 (The Filter): You shout out just three key features (e.g., "Wears a red hat, has blue eyes, and is tall"). The librarian instantly filters the crowd down to a small group of 50 people who fit those three criteria. This is the "blocking" stage. It's fast and throws out the obvious mismatches.
  • Stage 2 (The Deep Dive): The librarian then quickly checks the full details of just those 50 people to see if they are the exact match or a "good enough" match (with up to 3 differences).
  • Result: Instead of checking 8 million people, they only check 50. This happens in 1 to 13 seconds.

2. The "Broken Key" Logic (GvH vs. HvG)

This is the most clever part of the new system.

• Old Logic: If the donor has a tooth the patient doesn't have, that's a mismatch. If the patient has a tooth the donor doesn't have, that's also a mismatch. The old computers just added these up. If there was one "extra" tooth on the donor and one "missing" tooth on the donor, the computer said: "2 Mismatches! Too risky!"
• GRIMM-II Logic: The authors realized that biologically, it matters which way the mismatch goes.
  • GvH (Donor vs. Patient): The donor's immune cells attacking the patient.
  • HvG (Patient vs. Donor): The patient's immune cells attacking the donor.
  • The Insight: If a donor has one "extra" tooth and the patient has one "missing" tooth, the total biological risk isn't necessarily double. It might just be a single direction of risk. GRIMM-II calculates these separately and takes the maximum risk, rather than the sum.
  • The Result: This reveals that many donors previously rejected as "2 mismatches" are actually safe "1 mismatch" candidates. This opens the door to thousands of new donors for patients who previously had no options.

3. The "Missing Teeth" Problem (Imputation)

Sometimes, a patient's medical records are incomplete. Maybe they only know 3 of the 9 teeth on their key.

• The Challenge: How do you find a match if you don't know the full key?
• The Solution: GRIMM-II uses a "probability map" based on the patient's ethnicity. It's like a detective who knows that if someone has a red hat and blue eyes, they are 90% likely to also have brown hair. The system fills in the missing teeth with the most likely options, creating a "best guess" key to search for.

Why Does This Matter?

1. Speed: It finds donors in seconds, even in a database of 8 million people.
2. More Options: By accepting up to 3 mismatches and using the smarter "directional" math, it finds many more donors than before.
3. Fairness: This is a game-changer for people from minority ethnic groups. Because their specific "key teeth" combinations are rarer in the global pool, they often couldn't find a perfect match. GRIMM-II expands the pool so significantly that these patients finally have a real chance of finding a donor.

In a nutshell: GRIMM-II is a new, lightning-fast search engine for life-saving transplants. It stops looking for "perfect" keys and starts finding "good enough" keys, using smart shortcuts to scan millions of people in the blink of an eye, giving hope to patients who were previously told they had no match.

Technical Summary

1. Problem Statement

Hematopoietic stem cell transplantation (HSCT) success relies heavily on Human Leukocyte Antigen (HLA) compatibility. While traditional matching focuses on five classical loci (HLA-A, -B, -C, -DRB1, -DQB1), clinical practice is shifting toward nine-locus typing (adding DPA1, DQA1, DPB1, and DRB3/4/5) and accepting up to three HLA mismatches, particularly under Post-Transplant Cyclophosphamide (PTCy) regimens.

Current donor search algorithms face three critical limitations:

1. Scalability: Existing graph-based methods (like the original GRIMM) cannot handle the memory and computational load of nine-locus imputation and matching due to the combinatorial explosion of haplotype phases.
2. Rigidity: Most algorithms are optimized for perfect (10/10) or near-perfect matches, often excluding viable donors with 1–3 mismatches.
3. Symmetry Bias: Traditional methods often sum mismatches per locus, failing to distinguish between Graft-versus-Host (GvH) and Host-versus-Graft (HvG) directions, which have distinct biological implications.

2. Methodology: GRIMM-II

The authors propose GRIMM-II, a suite comprising two novel algorithms: ML-GRIM (Multi-Locus GRaph IMputation) and ML-GRMA (Multi-Locus GRaph Matching). Both utilize a two-stage approach combining graph-theoretic candidate reduction with detailed genotype comparison.

A. ML-GRIM (Imputation)

• Goal: Impute full nine-locus genotypes from partial or ambiguous typing (GL-string format).
• Two-Stage Process:
  1. Blocking Stage: Selects a subset of highly polymorphic loci (e.g., A, B, DRB1). It applies the classical GRIM algorithm to this subset to generate a list of candidate genotypes consistent with these three loci. This drastically reduces the search space.
  2. Verification Stage: The remaining typed loci are checked against the candidates generated in the first stage. Only genotypes consistent with all typed loci are retained.
• Efficiency: By limiting the initial graph traversal to three loci, the algorithm avoids the memory bottleneck of storing all possible nine-locus haplotype combinations.

B. ML-GRMA (Matching)

• Goal: Identify donors with up to three mismatches in real-time.
• Graph Structure:
  • Donor Graph: Contains donor IDs connected to their imputed genotypes. Genotypes are partitioned into Class I (A, B, C) and Class II (remaining loci).
  • Subclass Vertices: To enable rapid mismatch detection, the algorithm creates "subclass" vertices by removing one allele from a class (e.g., a Class I genotype with only 5 alleles instead of 6).
• Two-Stage Matching Process:
  1. Candidate Reduction: For a patient, the algorithm imputes their genotype and extracts their subclass vertices. It queries the donor graph for matching subclass vertices. If a donor shares a subclass vertex with the patient, that donor is a candidate.
  2. Detailed Comparison: The full genotypes of the remaining candidates are compared allele-by-allele to verify the mismatch count is $\le 3$.
• Asymmetric Mismatch Calculation:
  • Calculates GvH (alleles in patient absent in donor) and HvG (alleles in donor absent in patient) separately.
  • Defines the total mismatch count as $\max(\text{Total GvH}, \text{Total HvG})$. This is less conservative than summing mismatches per locus, acknowledging that a single mismatch in one direction does not necessarily imply a mismatch in the other.

3. Key Contributions

1. Real-Time Nine-Locus Processing: GRIMM-II is the first algorithm capable of performing nine-locus imputation and matching with up to three mismatches in real-time (typically <1 second for imputation, 1–13 seconds for matching) on databases exceeding 8 million donors.
2. Memory-Efficient Graph Framework: The introduction of a "blocking" stage and the partitioning of genotypes into Class I/II with subclass vertices allows the system to fit large-scale data into memory, overcoming the limitations of previous graph-based methods.
3. Novel Mismatch Metric: The algorithm introduces a biologically grounded mismatch definition ($\max(\text{GvH}, \text{HvG})$) rather than a simple sum, identifying significantly more suitable donors, especially those homozygous at specific loci.
4. Open Source Implementation: The tools are released as a web application (GRIMMARD) and Python libraries (py-graph-imputation, py-graph-match), supporting dynamic registry updates.

4. Results and Validation

The algorithms were validated using the WMDA3 (World Marrow Donor Association) benchmark dataset and simulated data from the NMDP registry (8,078,224 US donors).

• Accuracy:
  • WMDA3: Reproduced 100% of previously reported matches and probabilities (within rounding error) for 5-locus data.
  • Simulated Mismatches: Tested on 3,000 patients with artificially introduced 0–3 allele substitutions. The algorithm achieved 100% sensitivity and specificity in identifying donors at the expected mismatch levels.
  • Imputation: Successfully imputed genotypes across variable typed loci, with accuracy correlating to the mutual information between typed and untyped loci.
• Performance:
  • Imputation Time: <1 second per typing.
  • Matching Time: 1–2 seconds for 5 loci; 1–13 seconds for 9 loci on an Intel i7 CPU.
  • Scalability: Maintained performance even when searching databases >8 million donors.
• Donor Pool Expansion:
  • Identified substantially more potential donors than traditional algorithms by utilizing the new mismatch definition and avoiding the trimming of low-probability haplotypes.
  • Found that ~30% of mismatched pairs had different GvH and HvG counts, a nuance missed by symmetric scoring.
  • Demonstrated that for most patients, a large pool of 3-mismatch donors exists, whereas 0- and 1-mismatch donors are scarce, especially for underrepresented ethnic minorities.

5. Significance

GRIMM-II addresses a critical gap in contemporary transplantation practice by enabling the systematic exploration of the "mismatched donor" space.

• Clinical Impact: It facilitates the identification of suitable donors for patients from underrepresented ethnic minorities, who historically face low probabilities of finding perfect matches.
• Future-Proofing: The modular, graph-based architecture allows for dynamic updates as new donors are registered and can easily accommodate additional loci or evolving clinical criteria (e.g., T-cell epitope matching).
• Paradigm Shift: By validating the feasibility of up to three mismatches in real-time, the tool supports the clinical shift toward more flexible matching strategies that utilize post-transplant cyclophosphamide to mitigate GvHD risks.

In summary, GRIMM-II transforms HLA matching from a rigid, perfect-match search into a dynamic, probabilistic, and real-time process capable of handling the complexity of nine-locus typing and multi-mismatch scenarios.