INESC TEC coordinates unique project to manage and plan Public Health

Optimisation tool maximises number of transplants with paired kidney exchange

A tool developed as part of the project is now being used by the Instituto Português do Sangue e da Transplantação – IPST (institute for blood and organ donors) and it can mean a new hope for patients waiting for a kidney.

The algorithm can pair up donors and patients

It is estimated that Portugal about 800 thousand people suffer from kidney diseases. Of these people, about two thousand are waiting for a transplant, and they wait on average between two and four years, as kidney transplants from living donors represent less than 10 per cent of total transplants [1]. Focusing on this problem, INESC TEC started working on project KEP, together with Portuguese institutions, in order to study and develop new methods to help facilitate and improve decisions associated with kidney transplants with living donors.

Starting in April 2012, this research resulted in a specialised optimisation tool that is now being used since last year by the IPST, as part of the National Programme for Paired Kidney Exchange (PNDRC). The software determines compatibility (blood and HLA - Human Leukocyte Antigens) between the donors and patients involved in this plan and afterwards, according to the compatibilities found, it selects the pairs that make it possible to perform the largest number of transplants.

The algorithm was prepared to calculate solutions that involve a maximum number or pairs pre-defined by the user. This means “that if the user allows transplants with a maximum number of three pairs, donor 1 will donate a kidney to the patient in pair 2; the donor of pair 2 donates to the patient in pair 3, and the donor in pair 3 donates to the patient in pair 1, thus closing the cycle. However, if a fourth pair is required in order to close the cycle, the solution is dismissed,” explains Ana Viana, a researcher at INESC TEC’s Industrial Engineering and Management Unit (UGEI) and project leader. This is the component that makes the problem difficult to solve. The algorithm was also programed to consider indirect transplants, which involve donors with no associated patient, as well as donor/patient pairs where the patient has several alternative donors.

The tool is available to all hospitals involved in the PNDRC, which can locally insert the information associated with their pairs. However, the IPST is the only entity with access to the optimisation engine.

The project is new and almost exclusive in the world

In 2012, the Nobel Prize in Economics was given to two North-American economists, Alvin Roth and Lloyd Shapley, who conducted studies on markets, agents and optimisation tools for demand and supply. Using the Gale-Shapley algorithm, to which he introduced some changes, Alvin Roth successfully recreated the methods used by institutions in order to pair up, for example, doctors with hospitals, students with schools and organ donors with patients requiring a transplant.

This was one of the moments that brought worldwide attention to the problem of optimisation, but the fact is that there is still much to study in this area. Worldwide, it is believed that only the United Kingdom and the United States are doing research on paired kidney transplant optimisation similarly to what is being done at INESC TEC, which makes it almost exclusive. “This project is having quite an impact internationally, not only because there are few people working in this area, but also because there is a practical application for the work,” Ana Viana states, highlighting the importance of KEP: “the optimisation tools that are used in the countries we are aware of, where the same approach is used (United Kingdom and United States), are at the level of those developed in our project.”

Other than the IPST and UGEI/INESC TEC (Ana Viana, João Pedro Pedroso, Margarida Carvalho, Nicolau Santos, Xenia Klimentova), the project partners include the S. João Hospital (Gerardo Oliveira), the University of Minho (Filipe Alvelos and Abdur Rais), and the University of Lisbon (Miguel Constantino). The project will be concluded by the end of this year.

[1] Data from 2012

The INESC TEC researchers mentioned in this article are associated with the following partner institutions: INESC Porto, FCUP and ISEP.