"A unified nationwide exchange can yield significantly better solutions than multiple separate exchanges, and it is extremely rewarding that after we have worked on this for six years, the nationwide program is now live," said Tuomas Sandholm, a Carnegie Mellon professor of computer science who has led the development of computer algorithms for optimizing match runs.

The pilot program's initial computer run on Oct. 27 successfully matched seven people who need kidney transplants with medically compatible individuals who agreed to donate a kidney. Two of the seven candidates were highly sensitized because of previous exposure to donor antigens, which can make it particularly difficult to find donors with compatible tissue types.

"We are grateful both for Dr. Sandholm's expert consulting in developing our national pilot program and for the use of Carnegie Mellon's algorithm," said OPTN/UNOS President Charles Alexander. "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.

"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.

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 explained. 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.

In the pilot phase of the nationwide program, 77 living kidney donor transplant programs are participating. Each is affiliated with one of four coordinating centers — the University of Toledo's Alliance for Paired Donation, Johns Hopkins Hospital, New England Program for Kidney Exchange and the UCLA Medical Center/California Pacific Medical Center.Computerized matching will be performed every four to five weeks with information on potential living donors and candidates supplied by participating transplant programs. Each transplant program must document that potential donors have completed a rigorous medical screening and evaluation process, and that they have provided detailed informed consent for donation and for potential participation in a national match run.

"In the future, kidney exchanges could be made even better by using our newest generation of algorithms that consider not only the current problem but also anticipate donors and patients who might later join the system," Sandholm said.

"It can sometimes be best to wait on some of the transplants so that more or better transplants can be found as new pairs enter the system. Our new algorithms figure that out automatically using statistical properties of the blood- and tissue-type distribution of the population to generate possible sequences of additional pairs joining."

Source-Eurekalert