Summary of the impact

Algorithms developed by University of Glasgow researchers have helped NHS Blood and Transplant (NHSBT) tackle the complex problem of increasing the number of kidney transplants in the UK. For people with end-stage renal failure, the most effective form of treatment is transplantation. Dr David Manlove's research team have developed sophisticated algorithms which allow the NHS to help patients who require a kidney transplant, and who have a willing but incompatible donor, to exchange their donor with that of another patient in a similar position, in what is known as a paired exchange. By optimising kidney exchanges, University of Glasgow research has increased the number of transplants from paired donation by 40% between 2008 and 2013, when measured in comparison with the number of transplants that would have been possible with previous pairing techniques. Dr Manlove's work with NHSBT has translated not only into increased quality of life for patients freed from long term dialysis but will also afford the NHS an estimated £16 million of savings over the next 10 years.

Underpinning research

A group of two or more kidney patients swapping their willing but incompatible donors with one another in a cyclic fashion is called a paired kidney exchange (PKE). In early 2007, NHS Blood and Transplant (NHSBT) set up a national matching scheme to identify optimal sets of these exchanges from among the patient and donor data on the NHSBT database. NHSBT developed an algorithm to search the database and identify suitable matches from a number of weighted criteria, but this algorithm was only capable of finding PKEs involving two donor-recipient pairs and could only handle datasets of up to 100 potential transplants.

Dr David Manlove's interests in algorithmic research into matching problems, and his recognition of the inefficiencies in the existing model, as well as previous collaboration with NHS Education for Scotland on the Scottish Foundation Allocation Scheme, led to a fruitful collaboration with the NHSBT beginning in May 2007. Manlove (Lecturer 2000-09, Senior Lecturer 2009-present) and Dr Péter Biró (Research Assistant, 2007-10) developed a novel approach involving graph-matching algorithms which enabled optimal sets of PKEs, involving up to three donor-recipient pairs, to be identified [2; 6]. They also significantly increased the capacity of the algorithm to deal with larger datasets of up to 3,000 potential transplants. The simulations run by the University of Glasgow team in early 2008, using their implemented algorithms, indicated the likely benefit, in terms of numbers of additional transplants, of allowing PKEs to involve up to three patients rather than two. Two- and three-way PKEs were already established in the US, but there is a complex set of optimality criteria that made the UK application different and algorithmically challenging. Following this initial research, the NHSBT took the decision in April 2008 to allow PKEs to involve up to three patient-donor pairs. The introduction of three-way exchanges meant that this had become an `NP hard problem', meaning that an efficient algorithm to resolve the problem was unlikely to exist, with the main risk being that an increase in the size of the data set might cause a `combinatorial explosion', whereby computational times become unreasonably long.

In 2010 and 2011, an improved version [5] of the Glasgow software was written by Dr Gregg O'Malley (Research Assistant 2008-09 and 2010-11, Research Associate 2011-13), using an integer programming technique [1]. This also addressed some changes in the established criteria for matches. Dr O'Malley developed an in-house version of the software for the NHSBT, allowing them to conduct the searches themselves and speed up response times. This software was delivered to NHSBT in June 2011. O'Malley also developed a web application [4] enabling the NHSBT to trial potential changes to the criteria used in the matching run, which could have an effect on the number and quality of matches. Matching runs now occur on a quarterly basis.

The University of Glasgow researchers completed a project in 2013 which involved further development of the kidney exchange algorithms to address issues of scalability to ensure that they will be able to cope with even larger datasets going forward [3]. As awareness of the National Living Donor Kidney Sharing Schemes (the collective term used to describe the schemes in which donated kidneys are `shared' across the UK) continues to grow, more patients and donors are expected to join, leading to richer datasets involving more exchanges and in turn a greater quantity and quality of potential transplants that can be identified by the software in the future.

The Glasgow contribution included the original research on theoretical algorithm design, and subsequent implementation in software, leading to deployment by NHSBT. This work is a prime example of top quality fundamental research in matching algorithm theory, published in peer-reviewed references [1,2],which led to extraordinary advances in real life problems .

References to the research

3. Externally-funded research project: Optimising options and strategies for living donor kidney transplantation for incompatible donor-recipient pairs. Duration: 1 January 2012 - 30 June 2013. Amount: £151k. Funder: NHS Blood and Transplant. Co-Investigator: Dr David Manlove. Research Associate: Dr Gregg O'Malley.

4. Externally-funded research project: Kidney Paired Exchange Data Analysis Toolkit. Duration: 1 July 2011 - 31 December 2011. Amount: £32k. Funder: EPSRC KTA fund. Principal Investigator: Dr David Manlove. Research Associate: Dr Gregg O'Malley.

5. Externally-funded research project: Software for the National Matching Scheme for Paired Donation. Duration: 1 April 2010 - 30 June 2011. Amount: £108k. Funder: NHS Blood and Transplant. Principal Investigator: Dr David Manlove. Research Assistant: Dr Gregg O'Malley. *

6. Externally-funded research project: MATCH-UP: Matching Under PreferencesAlgorithms and Complexity. Duration: 1 June 2007 - 30 June 2010. Amount: £324k. Funder: EPSRC (grant EP/E011993/1). Co-Investigator: Dr David Manlove. Research Assistant: Dr Péter Biró.

* best indicators of quality

