@ 2015.01.08 , 08:30
22

器官捐赠中的数学:肾脏供受体之间的配对问题

[-]

人类是对称的有机体——包括我们身体内的很多器官也是左右对称。不过我们身体中的许多重要器官都只有一个(比如心脏)或者两个器官都需要才能运行得最好(比如肺)。肾是稀有的例外,你的身体里只要有一个肾就行了。这种情况允许人们靠捐赠而来的肾脏活着,这样捐赠者和受捐者都能靠一个肾脏活下来。

但可惜的是,经常有人需要肾脏移植、也有亲属愿意为他捐赠时却因为组织配对失败(强行将不配对的肾脏移植到病人体内会引起他免疫系统的排斥)而没法做手术。也有一些罕见的个体愿意为陌生人捐赠一个肾脏,因此医学界开始做能将供受体配对的“捐赠链”。

新的问题来了:有这么多移植体和受捐体,怎样才能以最大效率将他们配对呢?在以前这是NP困难问题。现在一些研究人员已经研发出了能解决这一问题的算法。

医院典型的捐赠链模式由一个愿意将肾脏捐给陌生人的不相关捐赠者开启。接着是供受体配对,结局有可能是配对不成功。捐赠链越长,捐赠者和受捐者之间配对成功的可能性越大,受捐者身上出现排斥反应的机会越小。

现在研究人员提出的新算法首先与“整数规划”(integer programming)这个术语有关,这种算法从一个不配对的捐赠者开始计算,然后列出所有可能的项,之后再查看这些可能项与受捐者之间的匹配程度。研究人员还将肾脏捐赠问题归类为旅行商问题(即一名旅行商打算拜访一张城市列表中的所有城市,每座城市只去一次,最后回到出发地,怎样走出最短路线的问题)。使用这种为这位旅行商修正过的算法之后,他们为肾脏捐赠专门研发了一种算法。

他们决定不使用过往数据,即那些已经配对成功了的人的医疗记录。于是他们另外收集了许多潜在的捐赠者和受捐者的数据。一般说来,旅行商算法比循环算法更好,即便捐赠链的潜在长度没有限制,它也能在一个合理的时间内给出答案。

这种算法已经同时配对了几百对供受体,肾脏捐赠问题也不再是我们以前所认为的NP难题了。研究人员的算法已经被医疗体系采用了,这说明学点数学在探讨现实问题上确实有些帮助。

本文译自 arstechnica,由译者 肌肉桃 基于创作共用协议(BY-NC)发布。


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

0.0
赞一个 (2)

TOTAL COMMENTS: 22+1

  1. 雨雨
    @3 years ago
    2654492

    不知道为什么,突然想起了汇仁肾宝

  2. 要十载
    @3 years ago
    2654493

    看的不是很明白,具体是怎么计算的?

  3. 保护模式
    @3 years ago
    2654499

    肾,是如何交配的?

  4. 科比大毒瘤
    @3 years ago
    2654500

    所以取消死刑犯强制夺取器官是提高司法公正非常重要的举措。配到了赶紧害死的路不通了。

    [19] XX [1] 回复 [0]
  5. 小次次
    @3 years ago
    2654503

    一进来就又是攻受又是NP,我们当然知道攻受配对难,也知道NP存在实施性的困难,但是小编你到底是啥目的……

  6. 腐女
    @3 years ago
    2654517

    攻受。。,

  7. 雨后的小故事
    @3 years ago
    2654519

    抖m在此!

  8. Xavier
    @3 years ago
    2654521

    买台iPhone装上试试……

  9. 海贼王
    @3 years ago
    2654538

    细节呢?细节才关键吧

  10. 飞盘
    @3 years ago
    2654551

    这些腐女真是没文化

  11. 有点幽默
    @3 years ago
    2654580

    每个字都看得懂

  12. 肤浅
    @3 years ago
    2654588

    我就是来看配图的

  13. 2654703

    这明明就是个二分图最大或最优匹配问题,为什么要弄旅行商??

  14. 2654720

    稳定婚姻问题、Gale-Shapley算法?

  15. 2654759

    2012年诺贝尔经济学获得者,Alvin E. Roth和Lloyd S. Shapley,在2004年提出了肾脏交易市场设计的数学模型,基于经济学理论提出了自由市场里最有效率分配肾脏的方法。

    他的论文,KIDNEY EXCHANGE(ALVIN E. ROTH,TAYFUN SO¨ NMEZ,M. UTKU U¨ NVER),也是计算机系里计量经济学必看的论文。

    看行为经济学的补充是怎么样绕过道德困境的指责,在数学上证明了自由市场在道德上也能达到最优。

  16. 戊戌白羊
    @3 years ago
    2654763

    先搜索周围的列表,然后点击配对不就好了?

  17. 2654765

    @asmn:
    二分图最大匹配没有考虑人性的自私性
    小明的舅舅愿意给小明捐肾,但是不匹配,反而跟小刚匹配
    小明的舅舅愿意给小刚捐吗?也许不愿意,但如果保证小明的舅舅给小刚捐了以后小明能找到捐赠者的话,小明的舅舅就愿意捐了
    所以实际的建模是说:我们已经有了一堆捐赠者-受捐者对,每一对作为图上的一个点
    小明舅舅-小明这一对到小刚舅舅-小刚有一条有向边表示小明舅舅和小刚匹配
    那么为了让小明舅舅捐出去,小明又能找到捐赠者,我们需要在图上找到一条以小明舅舅-小明开始,小明舅舅-小明结束的环,其中没有重复的点出现,这就是TSP,旅行商
    我想吐槽的是,TSP不也是NP-Hard的吗…

    [10] XX [0] 回复 [0]
  18. 土土
    @3 years ago
    2654789

    还是好好研究一下克隆技术或者细胞3D打印技术吧,我已经等了八年了。。。

  19. 2654812

    @John:不需要每个点都走一遍,而每一个点都有一个权重,对应肾脏捐赠的紧急性,求最大权重的路。应该算是TSP的广义化,PCTSP。

  20. dimsum
    @3 years ago
    2654860

    @John: 还有法律的问题,大部分国家都不允许买卖活人器官,才能有这种以物易物的算法出现。

  21. 向上击打
    @3 years ago
    2655368

    再次为“数学行天下”论提供有力证据

  22. 2655967

    总结起来就是乔布斯为医学的贡献

发表评论


24H最赞