Valuing Sets of Potential Transplants in a Kidney Paired Donation Network

KPDGUI: An interactive application for optimization and management of a virtual kidney paired donation program

BACKGROUND AND OBJECTIVES

The aim in kidney paired donation (KPD) is typically to maximize the number of transplants achieved through the exchange of donors in a pool comprising incompatible donor-candidate pairs and non-directed (or altruistic) donors. With many possible options in a KPD pool at any given time, the most appropriate set of exchanges cannot be determined by simple inspection. In practice, computer algorithms are used to determine the optimal set of exchanges to pursue. Here, we present our software application, KPDGUI (Kidney Paired Donation Graphical User Interface), for management and optimization of KPD programs.

METHODS

While proprietary software platforms for managing KPD programs exist to provide solutions to the standard KPD problem, our application implements newly investigated optimization criteria that account for uncertainty regarding the viability of selected transplants and arrange for fallback options in cases where potential exchanges cannot proceed, with intuitive resources for visualizing alternative optimization solutions.

RESULTS

We illustrate the advantage of accounting for uncertainty and arranging for fallback options in KPD using our application through a case study involving real data from a paired donation program, comparing solutions produced under different optimization criteria and algorithmic priorities.

CONCLUSIONS

KPDGUI is a flexible and powerful tool for offering decision support to clinicians and researchers on possible KPD transplant options to pursue under different user-specified optimization schemes.

An efficient algorithm to enumerate sets with fallbacks in a kidney paired donation program

Kidney paired donation is a partial solution to overcoming biological incompatibility preventing kidney transplants. A kidney paired donation (KPD) program consists of altruistic or non-directed donors (NDDs) and pairs, each of which comprises a candidate in need of a kidney transplant and her/his willing but incompatible donor. Potential transplants from NDDs or donors in pairs to compatible candidates in other pairs are determined by computer assessment, though various situations involving either the donor, candidate, or proposed transplant may lead to a potential transplant failing to proceed. A KPD program can be viewed as a directed graph with NDDs and pairs as vertices and potential transplants as edges, where failure probabilities are associated with each vertex and edge. Transplants are carried out in the form of directed cycles among pairs and directed paths initiated by NDDs, which we refer to respectively as cycles and chains. Previous research shows that selecting disjoint subgraphs with a view to creating fallback options when failures occur generates more realized transplants than optimal selection of disjoint chains and cycles. In this paper, we define such subgraphs, which are called locally relevant (LR) subgraphs, and present an efficient algorithm to enumerate all LR subgraphs. Its computational efficiency is significantly better than the previous, more restrictive, algorithms.