The Math Of Organ Donation

[Webster]

Ars Technica: The Math Of Organ Donation

We're bilaterally symmetric organisms—we've got matching bits on our left and right side. But many critical organs are present in only a single copy (hello heart) or we need both to function optimally (see: lungs). The kidneys are rare exceptions, as your body gets by just fine with only a single one. That has enabled people to become living kidney donors, with both the donor and recipient continuing life with one kidney.

Often, in cases where someone needs a transplant, there is a relative willing to make this sacrifice but is unable to do so because they aren't a close enough tissue match (which would lead to the organ's rejection by its new host's immune system). Separately, there are some rare individuals who are simply willing to donate a kidney to an unknown recipient. So the medical community has started doing "donation chains," where a group of donor-recipient pairs are matched so that everyone who receives a kidney has a paired donor that gives one to someone else.

That, as it turns out, has created its own problem: given a large pool of donors and recipients, how do you pull a set of optimized donor chains out? It turns out that the optimization belongs to a set of mathematical problems that are called NP-hard, making them extremely difficult to calculate as the length of the chain goes up. But now, some researchers have developed algorithms that can solve the typical challenges faced by hospitals with the processing power of a desktop computer.

The typical donor chain generated by hospitals starts with an unconnected donor, someone who's just willing to give up a kidney to anyone who needs it. From there, it goes through donor-recipient pairs, before ending at someone who doesn't have a paired donor. The longer the chain, the better the chances are of optimizing matches among donors and recipients so that there's a minimal chance of immune rejection.

The authors of the new paper try two different computational approaches for optimizing the chains. The first involves what are termed "integer programming" techniques, which are exactly what they sound like: the values used by the system to handle values for things like the suitability of a match and the amount of time spent waiting for an organ. Using this approach, they simply start with an unmatched donor and recurse through potential chains, checking for how optimal they are.

Separately, they note that the kidney donor problem is just a specialized case of what's called the prize-collecting traveling salesman problem. In this version, a person has to visit as many cities on a list as possible, but can skip some at the cost of a penalty. Using a modification of an algorithm designed for the traveling salesman, they implement one that is specialized for kidney donations.

They decided not to test this using historic data, given that medical records are biased toward containing people who have been successfully matched. So, they looked at a large pool of potential donors and recipients. In general, the traveling-salesman algorithm worked better than recursion and was able to produce answers in a reasonable amount of time on a desktop computing system, even when the potential length of the chain was unlimited.

With just a few hundred donor-recipient pairs at a time, the kidney donor problem isn't the sort of challenge we typically think of when we consider NP-hard problems. But it's nice to know the math that we've worked out while exploring those problems can be useful, as the authors' algorithms have already been adopted by a number of hospital systems.

Thoughts?

 

[Nebulous]

Interesting. We should have two hearts and 4 kidneys.

 

[Webster]

Interesting. We should have two hearts and 4 kidneys.

Now, now, let's not... *looks around* ...let's not give Justice any ideas for future conspiracy theories, m'kay?

 

[Nebulous]

Interesting. We should have two hearts and 4 kidneys.

Now, now, let's not... *looks around* ...let's not give Justice any ideas for future conspiracy theories, m'kay?

Lol. That'll happen regardless.

 

[Webster]

Interesting. We should have two hearts and 4 kidneys.

Now, now, let's not... *looks around* ...let's not give Justice any ideas for future conspiracy theories, m'kay?

Lol. That'll happen regardless.

Ohhh...forgot about that.

 

[Nebulous]

So what do you think about this article Web?

 

[Webster]

So what do you think about this article Web?

Its' an interesting look at the dilemma of organ donation; basically, how do you decide who gets what within the limitations of medicine at present?

 

[Nebulous]

So what do you think about this article Web?

Its' an interesting look at the dilemma of organ donation; basically, how do you decide who gets what within the limitations of medicine at present?

Ever seen the movie "The Island" ?

 

[Webster]

So what do you think about this article Web?

Its' an interesting look at the dilemma of organ donation; basically, how do you decide who gets what within the limitations of medicine at present?

Ever seen the movie "The Island" ?

Yeah, I've seen it...thankfully, we ain't at that point yet.

 

[Nebulous]

Yeah. Maybe we are? You never know whats underneath the endless miles of nothingness in the mid west.

 

[Webster]

Yeah. Maybe we are? You never know whats underneath the endless miles of nothingness in the mid west.

That's true...I mean, there's just endless miles and miles of--; oooh! Shiny things!