Algorithm Matches Kidneys More Efficiently

An algorithm developed by a computer scientist at Carnegie Mellon University could drastically improve the efficiency of matching kidney donors to recipients, and save lives in the process.

Tuomas Sandholm, a professor of computer science, designed a program that takes pairs of donors and recipients and checks them against other pairs. The algorithm then checks to see if the people in the pairs are a better match for people in the next pair. For example, in a situation with two pairs, donor A might not be a good match for recipient A, but a better match for recipient B. Meanwhile, donor B might be a better match for recipient A.

The algorithm also works with chains of people, in which a person who wants to give a kidney is matched with another donor-recipient pair. The person who was donating a kidney in the original pair gives their kidney to someone else (who is presumably a better match), and on down the line.

The national Organ Procurement and Transplantation Network, operated by the United Network for Organ Sharing (UNOS), began a national pilot program using this algorithm to increase the number of kidney paired-donation transplants. Such transplants involve a living donor who wants to give a kidney, rather than donations from people who have died. Some 6,600 kidneys were transplanted this way last year, out of a total of 24,000 transplants.

Often, those people who want to donate kidneys don't have anyone to donate to, as a recipient has to have the right tissue type. Outside of close relatives such people are not easy to find, so access to a pool of possible recipients makes the whole process more efficient.

Doing this with hundreds or thousands of donors and recipients would be nearly impossible without a computer. Even with one, it turns out to be a complicated problem, Sandholm says.

The number of pairs one can include in each set, as well as people in the chains, is limited, he adds. The reason is that the way kidney transplants are performed, the recipient or donor might have to travel to have the operation, and the kidney can't be outside of the body for long. We have doctors on cell phones saying they are performing the operation now, he said.

That means that any more than three pairs would be logistically difficult to do -- as it is, once people in a group of three donor-recipient pairs are matched, a total of six operating rooms have to be booked. On top of that, just before the surgery a donor's and recipient's blood has to be tested. The blood is mixed and if it coagulates then the kidney isn't a good enough match. The surgery is then called off.

But even with that limitation, having thousands of people in the pool of pairs makes it much easier to find matches between organs and donors.

While the pilot program only involves less than a hundred people, but eventually it will include thousands. Having a nationwide pool of people will make it that much easier to match pairs, Sandholm says, because the odds of finding a compatible kidney are so small to begin with.

About 87,000 people are waiting for a kidney, according to the Organ Procurement and Transplant Network. By making it easier to match the donor-recipient pairs the efficiency of the process is increased, and that could cut waiting times, which currently average about three years.

Sandholm says he has been working on the problem for the last six years. The matching problem originally came from an interest he had in markets in which goods are exchanged via barter, rather than money. The first version of the kidney program was completed in 2006, and he has been refining it since then.