First Kidney Transplants Using New Matching Algorithm

A man in St. Louis and a woman in New Hampshire have received the first kidney transplants through a new computer algorithm that matches transplant candidates with living donors.

The program is run by the Organ Procurement and Transplantation Network. It uses an algorithm developed at Carnegie Mellon University. The matches were identified during a computer run Oct. 27 that considered 43 transplant candidates and 45 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.

It was the first match run of the OPTN pilot program, which is expected to increase the number of kidney paired donation transplants by creating a national pool of mismatched donor-recipient pairs.

In paired donation, the 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.

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.

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 the computer algorithms. 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, he said in a statement.

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, in a statement.

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 paired donation 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 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 demand for donor organs far exceeds supply. More than 86,000 people are now on the kidney waiting list. Last year, 28,463 people received kidney transplants, with 6,609 of those kidneys coming from living donors.