Send to

Choose Destination
Bioinformatics. 2019 Jan 28. doi: 10.1093/bioinformatics/btz050. [Epub ahead of print]

GRIMM: GRaph IMputation and Matching for HLA Genotypes.

Author information

Center for Blood and Marrow Transplant Research, Minneapolis, MN, USA.
National Marrow Donor Program/Be The Match, Minneapolis, MN, USA.
Department of Pathology, Tulane University, New Orleans, LA, USA.
Department of Mathematics, Bar Ilan University, Ramat Gan , Israel.



For over 10 years allele-level HLA matching for bone marrow registries has been performed in a probabilistic context. HLA typing technologies provide ambiguous results in that they could not distinguish among all known HLA allele equences; therefore registries have implemented matching algorithms that provide lists of donor and cord blood units ordered in terms of the likelihood of allele-level matching at specific HLA loci. With the growth of registry sizes, current match algorithm implementations are unable to provide match results in real time.


We present here a novel computationally-efficient open source implementation of an HLA imputation and match algorithm using a graph database platform. Using graph traversal, the matching algorithm runtime is practically not affected by registry size. This implementation generates results that agree with consensus output on a publicly-available match algorithm cross-validation dataset.


The Python, Perl and Neo4j code is available at

Supplementary information:

Supplementary data are available at Bioinformatics online.

Supplemental Content

Full text links

Icon for Silverchair Information Systems
Loading ...
Support Center