9Fj59Iy

En 2013, en España se contaron hasta 382 donantes de riñón, un récord del que sin duda podemos estar muy orgullosos. Y es que, al contrario de lo que pasa con la mayoría del resto de órganos, podemos prescindir de uno de ellos y llevar una vida prácticamente normal. El problema surge cuando hay donante y receptor, pero sus tejidos no son los suficientemente compatibles, lo que llevaría a un rechazo por parte del sistema inmunitario del último. Para solucionar esto se ha creado un sistema de “cadenas de donaciones” que tiene mucha matemática de por medio.

La idea es que si tú recibes un riñón, un conocido o pariente tuyo tiene que donar uno a otra persona (ya sea conocida o no) y así sucesivamente. El ejemplo que siguees real, se dio en Estados Unidos y tuvo una importante repercusión por su componente racial. Un hombre blanco perdió a su hijo de 18 años en un accidente con moto de nieve. A los tres años, decidió que quería salvar la vida de alguien donando su riñón. El órgano se trasplantó a una mujer de raza negra, cuyo hijo donó el suyo a un hombre asiático en diálisis. Y la mujer del asiático hizo lo propio en beneficio de una profesora hispana. Se trata de una de las cadenas con mayor eco mediático, pero no la más larga del mundo.

Como se puede ver, cada cadena empezaría con un donante altruista y acabaría con un receptor que no tuviera alguien conocido que donara (“pareja donante”). Esto, a su vez, ha creado un problema: dada una gran cantidad de donantes y receptores, ¿cómo haces para conseguir un conjunto de cadenas de donantes optimizadas? Con optimizadas me refiero a que haya el menor rechazo posible entre donante-receptor y que el mayor número de enfermos posibles tenga un donante del que recibir. Pues resulta, damas y caballeros, que este problema pertenece a un tipo llamado “problemas NP complejos”.

El problema de los problemas

En  teoría de la complejidad computacional una de las cosas que más importa al resolver un problema no es que lo resuelvas, sino cómo lo resuelves, cuánto tiempo lleva. Por ejemplo, imaginad que tratamos de buscar un número concreto en un conjunto denúmeros. Conforme el conjunto de números se haga más grande, tardaremos más tiempo, pero de una forma lineal. Es decir, si es el doble de grande, tardaremos el doble de tiempo, entonces decimos que, siendo n la cantidad de números, el tiempo que tarda es del orden de n ( T(n)=O(n) ). Puede darse el caso en que el orden sea de n² o de cualquier otra potencia. En estos casos, en los que el tiempo es un polinomio (tiempo polinómico) se dice que ese problema pertenece a la clase P. Por supuesto, todo problema que se pueda resolver en tiempo polinómico también es verificable en tiempo polinómico (en el ejemplo, bastará con volver a buscarlo).

7

Diagrama de Euler para los conjuntos P, NP y NP complejos (NP-Hard).

Por otra parte está la clase de problemas NP, aquellos que son verificables en tiempo polinómico (no tienen por qué ser resolubles en tiempo polinómico). Por ejemplo, ¿cuáles son los factores primos de 436141? Os podéis morir dividiendo, porque 436141=587*743. Cuanto más grande es el número, más cuesta encontrar sus factores primos, pero si os doy los factores primos es inmediato comprobar si la respuesta es correcta. Uno de los mayores problemas actuales en matemáticas, justamente es saber si P=NP (hasta tiene un premio de un millón de dólares).

 Una cosa que es muy útil en informática en general a la hora de tratar un problema, es poder reducirlo a algo más fácil que sí sepamos como resolverlo. De esta idea surgen los problemas NP-complejos. Un problema A es NP-complejo si cualquier otro problema que sea NP puede reducirse a A en tiempo polinómico. Intuitivamente quiere decir que podemos resolver B rápido si podemos resolver rápido, y el nombre viene lógicamente porque son los más difíciles de resolver. Y a esta clase pertenece nuestro problema de la cadena de donantes.

Difícil, pero no imposible

A finales de 2014, en este estudioRoss Anderson y su equipo de la Universidad de Cambridge,  probaron con dos aproximaciones diferentes para encontrar estas cadenas. La primera involucra técnicas de lo que se llama “programación entera“, es decir que trabaja con números enteros, como la compatibilidad entre tejidos o la cantidad de tiempo esperada para recibir un órgano. Usando esta aproximación, empezaron con un donante altruista y recursivamente fueron generando todas las posibles cadenas, comprobando cuál iba siendo mejor para encontrar la óptima.

Bruteforce (1)

Ejemplo de generación de cadenas en un TSP con 7 ciudades.

Por otra parte, se dieron cuenta de que el problema del donante de riñón no es más que un caso específico de lo que se llama “el problema del viajante” (TSP, por sus siglas en inglés). En esta versión, una persona tiene que visitar tantas ciudades como pueda, por los caminos más cortos posibles, pero por cada ciudad que no pase tiene una penalización. Usando una modificación de un algoritmo diseñado para este problema, han implementado uno que es específico para las donaciones de riñón.

Para probar ambos algoritmos decidieron emplear una gran cantidad de potenciales donantes y receptores. En general, el segundo algoritmo funciona mejor que la recursión y produjo respuestas en una cantidad razonable de tiempo, incluso cuando la longitud de la cadena era ilimitada.

Este es otro ejemplo de trabajos interdisciplinares, donde se investiga en las fronteras de áreas del conocimiento en principio diferentes (en este caso matemáticas y biología) y que está dando resultados muy, muy interesantes. Sólo espero que este tipo de trabajos no nos cueste un riñón ;-) .

Únete a la comunidad

Más de 14.212 personas se han unido a nuestra newsletter. Prometemos enviarte sólo cosas interesantes.

Gracias por suscribirte.

Share This