New Algorithm Increases Transplants


This step-by-step method, or algorithm, developed at Carnegie Mellon University could significantly boost the efficiency of kidney exchanges, a mechanism for matching live donors with unrelated recipients. Kidney exchanges are now considered the best chance for boosting the number of kidney transplants.

The matching algorithm makes it possible to create matches for three- and four-way exchanges — that is, three or four donors matched to three or four recipients — as well as two-way exchanges. It is the first that is scalable so it can be used for a national pool of donors and recipients, said Tuomas Sandholm, professor of computer science at Carnegie Mellon University. A kidney exchange program for 50 transplant centres in 15 states began using the matching algorithm. The director, Dr. Michael Rees of the University of Toledo Medical Center, said it improves on previous methods both by including three- and four-way exchanges and by factoring in so-called altruistic donors — kidney donors without a specified recipient.

For instance, in a match run in early May, the algorithm identified four potential two-way exchanges, three three-way exchanges and one four-way exchange among about 100 donor-patient pairs and seven altruistic donors. Whether any of those transplants take place will depend on factors such as final compatibility testing, Rees said. With the same set of donor-patient pairs and without altruistic donors, the matching method previously used would have identified only one two-way exchange, he added.

“Computer memory is a limiting factor in optimising kidney exchanges,” Sandholm said, noting the large number of constraints, such as differing blood and tissue types, that must be considered. “We work around this by using incremental problem formulation,” he said. That is, the algorithm devised at Carnegie Mellon doesn’t consider all of the constraints at once, but formulates them in the computer’s memory only as needed, enabling it to analyse up to 10,000 donor-patient pairs.

COMPAMED.de; Source: Carnegie Mellon University