The growing list of people in need of a new kidney might get a little shorter, thanks to an unlikely source: that old, formidable puzzle in mathematics known as The Traveling Salesman Problem. That puzzle, and the methods used to solve it, have inspired an algorithm that can help pinpoint better matches, researchers report.
Kidney transplants, first performed in the 1950s, depend on either a living relative or the very recently deceased. Getting a kidney from a living donor is the better of the two options, but tracking down a viable donor among one’s friends and relatives isn’t always possible. Some simply don’t want to donate, or maybe aren’t healthy enough for the surgery. Others may be willing and able, but antibodies in their blood don’t match the patient’s well enough—a strong indicator a recipient’s immune system will reject the donated kidney.
Kidney transplants, first performed in the 1950s, depend on either a living relative or the very recently deceased. Getting a kidney from a living donor is the better of the two options, but tracking down a viable donor among one’s friends and relatives isn’t always possible.
To solve that problem, doctors began looking for transplant cycles and chains. The latter begins with a living person donating a kidney to another, often a stranger. A friend or relative connected to that recipient then donates to another stranger, and the process continues. (A cycle is just a chain that ends with a recipient connected to the first donor.) There are now registries set up specifically to facilitate cycles and chains, but actually finding the best chains—those that seek out the most compatible donor-recipient matches, while taking into account factors like how sick someone is or how long they’ve waited for a new kidney—remains a challenging technical problem.
Researchers from a variety of disciplines have been grappling with this challenge for a while, but haven’t had much luck in finding any particularly great solutions. To seek a better one, Ross Anderson, a recent graduate of MIT’s Operations Research Center, led a team that zeroed in on the Traveling Salesman Problem as inspiration. The classic problem is for a salesperson to find the shortest route that visits each city on a list just once—not quite the kidney exchange problem. But another version, the prize-collecting traveling salesman problem, is closer. In that version, the salesperson doesn’t have to make it to each city, but there’s a reward for each city he or she does get to.
That, Anderson and company reasoned, was a lot like the kidney transplant chain problem, in that one wants to find the longest possible chain of kidney patient-donor pairs without the impractical requirement that everyone who needs a kidney gets one on the first go. From there, the team adapted a known algorithm for solving the PC-TSP to the kidney exchange problem, able to obtain the longest possible transplant chains in real data from two kidney exchange programs, something previous approaches had been unable to do reliably, using just a desktop personal computer.
Along with another method the team developed, the new algorithm is already in use in kidney exchange programs, “including Methodist Specialty and Transplant Hospital in San Antonio, Texas, and the Northwestern University Medical Center in Chicago,” the authors write.
