Optimal kidney exchange
بہترین گردے کا تبادلہ (اوکے ای) ایک اصلاح کا مسئلہ ہے جس کا سامنا گردے کے جوڑے کے عطیات کے پروگراموں کو کرنا پڑتا ہے (جسے گردے کا تبادلہ پروگرام بھی کہا جاتا ہے)۔ اس طرح کے پروگراموں میں مریض-عطیہ دہندہ کے جوڑوں کا بڑا ڈیٹا بیس ہوتا ہے، جہاں عطیہ دہندہ مریض کی مدد کے لیے گردے کا عطیہ کرنے کو تیار ہوتا ہے، لیکن طبی عدم مطابقت کی وجہ سے ایسا نہیں کر سکتا۔ مراکز ایسے جوڑوں کے درمیان تبادلوں کا انتظام کرنے کی کوشش کرتے ہیں۔ مثال کے طور پر، جوڑی اے میں عطیہ دہندہ جوڑی بی میں مریض کو عطیہ کرتا ہے، جوڑی بی میں عطیہ دہندہ جوڑی سی میں مریض کو عطیہ کرتا ہے، اور جوڑی سی میں عطیہ دہندہ جوڑی اے میں مریض کو عطیہ کرتا ہے۔ اوکے ای مسئلہ کا مقصد اس طرح کے تبادلے کا بہترین انتظام تلاش کرنا ہے۔ "زیادہ سے زیادہ" کا مطلب عام طور پر یہ ہے کہ ٹرانسپلانٹ کی تعداد جتنی ممکن ہو اتنی زیادہ ہے، لیکن اس کے دوسرے مقاصد بھی ہو سکتے ہیں۔ اس اصلاح کے مسئلے میں ایک اہم رکاوٹ یہ ہے کہ ایک عطیہ دہندہ صرف اس صورت میں گردہ دیتا ہے جب اس کے مریض کو مطابقت پذیر گردہ ملتا ہے، تاکہ کوئی بھی جوڑا حصہ لینے سے گردے سے محروم نہ ہو۔ اس ضرورت کو بعض اوقات انفرادی معقولیت کہا جاتا ہے۔ اوکے ای مسئلہ کی بہت سی قسمیں ہیں، جو ہر تبادلے کے اجازت شدہ سائز، معروضی فنکشن اور دیگر عوامل میں مختلف ہوتی ہیں۔ تعریفیں ان پٹ اوکے ای کی ایک مثال کو عام طور پر ڈائریکٹڈ گراف کے طور پر بیان کیا جاتا ہے۔ ہر نوڈ مریض-عطیہ دہندہ کے جوڑے کی نمائندگی کرتا ہے۔ جوڑی اے سے جوڑی بی تک ایک ہدایت شدہ آرک کا مطلب ہے کہ جوڑی اے میں عطیہ دہندہ جوڑی بی میں مریض کے ساتھ طبی طور پر مطابقت رکھتا ہے (مطابقت کا تعین عطیہ دہندہ اور مریض کے خون کی اقسام کے ساتھ ساتھ دیگر عوامل جیسے کہ ان کے خون میں مخصوص اینٹی جینز کی بنیاد پر کیا جاتا ہے)۔ مطابقت گراف میں ایک ہدایت شدہ سائیکل ممکنہ تبادلے کی نمائندگی کرتا ہے۔ سائز 2 کا ایک ہدایت شدہ چکر (مثال کے طور پر۔ A-> B-> A) ممکنہ جوڑی کے لحاظ سے تبادلے کی نمائندگی کرتا ہے-جوڑوں کے جوڑے کے درمیان تبادلہ۔ اوکے ای کی ایک زیادہ عام قسم دوسری قسم کے نوڈس پر بھی غور کرتی ہے، جو پرہیزگاری عطیہ دہندگان کی نمائندگی کرتے ہیں-عطیہ دہندگان جو کسی مریض کے ساتھ جوڑے نہیں ہیں، اور کسی بھی ہم آہنگ مریض کو گردے کا عطیہ کرنے کے لیے تیار ہیں۔ الٹروسٹک ڈونر نوڈس میں صرف باہر جانے والے آرکس ہوتے ہیں۔ پرہیزگاری عطیہ دہندگان کے ساتھ، نہ صرف سائیکلوں کے ساتھ بلکہ زنجیروں کے ساتھ بھی تبادلوں کا انتظام کرنا ممکن ہے، جس کا آغاز ایک پرہیزگاری عطیہ دہندہ سے ہوتا ہے۔ گراف میں موجود آرکس میں وزن ہو سکتے ہیں، مثال کے طور پر۔ شامل ٹرانسپلانٹس کی کامیابی کا امکان۔ ان کی ترجیحات بھی ہو سکتی ہیں، مثال کے طور پر۔ طبی فوری ضرورت کی وجہ سے یا اس وقت تک جب مریض ٹرانسپلانٹیشن کی قطار میں انتظار کر چکا ہو۔ آؤٹ پٹ اوکے ای کی آؤٹ پٹ جوڑی کے لحاظ سے جداگانہ ڈائریکٹڈ سائیکلوں کا ایک مجموعہ ہے (اور ممکنہ طور پر ڈائریکٹڈ چینز، اگر رضاکارانہ عطیہ دہندگان دستیاب ہوں)۔ اوکے ای میں سب سے آسان مقصد گردے حاصل کرنے والے مریضوں کی تعداد کو زیادہ سے زیادہ کرنا ہے۔ دیگر عام مقاصد یہ ہیں: گردے کے تبادلے کے وزن کے مجموعے کو زیادہ سے زیادہ کرنا: گراف کے ہر کنارے کا وزن ہوتا ہے، اور مقصد ایک ایسا تبادلہ تلاش کرنا ہے جو تبادلے میں استعمال ہونے والے تمام کناروں پر وزن کے مجموعے کو زیادہ سے زیادہ کرے۔ ٹرانسپلانٹ امیدواروں کی متوقع عمر کو زیادہ سے زیادہ کرنا، یا ان کی معیار کے مطابق متوقع عمر کو بہتر بنانا۔ غیر محدود سائیکل کی لمبائی ابتدائی طور پر، تبادلے کے چکروں کی لمبائی پر کسی حد کے بغیر اس مسئلے کا مطالعہ کیا گیا تھا۔ روتھ، سونمیز اور انور نے ایک طریقہ کار پیش کیا، جو ٹاپ ٹریڈنگ سائیکل میکانزم کی توسیع پر مبنی تھا، تاکہ پیریٹو-بہترین اور ترغیبی-مطابقت پذیر طریقے سے تبادلے کے چکروں کو تلاش کیا جا سکے۔ ابراہم، بلوم اور سینڈہولم ظاہر کرتے ہیں کہ، غیر محدود سائیکل کی لمبائی کے ساتھ، کثیر الجہتی وقت میں زیادہ سے زیادہ کارڈینالٹی اور زیادہ سے زیادہ وزن کا تبادلہ پایا جا سکتا ہے۔ مثال کے طور پر، میکسیم-کارڈینالٹی ایکسچینج تلاش کرنے کے لیے، اصل ہدایت شدہ گراف G کو دیکھتے ہوئے، ایک غیر ہدایت شدہ دو طرفہ گراف H (X + Y، E) بنائیں جس میں: G میں ہر جوڑے j کے دو نوڈس ہوتے ہیں: xj (ڈونر کی نمائندگی) اور yj (مریض کی نمائندگی)۔ وہ وزن 1 کے کنارے سے جڑے ہوئے ہیں۔ G میں ہر کنارے i-> j کے لیے، وزن 1 + 1/n کے H ایک کنارے xi-- yj میں شامل کریں۔ H میں زیادہ سے زیادہ وزن کا مماثلت تلاش کریں۔ G میں ہر زیادہ سے زیادہ کارڈینالیٹی کا تبادلہ H میں زیادہ سے زیادہ وزن کے مماثلت سے مطابقت رکھتا ہے۔ نوٹ کریں کہ وزن اس بات کی ضمانت دیتا ہے کہ H میں ہر زیادہ سے زیادہ وزن کا مماثلت کامل ہے، تاکہ ہر مریض کا مماثلت ہو، یا تو کسی ہم آہنگ ڈونر سے، یا اس کے اپنے ڈونر سے۔ لہذا کوئی عطیہ دہندہ اس وقت تک گردہ نہیں دیتا جب تک کہ اس کے مریض کو گردہ نہ مل جائے، جو انفرادی عقلیت کی ضرورت کو پورا کرتا ہے۔ اس الگورتھم کو زیادہ سے زیادہ وزن کے تبادلے تک بڑھانا، اور پرہیزگاری عطیہ دہندگان کو شامل کرنا آسان ہے۔ جوڑی کے لحاظ سے گردے کا تبادلہ 2004 میں نیو انگلینڈ میں گردے کے تبادلے کے پروگرام کو نافذ کرنے کے لیے ہونے والی بات چیت میں یہ معلوم ہوا کہ لاجسٹک طور پر صرف جوڑی کے لحاظ سے تبادلے ممکن ہیں۔ اس کی وجہ یہ ہے کہ تبادلے میں تمام کارروائیاں بیک وقت کی جانی چاہئیں۔ اس ضرورت کا مقصد انفرادی عقلیت کی رکاوٹ کو یقینی بنانا ہے-اس خطرے سے بچنے کے لیے کہ ایک عطیہ دہندہ اپنے مریض کے گردے حاصل کرنے کے بعد عطیہ دینے سے انکار کر دیتا ہے۔ سائز k کے تبادلے کے چکر میں بیک وقت 2k کارروائیوں کی ضرورت ہوتی ہے۔ اس وقت بیک وقت 4 سے زیادہ کارروائیوں کا انتظام کرنا عملی نہیں تھا، اس لیے سائیکلوں کا سائز 2 تک محدود تھا۔ اس ترتیب میں، ہدایت شدہ مطابقت کے گراف کو غیر ہدایت شدہ گراف تک کم کرنا ممکن ہے، جہاں A اور B کے جوڑے صرف اس صورت میں جڑے ہوں اگر A-> B اور B-> A ہوں۔ زیادہ سے زیادہ کارڈینالیٹی جوڑی کے لحاظ سے تبادلے کا پتہ لگانا اس غیر ہدایت شدہ گراف میں زیادہ سے زیادہ کارڈینالیٹی میچنگ تلاش کرنے کے مترادف ہے۔ مزید برآں، جب صرف جوڑی کے لحاظ سے تبادلوں کی اجازت ہوتی ہے، تو ایک مماثلت پیریٹو موثر ہوتی ہے اگر اور صرف اس صورت میں جب اس میں زیادہ سے زیادہ کارڈینالیٹی ہو۔ لہذا، اس طرح کا تبادلہ کثیر الجہتی وقت میں پایا جا سکتا ہے۔ روتھ، سونمیز اور انور سادہ زیادہ سے زیادہ کارڈینالیٹی کے تبادلے کی دو توسیعات کا مطالعہ کرتے ہیں: مریضوں یا ٹرانسپلانٹس پر ترجیحی درجہ بندی کو دیکھتے ہوئے، کثیر الجہتی وقت میں ترجیحی ملاپ تلاش کرنا ممکن ہے-ایک ایسا ملاپ جو، تمام زیادہ سے زیادہ کارڈینالیٹی کے ملاپ کے درمیان، اعلی ترجیحی مریضوں کی تعداد کو زیادہ سے زیادہ کرتا ہے۔ مزید برآں، ان الگورتھم کو اس معنی میں ترغیبی مطابقت پذیر بنایا جا سکتا ہے کہ ہر مریض زیادہ سے زیادہ عطیہ دہندگان کو نظام میں لا کر اور زیادہ سے زیادہ گردوں کو قبول کرنے پر راضی ہو کر اپنے مماثل ہونے کے امکانات کو زیادہ سے زیادہ بڑھاتا ہے۔ ثبوت گراف تھیوری کے تصورات کا استعمال کرتے ہیں، جیسے کہ گیلائی-ایڈمنڈز سڑنا۔ اسٹوکاسٹک ایکسچینج تلاش کرنا ممکن ہے، جہاں تمام زیادہ سے زیادہ کارڈینالیٹی مماثلتوں میں سے بے ترتیب طور پر ایک مماثلت کا انتخاب کیا جاتا ہے۔ مساویانہ طریقہ کار کا مقصد مریض کے گردے حاصل کرنے کے سب سے کم امکان کو زیادہ سے زیادہ کرنا ہے۔ مساویانہ طریقہ کار اسی لحاظ سے ترغیبی مطابقت رکھتا ہے جس طرح ترجیحی طریقہ کار ہے۔ لمبائی k کے چکروں نے بعد کے سالوں میں، لاجسٹک بہتریوں نے بیک وقت کارروائیوں کی بڑی تعداد کو انجام دینے کی اجازت دی۔ اس کے مطابق، تین یا اس سے زیادہ جوڑوں پر مشتمل تبادلے کے چکروں کو ممکن بنایا گیا۔ زیادہ سے زیادہ کارڈینالیٹی کے تبادلے کو تلاش کرنا، گراف نظریاتی اصطلاحات میں، زیادہ سے زیادہ سائیکل پیکنگ کہا جاتا ہے۔ زیادہ سے زیادہ k لمبائی کے چکروں کے ساتھ زیادہ سے زیادہ سائیکل پیکنگ، کسی بھی فکسڈ k ≤ 3 کے لیے، ایک NP-سخت کمپیوٹیشنل مسئلہ ہے (یہ ہائپر گراف میں 3 جہتی ملاپ کے مسئلے سے کمی سے ثابت کیا جا سکتا ہے)۔ ابراہم، بلوم اور سینڈ ہولم زیادہ سے زیادہ سائیکل پیکنگ کے لیے دو تکنیکیں پیش کرتے ہیں: کالم نسل اور رکاوٹ نسل۔ وہ رپورٹ کرتے ہیں کہ کالم نسل کا پیمانہ بہت بہتر ہے۔ ان کے الگورتھم کو الائنس فار پیئرڈ گردے کے عطیات میں نافذ کیا گیا ہے۔ بیرو، مینلوو اور رزی اس مسئلے کو حل کرنے کے لیے دو طریقے تجویز کرتے ہیں یہاں تک کہ جب کناروں کے وزن ہوتے ہیں (اس صورت میں اسے زیادہ سے زیادہ وزن والی سائیکل پیکنگ کہا جاتا ہے): زیادہ سے زیادہ وزن والے آزاد سیٹ کے لیے معروف تخمینہ الگورتھم پر مبنی ایک تخمینہ الگورتھم ؛ ایک عین مطابق الگورتھم، سائیکل کے ہائپر گراف کو گراف میں تبدیل کرنے کے تمام طریقوں کو منظم طریقے سے چیک کرتا ہے۔ الگورتھم وقت پر چلتا ہے، جہاں s ایک سیٹ کا سائز ہے جس میں ہر 3 سائیکل سے ایک آرک ہوتا ہے۔ لمبائی k کے چکروں، اور غیر محدود لمبائی کی زنجیروں کو متفرق عطیہ دہندگان کے تبادلے کا سلسلہ شروع کرنے کے لیے استعمال کیا جا سکتا ہے، یہ کوئی چکر نہیں ہے۔ اس طرح کے سلسلے میں، آپریشنز کو بیک وقت کرنے کی ضرورت نہیں ہے: ہر مریض کو اس بات کی ضمانت دینا ممکن ہے کہ اس کے عطیہ دہندہ کے گردے دینے سے پہلے اسے گردہ مل جائے۔ اگر کوئی عطیہ دہندہ عیب دار ہے، تو یہ زنجیر کو توڑ دیتا ہے، لیکن یہ ان مریضوں کو نقصان نہیں پہنچاتا جن کے عطیہ دہندہ نے پہلے ہی گردے دے دیے ہیں، اس لیے یہ انفرادی معقولیت کو نہیں توڑتا ہے۔ اینڈرسن، اشلاگی، گامرنک اور روتھ زیادہ سے زیادہ k اور لامحدود لمبائی کی زنجیروں پر لمبائی کے چکروں میں زیادہ سے زیادہ کارڈینالیٹی پیکنگ تلاش کرنے کے لیے دو الگورتھم پیش کرتے ہیں: ایک انٹیجر لکیری پروگرامنگ اور رکاوٹ پیدا کرنے پر مبنی ہے ؛ دوسرا ٹریول سیلز مین کے مسئلے کے حل پر مبنی ہے۔ غیر یقینی ٹرانسپلانٹس اوکے ای میں ابتدائی نظریاتی کاموں نے فرض کیا کہ، ایک بار تبادلوں کے ایک سیٹ کا تعین ہونے کے بعد، ان سب پر عمل درآمد کیا جائے گا۔ تاہم، عملی طور پر، ٹرانسپلانٹ منسوخ کیے جا سکتے ہیں۔ مثال کے طور پر، ٹرانسپلانٹ سے ٹھیک پہلے کیے گئے طبی معائنے سے یہ ظاہر ہو سکتا ہے کہ عطیہ دہندہ مریض کے ساتھ مطابقت نہیں رکھتا، حالانکہ ڈیٹا بیس میں وہ مطابقت کے طور پر رجسٹرڈ ہیں۔ لہذا، نئے کاموں کا مقصد ٹرانسپلانٹ کی متوقع تعداد کو زیادہ سے زیادہ کرنا ہے۔ مثال کے طور پر، الویلوس، کلیمینٹووا اور ویانا اس مسئلے کے لیے ایک برانچ اینڈ پرائس الگورتھم پیش کرتے ہیں۔ گردے کے تبادلے کے لیے انٹیجر پروگرامنگ ماڈل کے مزید حوالہ جات۔ حوالہ جات اصلاح کے الگورتھم اور طریقے اعضاء کا عطیہ