Details of the impact

Kidney failure has a devastating impact on patients' lives, and long-term survival rates after transplantation demonstrate a doubled or tripled life expectancy compared to dialysis. The NHSBT estimates that over 37,500 people in the UK have end-stage renal failure; nearly 21,000 are on dialysis. As of 31 March 2013 there were 6,325 patients on the transplant list for a donor kidney; the number of kidney transplants carried out each year is less than half that number (2984 between April 2012-April 2013 of which 1916 were from deceased donors and 1068 from living donors [NHSBT]). The NHSBT estimates median waiting time on the transplant list at 1168 days for an adult and 354 days for a child, and according to the National Kidney Federation approximately 400 people each year die while awaiting a kidney transplant.

Prior to 1 September 2006, transplants could only take place between those with a genetic or emotional connection. However, the Human Tissue Act 2004 and Human Tissue (Scotland) Act 2006 created the legal framework to allow transplants between strangers, thus opening up new possibilities for living donor transplants.

Increasing the number of potential kidney matches
Research by the University of Glasgow showed how to model a complex, hierarchical set of criteria that form the definition of an optimal set of kidney exchanges. The algorithm developed to identify optimal sets has been used by NHS Blood and Transplant (NHSBT) since 2008, enabling the number of potential matches to be radically improved and resulting in more transplants arising from identified kidney exchanges being carried out over the last four years (see Figure 1).

The development of the University of Glasgow algorithm led directly to a decision by the NHS to allow three-patient `swaps' of donor kidneys from April 2008 onwards, increasing the number of potential transplants even further. Between July 2008 and April 2013, a total of 393 transplants were identified by the algorithms and of these, 232 transplants actually took place. Had the NHSBT continued to use their pre-existing algorithm, which was only capable of identifying pairwise exchanges, it is likely that only 165 transplants would have gone ahead (from a total of 280 identified matches, using the same conversion rate). Thus the 232 transplants that took place represents an increase of 67, or 40%, compared to the estimated number that would have occurred if the status quo techniques had continued to be used.

A modified University of Glasgow algorithm has allowed altruistic donors (people who are willing to donate a kidney to a stranger) to be included in the National Living Donor Kidney Sharing Schemes since January 2012. An altruistic donor can either donate directly to a patient on the Deceased Donor Waiting List, or else trigger a domino paired donation chain involving one or more incompatible patient-donor pairs, leading to additional transplants.

In 2010, the Head of Organ Donation and Transplantation Studies, NHS Blood and Transplant stated:

Since July 2008, we have been collaborating with Dr David Manlove and Dr Péter Biró in relation to the NMSPD [National Matching Scheme for Paired Donation, now the National Living Donor Kidney Sharing Schemes]: their matching algorithms have been used in order to construct optimal solutions to the datasets that we provide. Some of these datasets have encoded particularly challenging underlying problems, and the task of producing an optimal solution would have been highly complex without the assistance of these matching algorithms. We anticipate that this will be a growing issue as the number of people in the database increases over time.

Improving patient quality of life
For patients, the benefits are numerous. Kidneys from living donors last on average 33% longer than those from deceased donors (15 years compared to 10), so increasing the number of these types of exchanges translates into more patients enjoying a longer period of time living with a healthy kidney, returning to work or otherwise resuming their normal lives. Transplantation also extends the life expectancy of patients with kidney disease compared to dialysis (life expectancy for dialysis patients is only five years on average). Dialysis can save patients' lives but it is not a cure as it does not replace all the functions of a healthy kidney. Dialysis also carries significant health implications for patients and can cause or contribute to anaemia, bone disease, high blood pressure, heart disease, nerve damage and infection. A BBC news article in March 2010 described the difference that a three-way kidney transplant made to the lives of the recipients involved.

Financial benefits for the NHS
The work of Dr Manlove and colleagues has economic benefits for the NHS as well as health benefits for the patients involved. According to NHSBT, each kidney transplant saves the NHS £240,000 over 10 years (based on a comparison with the cost of dialysis over that time period, and taking into account the cost of the operation itself). This means that by enabling an increase of 67 new kidney transplants, the University of Glasgow researchers have potentially saved the NHS around £16 million over the next 10 years, with additional savings to come with each new three-way pairing identified.

With an aim to share best practice, compare and agree on common optimality criteria and common data formats and lay the ground-work to ultimately share kidney exchange pools on an international basis, Dr Manlove and his collaborators currently have a European Cooperation in Science and Technology proposal under review. The proposal includes representation from the UK, France, Germany, Netherlands, Spain, Portugal, Hungary, Czech Republic, Slovakia and wider participation from the USA and Australia.

Sources to corroborate the impact

Evidencing value of the research to kidney donor-patient matching in the NHS:

• Corroborating Statement from the Head of Organ Donation and Transplantation Studies, NHS Blood and Transplant (available from HEI)
• NHSBT Paired donation website (link)
• Research Council UK, Big Ideas for the Future Report (link, see pg 13)
• Public Service Review: Devolved Government, Vol 19 (pg36 profiles the Glasgow research and its contribution to the NHS living donor kidney transplant programme) [available from HEI]
• The Engineer, 18 March 2010 (link or available from HEI)
• BBC News, 8 March 2010 (link or available from HEI) (describes quality-of-life benefits to patients)