Kidney Matchmaking

A new method of matching patients and donors could make transplants possible for thousands more

People are born with two kidneys but need only one to survive. That can be a blessing for those with two failed kidneys, because sometimes they can receive a donated kidney from a family member. But the good fortune can turn bitter: a third of the time, the donor and the recipient aren’t a compatible match.

Each node in these graphs represents an incompatible donor-recipient pair. In the left-hand graph, lines show all possible links for which the donor of each pair is a good match for the recipient in the other pair. The right-hand graph shows which choices of links would provide the maximum number of transplants. Gentry
The numbers in the circles represent the degree of importance that a particular patient receives a kidney. The numbers on the lines connecting the circles denote the quality of each match. Gentry
In this graph, choosing the link between the two middle nodes gives the maximum edge value (3), but not the maximum number of links. Choosing the two outside links gives the maximum number of links (2), but not the maximum edge value (2). Gentry
This image gives an example of how Gentry’s team solved the problem of maximizing both the quality and the quantity of matches. They assigned each link a high value to begin with and then added small values to distinguish superior matches. Now the two outer links have the maximum edge value as well as being the maximum number of links. Gentry
Try it yourself! Each node in this graph represents an incompatible donor-recipient pair, and the links between them show possible matches in which each donor is compatible with the opposite recipient. Can you find the maximum number of matches? How about the minimum? We’ll post the answer here in a couple of weeks, or, for a flash version of the puzzle, hints, and instant answers, go to . Adapted from Stanford University School of Engineering

One solution is to arrange a kind of surgical double-date. When two donor-recipient pairs are in the same predicament of incompatibility, it can happen that the donor of one pair is a good match for the recipient of the other, and vice versa. Doctors and lawmakers are working to create a national database of kidney donation pairs that could vastly improve the chances of finding such matches.

Multiple transplants involving more than two pairs are possible, and have occasionally been performed, but the complex logistics of such procedures ensure that they can happen only rarely. But even matching up two pairs raises difficult questions about how to find the matches. A new mathematical study shows how to match up the maximum number of donors with recipients while simultaneously guaranteeing high compatibility in each case.

Finding the best matches is a complex task. Doctors tend to consider some patients higher priority than others. For example, although dialysis allows most patients to survive after their kidneys have failed, patients who cannot be treated with dialysis will die without a transplant. If a patient had donated a kidney when healthy, a sense of justice calls for that patient to receive one when sick. Doctors also favor giving higher priority to children.

Furthermore, some matches are better than others. Donor and recipient must have compatible blood types and sufficient immunological compatibility for a transplant to be possible. But in addition, there are degrees of immunological compatibility: the better the match, the longer a transplanted kidney is likely to keep working. Another consideration is that transplants are least expensive and easiest on doctors and families when the donors and patients live near one another, so that all the surgeries can take place in the same locality.

Graph theory can address the problem of matching up donor-recipient pairs. The nodes of a graph represent incompatible donor-recipient pairs, and two nodes are linked if the donors of each pair are matches for the recipients of the other pair. The nodes are given weights according to patient priority, and the links are given weights to represent the quality of the match.

In the 1960s, graph theorists developed a method for finding the greatest possible number of matches in a graph. Another method can do the same thing while maximizing the value of the matched nodes, which in this case means giving kidneys to the highest-priority patients.

But maximizing the value of the edges—not just the matched nodes—can result in fewer matches, sometimes only half as many. That means it has not been clear how to choose the most compatible matches while at the same time maximizing the number of transplants.

Sommer Gentry and T. S. Michael, mathematicians at the United States Naval Academy in Annapolis, Md., and Dorry Segev, a transplant surgeon at Johns Hopkins University in Baltimore, have now solved that problem. They have developed a method of weighting the edges to identify the most compatible matches while also guaranteeing the selection of a maximum number of matches.

Gentry expects that if there were a national registry in place for kidney matching, and if it used her team’s method, then each month, about half the pairs in the registry would find a compatible match. Each year, 1,000–2,000 patients would get kidneys who currently would not.

By contrast, as of 2005, only 51 patients had ever received kidneys through a swap in which two incompatible pairs exchange donors to create compatible pairs. Gentry calculates that developing a national registry could save $750 million per year, because dialysis, the only alternative to transplantation, is very expensive.

Gentry and her colleagues originally developed the weighting method in 2005 and published it in the Journal of the American Medical Association. Now, they have proved that their method always works—that is, it maximizes the total number of transplants while selecting matches with greater compatibility and closer proximity. Gentry presented their results Aug. 4 at MathFest 2007 in San Jose, California.

Gentry hopes that her research will help build support for a national registry for kidney pair matching.

“To me, these results are not important until they’re implemented,” she says. “This theoretical work shows that these allocations can be done in a sane way, and if we’re smart about it, we might get a large number of additional transplants in a year.”

If you would like to comment on this article, please see the blog version.

More Stories from Science News on Math

From the Nature Index

Paid Content