Carnegie Mellon Computer Method Enables National Pool of Donor-Recipient Pairs

PITTSBURGH-A man in St. Louis and a woman in New Hampshire have received the first kidney transplants made possible through a new national program of the Organ Procurement and Transplantation Network (OPTN) that uses a Carnegie Mellon University computer algorithm to match transplant candidates with living donors.

Both recipients - Ken Crowder of St. Louis and Kathy Niedzwiecki of Pelham, N.H. - had loved ones who were willing to donate a kidney but who were medically incompatible with them. So, through a paired donation, Mr. Crowder's fiancée, Rebecca Burkes, donated her kidney to Ms. Niedzwiecki and Ms. Niedzwiecki's sister-in-law, Cathy Richard of Henniker, N.H., donated her kidney to Mr. Crowder. The donor recovery and transplant operations took place Dec. 6 at Barnes-Jewish Hospital in St. Louis and Dartmouth-Hitchcock Medical Center in Lebanon, N.H.

The matches were identified during a computer run Oct. 27 that considered 43 transplant candidates and 45 donors. It was the first match run of the OPTN pilot program, which is expected to increase the number of kidney paired-donation (KPD) transplants by creating a national pool of mismatched donor-recipient pairs. The United Network for Organ Sharing (UNOS) operates the OPTN under federal contract.

"It is gratifying to know that this pilot program has helped make these transplants possible," said Tuomas Sandholm, a professor of computer science at Carnegie Mellon who has led the development of computer algorithms for optimizing match runs. "As the size of the pool increases, we are confident that we can significantly boost the number of patients who are able to receive kidney transplants. The more people in the pool, the higher the portion of them we can save."

"Paired donation is helping the transplant community help people who otherwise could not get a living donor transplant. We're proud to be able to coordinate these for the first time using a national network for potential matches among 77 participating transplant programs," said Charles Alexander, OPTN/UNOS president.

Alexander said the Carnegie Mellon algorithm and Sandholm's expert advice were important parts of the pilot program. "These contributions have helped us develop the program more quickly and at significantly lower cost than we could have achieved otherwise, so we can focus on saving and enhancing lives through kidney paired-donation," he explained.

Smaller, existing kidney exchanges, which take these incompatible donor-recipient pairs and match them with other donor-recipient pairs, already have increased the number of KPD transplants. In the last three years, exchanges have enabled more than 700 kidney transplants that otherwise would not have occurred. Two of those exchanges have used the Carnegie Mellon computer algorithm to match pairs.

"The goal of the pilot project is to see whether combining the data of multiple centers and networks will generate successful matches that may not be found through one individual organization," Alexander said. "The fact that these transplants occurred from the first match run suggests this will be true."

Examining all of the possible combinations of two- and three-way exchanges between the donor-recipient pairs is a massive computational task. The first algorithm that could solve this problem optimally on a nationwide scale - a projected 10,000 pairs in the pool - was developed in 2006 by Sandholm, Computer Science Professor Avrim Blum and then-graduate student David J. Abraham. The algorithm has since been further refined by Sandholm and Ph.D. students Pranjal Awasthi, Erik Zawadzki and John Dickerson.

The optimization problem places a huge demand on computer memory, Sandholm said. Therefore, the algorithm never writes down the entire problem in the computer's memory. It nevertheless finds an optimal solution by formulating into memory only those parts of the problem that turn out to be relevant.

Future match runs will be conducted every four to five weeks with information on potential living donors and candidates supplied by pilot participants. Each transplant program will make individual medical decisions about accepting living donors or candidates and whether they qualify for matching through the pilot program. In addition, each program must document that potential living donors have undergone a rigorous medical screening and have provided detailed informed consent for donation and for potential participation in a national match run.

The need to increase the efficiency of kidney exchanges is compelling. The demand for donor organs - more than 86,000 people are now on the kidney waiting list - far exceeds supply. Last year, 28,463 people received kidney transplants, with 6,609 of those kidneys coming from living donors.

In addition to OPTN funding, the pilot project has been made possible by charitable support and in-kind donations from Carnegie Mellon, Sandholm, the New England Program for Kidney Exchange, EDS Consulting, Sommer Gentry and numerous private charitable foundations.

Work by Sandholm's team has been supported by the National Science Foundation and by the CMU Center for Computational Thinking, which in turn is supported by Microsoft Research.