Doing the maths to find a match

Doing the maths to find a match

Issued: Mon, 07 Nov 2011 10:50:00 GMT

The complex problem of increasing the possibility of kidney transplants in the UK is being tackled by Glasgow researchers and NHS Blood and Transplant.

kidney dialysisComputing scientist Dr David Manlove is helping patients who require a kidney transplant, and who have a willing but incompatible donor, to find an appropriate match by 'swapping' their donor with that of another patient in a similar position. Dr Manlove has been collaborating with NHS Blood and Transplant since July 2008 on their kidney exchange matching scheme.

The scheme, which has been helping to connect patients and donors since April 2007, has resulted in a total of 111 transplants so far that might not otherwise have gone ahead (this total comprises 30 exchanges involving two couples, and 17 exchanges involving three couples). In collaboration with colleagues Dr Gregg O'Malley at Glasgow, and Rachel Johnson and Joanne Allen of NHS Blood and Transplant, Dr Manlove's role has been to design an algorithm that can search out options for kidney exchanges from anonymous patient data covering the whole of the UK.

Until 2006, organ transplants from living donors were only possible where there was a genetic or emotional relationship between the patient and the donor. This changed when the Human Tissue Act came into force. Now, as long as there is no financial inducement and the potential donor passes a thorough assessment, strangers can donate to someone in need.

'In the 12 months from April 2010, 38% of all kidney transplants were achieved through live donations,' explains Dr Manlove, 'but what can complicate living kidney donation is a blood-type incompatibility, or a tissue-type incompatibility. These can cause a patient's body to reject a kidney. There is also a major shortage of donors – there are approximately 7,000 patients on the kidney transplant list, and the average waiting time for a kidney is around three years for adults and around ten months for children.'

At the moment, the algorithm produces results within one second. However, the challenge for Dr Manlove and his colleagues is to ensure that they can anticipate the future needs of the matching scheme. This includes improving the algorithm so that the running time remains fast even as the input grows larger.

'We are dealing with a computational problem that is inherently difficult technically,' Dr Manlove says. 'It's called an "NP hard problem". What that means is that no "efficient" algorithm exists to solve the problem. It is important to avoid the possibility of a "combinatorial explosion", where just a small increase in the size of the data being fed into the algorithm could cause the running time to rocket to many hours or even days.'

Recently, Dr O'Malley has been working on a major redesign of the algorithm in order to deliver a stand-alone software product that NHS Blood and Transplant can use in-house. This will also allow 'chains' of transplants to be found, involving altruistic (non-directed) donors and couples,each comprising a patient and their willing but incompatible donor.  Expanding on this research, Dr Manlove hopes to continue working to adapt the algorithms to assist with the output of statistical data that could help inform decisions on whether the best course of action for a particular patient would be to participate in kidney exchange, or to opt for desensitisation treatment instead, which would enable them to accept a donation even where there is some level of incompatibility.

'Even beyond the medical sphere there are commodities that can be exchanged,' concludes Dr Manlove. 'Local government housing in China can be exchanged using matching schemes, for example. Previously, residence exchange fairs have attracted up to 80,000 people. At one fair in Beijing in 1991, nine families formed a chain and exchanged houses.

'So I expect that in the future, with more people engaging with forms of electronic communication and more processes being centralised, we will only see an increase in the need for matching schemes of this type.'

Related pages