Research

Doing the maths to find a match: Dr David Manlove

Issued: Thu, 27 Jun 2013 12:25:00 BST

Computing Scientist Dr David Manlove has been collaborating with NHS Blood & Transplant since 2008 on their kidney exchange matching scheme. The scheme has resulted in a total of 142 transplants so far that might not otherwise have gone ahead.

Dr Manlove’s role has been to design an algorithm that can search out options for so-called kidney exchanges from anonymous patient data across all of the UK.

In a kidney exchange, a patient with a willing but incompatible donor can ‘swap’ their donor with that of another patient who is in a similar position. Currently in the UK, such exchanges involve either two or three donor–recipient pairs.

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 2011, 36% 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 more than 6,600 patients on the kidney transplant list, and the average waiting time for a kidney is about three years for adults and 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, one of Dr Manlove’s colleagues at the University – Dr Gregg O’Malley – has been working on a major redesign of the algorithm in order to deliver a stand-alone software product that NHS Blood & Transplant can use in-house.

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.’

<< Researchers