Wait No More

Kidney Match Algorithm Saves Lives

The number of patients that have received life-changing kidney transplants continues to grow thanks to an algorithm devised by Carnegie Mellon computer scientists.

The kidney-matching algorithm was used to launch a chain of living kidney donations that was detailed in a report in the March 12 issue of the New England Journal of Medicine. Thus far, 10 people have received kidneys and the chain could still grow longer.

The kidney-matching algorithm was originally devised by Computer Science Professor Tuomas Sandholm, working with fellow Professor Avrim Blum and graduate assistant David J. Abraham, to increase paired donations.

These donations occur when someone is willing to donate a kidney, but is incompatible with the recipient. A paired donation becomes possible if doctors can find a compatible donor-recipient pair, so that donor A gives a kidney to recipient B, while donor B gives to recipient A.

"Computer memory is a limiting factor in optimizing kidney exchanges," Sandholm said, noting the large number of constraints, such as differing blood and tissue types, that must be considered.

"We work around this by using incremental problem formulation," he said.

That is, the algorithm doesn't consider all of the constraints at once, but formulates them in the computer's memory only as needed, enabling it to analyze up to 10,000 donor-patient pairs.

It has made three- and four-way matches possible, as well as increasing the length of donor chains initiated by altruistic donors. It's also scalable. One day, it could be used for a national pool of donors and recipients.

In fact, the United Network for Organ Sharing, which oversees U.S. organ transplants, has announced it is developing a national system for pairing living donors and recipients.

Homepage Story Archives