Kidney Exchange -- Computer Scientist Invents Software To Arrange Matches For Kidney Transplants

Kidney Exchange -- Computer Scientist Invents Software To Arrange Matches For Kidney Transplants

October 1, 2007 — Computer Scientists have created an algorithm able to sort through up to 10,000 kidney donor/patient pairs, taking over the mammoth task of coordinating paired donation. The new algorithm was needed to make the organization of 4 or 5 way swaps practical. This means that each patient is able to receive a kidney of the correct tissue type from a donor within one of the other pairs.

More than 70,000 Americans need a kidney transplant. Four-thousand will die this year waiting for a suitable organ to become available. But a revolutionary computer software program is matching live donors with those in need.
For the Repasky family, a healthy meal is one that's low in sodium. Marnie and Hal's sons have kidney disease.
"My oldest son has had two kidney transplants. My youngest son has had two transplants. We fully understand the need for organs and organ donation," mother Marnie Repasky says. Nineteen-year-old Nathan received his second kidney last year from his sister-in-law, Susan. The Repaskys are fortunate.
Many times, patients and loved ones willing to donate have blood or tissue types that don't match. When that happens, the incompatible donor and patient may agree to try paired kidney donation: donor A would give a kidney to patient B, while donor B would give a kidney to patient A. Transplant experts say paired donation is successful, but is often difficult to coordinate.
That's where computer scientist Tuomas Sandholm, from Carnegie Mellon University in Pittsburgh, Penn., makes a difference. Dr. Sandholm designed computer software that finds multiple matches.
"It's a very complex problem of deciding what kidney goes to whom," Dr. Sandholm says.
Algorithms already exist for two-way paired donation, but Dr. Sandholm's program keeps doing the math. It calculates the most efficient way to exchange the kidneys, resulting in multiple possible combinations. For example, donor A would donate to patient B, donor B would give a kidney to patient C, donor C would go to patient D, and so on -- up to four or five-way swaps, where the last donor would give an organ to patient A.
Sandholm's algorithm is already being used successfully -- last December, a network of 55 transplant centers began using the software.
"This really is the enabling technology to get a nationwide kidney exchange going."
For the thousands of families affected by kidney disease, it's welcome news.
"Time is such a precious commodity to everybody. But to somebody who needs a transplant, it's even more so," says kidney recipient Nathan Repasky.
Sandholm's algorithm can analyze 10,000 donor and patient pairs. He said existing algorithms were only able to handle data from 900 pairs.
The American Mathematical Society and the Mathematical Association of America contributed to the information contained in the TV portion of this report.


BACKGROUND: About 4,000 patients will die each year waiting for a kidney transplant. But a new number-crunching computer program developed at Carnegie-Mellon University could help match living donors with patients to save more lives. The biggest advantage of the new software is that it uses a new algorithm that enables more complicated matching by factoring in not just donors, but also the most efficient way to handle three and four way exchanges.
HOW IT WORKS: Many kidney disease patients receive a life-saving organ from a donor who has died -- a process managed by the United Network for Organ Sharing (UNOS). Other patients have living friends or family members willing to sacrifice a kidney -- a process managed by a local transplant center. But sometimes the family member's or friend's blood or tissue doesn't match the patient, so that particular donation isn't possible. So hospitals will then attempt to match a donor-patient pair with another willing pair with compatible blood or tissue. This is a typical two-way match. The more donor-patient pairs there are in a pool, the more complicated the matching process becomes. In a three-way match, Donor A gives a kidney to Patient B. Donor B gives a kidney to Patient C. And Donor C gives a kidney to Patient A.
Existing software can handle two-way exchanges for a large pool of donor-patient pairs, but those designed to arrange three- and four-way exchanges can only handle between 600 to 900 pairs. The CMU software, in contrast, can handle as many as 10,000 patient-donor pairs. There are other complicating factors. For instance, even after matching pairs are found, results of blood and tissue tests could make the donation unsuitable, and many transplant centers operate independently, reducing the number of potential pairs. The hope is that the UNOS will establish a national paired donation registry, providing an enormous pool of potential donors and patients for which the CMU software would be ideally suited.
ABOUT THE KIDNEYS: The kidneys are major organs whose function is to remove waste products and excess fluid from the body via the production of urine. In the process, they also regulate the body's salt, potassium and acid content, and produce hormones that affect the function of other organs, such as red blood cell production, or regulating blood pressure. There are two kidneys, each the size of a fist, located on either side of the spine at the bottom of the rib cage. Each kidney is made up of as many as a million functioning units called nephrons: a filtering unit of tiny blood vessels attached to a tubule. When blood enters the vessels in the unit, it is filtered and the remaining fluid passes through the tubule, where chemicals and water are either added or subtracted -- depending on the body's need at the time -- to eventually produce urine. The kidneys process about 200 quarts of fluid every 24 hours.