Scientists create algorithm to help kidney transplants

Statistics from the Scientific Registry of Transplant Recipients reveal that nearly 78,000 patients throughout the U.S. are on the waitlist for receiving kidney transplants. Considering this dire state of affairs, a system that can match needy patients with available donors more efficiently is extremely necessary. Computer science professors Tuomas Sandholm and Avrim Blum, along with David J. Abraham, a graduate student in the computer science department, came up with an algorithm that is capable of efficiently matching donors to patients. Currently, newer versions of the algorithm are being developed by Sandholm and Pranjal Awasthi, a graduate student in the machine learning department.

Blum explained that a variety of factors decide whether a kidney donor and recipient are compatible with each other. Particularly, if the donor and recipient’s blood type and proteins of the group known as the major histocompatibility complex do not match, the recipient’s body will elicit a strong immune response against the transplanted organ. Hence, the donors and recipients have to be carefully matched for a successful transplant.

Usually, relatives of patients needing a transplant are willing to donate their kidneys, but, more often than not, these donors are not compatible with the patients. There may be many such incompatible donor-patient pairs. However, a donor from one pair may be able to donate his or her kidney to a patient from a second pair.

If the donor of the second pair is compatible with the patient of the first pair, both the donors can switch places and the required transplant operations can be performed as planned, albeit with different donor-patient pairs. This forms the basis of paired kidney donation.
With a database containing the results of preliminary compatibility tests of over 10,000 donor-patient pairs from all over the country, the donor-patient pairs can be matched with each other in a variety of ways.

The team at Carnegie Mellon decided to tackle the momentous task of developing an algorithm that performed the matching in a way that maximizes the number of patients who could receive transplants from the possible donors.

“There might be multiple ways one could do [the matching] and some of [the ways] might end up with more people getting kidneys,” Blum said. To explain this concept, Blum illustrated an example with four donor-patient pairs: A, B, C, and D. Suppose the donors of pairs A and B can be switched, and the donors of C and D can be switched, then the patient from each pair has a donor.

However, consider that the donors of B and C can also be switched, but those of A and D cannot. If the switch were performed between B and C without taking into account the presence of A and D, patients from A and D would be left without kidney transplants. The main purpose of the algorithm was to prevent something like this from happening.

“The idea was to get this large collection of people and then you could find the best possible ways of doing the matching,” Blum explained. Blum elaborated further by saying that the larger the pool of donor-patient pairs, the larger are the chances of finding good matches. Hence, the group wanted to come up with an algorithm that could be used for a very large group of people. “The challenge that we were going to solve was could we come up with procedures we could scale up to 10,000 [donor-patient groups],” Blum said.

Sandholm agreed that the issue of scaling the algorithm to such high numbers was the greatest challenge they faced, and perhaps also the reason why they took interest in solving the problem in the first place. “I was on the program committee of the International Congress of the Game Theory Society 2004.... We invited Al Roth to be a speaker there, and he talked about kidney exchange. Then it became clear that the algorithms solving who was going to give [kidneys] to whom weren’t scalable. So I decided that’s probably a place where computer scientists can help significantly,” Sandholm said.

Coming up with the algorithm was not that easy, and many changes had to be made to the originally developed algorithm. “In my lab by now, we’ve generated several generations of the algorithm,” Sandholm said. “Some of the newest improvements have to do with the dynamic aspects of the problem. New patients and donors are going to come in and the algorithm should be smart about how it handles [the new donor-patient pairs].” This is work that Sandholm did with Awasthi.
A consequence of the research was the development of Never Ending Altruistic Donor chains. In such cases, an altruistic donor, who is not paired with any patient, donates a kidney to a patient part of a donor-patient pair. The donor of the pair can then donate his or her kidney to the next donor-patient pair, whose donor can donate the kidney to the next pair, and so on. The chain terminates with one leftover kidney that can be used to initiate another such chain. As Sandholm put it, “It’s like a gift that keeps giving.”

As published in the March 12 edition of the New England Journal of Medicine, such a chain was recently started using the algorithm, and 10 people have successfully received transplants through the chain so far. The project has thus shown that it has great potential and can immensely help the medical community.
Although the current algorithm is being developed for kidney transplants only, Sandholm believes that this has a large impact, as kidney transplants are by far the most prevalent transplants. “If you work on kidneys, you can save as many lives as if you work on all other transplants combined,” he said.