The graph theory provides an interesting approach in finding compatible donors through kidney exchange programs.
Kidney exchanges were established in the past decade to solve a problem affecting thousands of people with kidney disease: They have a loved one willing to donate a kidney, but the two have incompatible blood or tissue types. Organized in a clearinghouse or exchange, however, incompatible pairs can trade with each other, forming cycles in which each patient needing a kidney receives one from the donor of a different pair. Cycles have to be short—usually two or three pairs—because the transplants must be done simultaneously so each pair donating a kidney knows for certain it will receive one in return.
But if a donor comes forward who is not part of a pair, the potential for more life saving transplants arises. Because each pair can receive a kidney before donating one, the transplants do not have to be done simultaneously. What is the best way to use the kidney of an altruistic donor so that the greatest number of patients get transplants?
To answer this question, we gathered data from a kidney exchange clearinghouse. Included was detailed information about patients’ blood and tissue types, which told us how hard it would be to find matches for them. We analyzed the data using the tool of graph theory, an approach used in mathematics and computer science to understand relationships among pairs of objects.
We found that long chains and long cycles of donations are essential to helping the greatest number of patients. This is especially true for patients whose blood or tissue types make them difficult to match. The percentage of hard to match patients in kidney exchange programs is very high since easy to match patients can often find a donor without the aid of the exchange program (even when enrolling the program they can be matched quickly while hard to match patients accumulate over time). But lengthy chains will benefit hard to match patients while not harming easy to match patients who are in kidney exchange programs, we found.
Read the full article.
Keywords: Graph Theory • Kidney Transplant • Medicine