- Computer Algorithm Matches Kidney Donors with Those in Need
- A newly developed computer algorithm is building a network of people in need of kidneys and potential donors. The technology could increase the number of kidney transplants, thereby saving thousands of lives per year.By the end of 2009, there were over 86,000 people on the waitlist to receive a kidney donation. According to the Scientific Registry of Transplant Recipients, that waitlist has been increasing steadily each year, while the number of donors has remained relatively constant. Now, a computer algorithm developed by researchers at Carnegie Mellon University is matching transplant recipients with potential living donors. The technology, being used to create a national network, could save lives and lower the risks of organ rejection.
Kidneys for transplants can be either from living or deceased donors. Most people on the waitlist do not have compatible family members and are waiting for organs from deceased donors. But organs from living donors have higher success rates, since they are often closer matches to recipients' blood and tissue type, and the organs do not need to be transported over long distances.
Now, the Organ Procurement and Transplantation Network (OPTN), operated by the United Network for Organ Sharing (UNOS), is using a computer algorithm to match kidney recipients with potential donors. Using the technology, the OPTN has started a national pilot program to increase the number of kidney paired-donation (KPD) transplants.
Although the waitlist for kidneys continues to grow each year, the number of transplant surgeries has remained relatively constant (source: OPTN/SRTR).Matching possible donors with recipients is a huge computational task. In 2006, the first algorithm that could successfully perform the equations on a nationwide scale—that is, with up to 10,000 pairs—was created by Tuomas Sandholm and Avrim Blum, both professors of Computer Science at Carnegie Mellon, and then-graduate student David J. Abraham. The algorithm has since been improved by Sandholm, with help from Ph.D. students Pranjal Awasthi, Erik Zawadzki and John Dickerson.
The main technological problem was computer memory, which could not handle the huge demand of the matching process. To circumvent this difficulty, the researchers' algorithm never records the entire process within the computer's memory. Instead, it only records those parts of the process that turn out to be relevant.
In a trial run, the process included only 43 kidney transplant candidates and 45 potential living donors. Researchers expect, however, that this national KPD network could eventually be expanded to include up to 20,000 individuals.
In many situations, a potential kidney donor—usually a family member—is not medically compatible with the intended recipient. Blood and tissue samples must match; otherwise an organ has a high risk of rejection, which could lead to infection and even death.
With the new technology, the computer creates new potential pairs based on medical information. A two-way exchange, for example, might match the donor from one pair with the recipient from the second, with the second donor donating to the first recipient. The algorithm is even capable of determining three-way exchanges.
As the national network grows, the chances of finding a potential match will increase.
"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 Sandholm in a statement. Sandholm led the team of researchers in the development of the computer algorithms that finds organ matches.
On Oct. 27, a trial run of the program successfully matched seven donor-recipient pairs. The technology even found matches for two kidney recipients with particularly rare 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 Charles Alexander, pesident of OPTN/UNOS. "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 computerized matching process will be performed every four to five weeks, as participating transplant programs supply new patient and potential donor information.
"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."