Problem
Definition

Kidney transplantation has emerged as the treatment for
the most serious forms of kidney disease. However, there is
a considerable shortage of donor kidneys in the U.S.: more
than 80;000 patients are on the waiting list for transplants
by the end of 2010. In the real world clinical application,
deceased donation and living donation are the two resources
of organs for kidney transplantation, and livingdonor transplant
has a higher chance of success. Unfortunately, about
onethird of patients with willing live donors will be excluded
from kidney transplantation because of ABO blood
type mismatch or HLA incompatibility. Therefore, KPD program is established as
a promising clinical solution to overcome the shortage of
donors. The essential idea of such program is to exchange
living kidney donors between two willing but incompatible donorrecipient pairs. The fundamental question in the KPD
program is how to make an optimal decision of kidney
exchanges that benefit patients the best.

Algorithms
 A kidney exchange problem can be represented as a
directed graph G =(V, E). Let V be the number of vertices
(nodes) and E be the number of edges in a KPD graph,
where  denotes cardinality. Each vertex in graph G represents an incompatible donorrecipient
pair (e.g., vertex 1) or an altruistic donor (e.g.,
vertex 7). Each edge from vertex i to vertex j indicates
that the donor kidney in vertex i is compatible with the
recipient in vertex j (e.g., 7 >1). In this directed graph,
each edge is assigned a weight representing edge utility ui j
of the kidney transplant from the donor in vertex i to the
recipient in vertex j (e.g., u_{71} = 9). In addition, an edge
probability pi j is considered for each edge to reflect the
possibility of an actual successful kidney transplant from i to
j (e.g., p_{71} = 0.6). All the directed edges are established for
compatibility of ABO blood types and HLA sensitizations (see
above Figure).
 The goal of optimization for kidney exchange program
is to find a collection of mutually disjoint cycles or chains that attain the maximum overall expected utility of graph G.
This task of optimizing matches on graph G by the following
setup of integer programming:
Results
 We compared two allocation strategies
in terms of accumulated number of transplants, in the
settings where the KPD only involved donorrecipient pairs
(namely no ADs). The two strategies to be compared are (1)
CycleWithoutADBase: a traditional method that does not
consider the expected utility in the optimization; (2) Cycle
WithoutAD: a new method that uses the expected utility
and accounts for the chance of failure in the optimization. The accumulated number of transplants obtained by the
two approaches with different arrival rates shown in the following figures. It implies that
the more pairs participate in the kidney exchanges program,
the higher likelihood of achieving matches in the KPD pool.
Moreover, the accumulated number of transplants gained by
the new approach (i.e., CycleWithoutAD) is significantly
higher than the traditional method (i.e., CycleWithoutADBase)
in the magnitude of 24 folds.
 We integrated the ADs into the new allocation
strategy and investigated the role of ADs in the kidney
exchanges. In the following figures (a)(c) display the accumulated
number of transplants obtained by two strategies: (1) Cycle
WithoutAD and (2) CycleWithAD, where the edge utility
is generated from a uniform distribution on interval from
[10,10] to [10,30] and the arrival rate is 10. In these
panels, based on the accumulated number of transplants
over 12 match runs, method CycleWithAD gives at least
10% more matches than the method without using ADs.
Moreover, we plotted the results for the case of arrival rate equal to 20 in
the following figures (d)(f). Again, when more people enters, method
with ADs clearly performed better than the one without ADs.
As a result, using ADs in the kidney exchanges would help
clinicians to achieve more transplants.
 We also compared accumulated utility of these two methods
(1) CycleWithoutAD and (2) CycleWithAD. From the following figures (a)(c),
we noticed that the accumulated utility of the CycleWith
AD method enjoys a gain between 15% to 30% over the
CycleWithoutAD method when the edge utility distribution
changes from [10,10] to [10,30] with arrival rate equal to 10. Likewise,
in the following figures (d)(f) report the accumulated utility of method
using ADs is about at least 10% higher than that of the
method not using ADs with arrival rate equal to 20. Therefore, it is obvious
that on average the method without using ADs is consistently
outperformed by the method using ADs over all match
runs in terms of accumulated utilities.
 We developed a general KPD computerized platform
and graphic user interface (GUI) that allow to model,
visualize, and monitor the real world kidney exchange
program. The following is a flowchart of computerized platform for kidney exchanges.
Related Publications
 Yanhua Chen, Jack Kalbfleisch, Yijiang Li, Peter X.K. Song, and Yan Zhou,
"Computerized Platform for Optimal Organ Allocations in Kidney Exchanges,"
Proceedings of the 2011 International Conference of Bioinformatics and Computational Biology (BIOCOMP),
Las Vegas, NV, USA, 2011 (acceptance rate = 21%).
 Yanhua Chen and Peter X.K. Song, "Computerized Decision Support System for Kidney Paired Donation Program
", Proceedings of 33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society(EMBC),
Boston, MA, USA, 2011.
 Yanhua Chen, Yijiang Li, Jack D. Kalbfleisch, Yan Zhou, Alan Leichtman and Peter X.K. Song,
"Graphbased Optimization Algorithm and Software on Kidney Exchanges",
IEEE Transactions on Biomedical Engineering (TBME), Vol. 59, No. 7, pp. 19851991, July 2012
