Tree alignment
کمپیوٹیشنل فائیلوجینیٹکس میں، درخت کی صف بندی ایک کمپیوٹیشنل مسئلہ ہے جس کا تعلق متعدد ترتیب کی صف بندی، یا ڈی این اے، آر این اے، یا پروٹین کے تین یا زیادہ ترتیبات کی صف بندی سے ہے۔ ترتیبات کو ایک فائیلوجنیٹک درخت میں ترتیب دیا جاتا ہے، جو انواع یا ٹیکسا کے درمیان ارتقائی تعلقات کو ماڈلنگ کرتا ہے۔ ترتیبات کے درمیان ترمیم کے فاصلے کا حساب درخت کے اندرونی عمودی حصوں میں سے ہر ایک کے لیے اس طرح لگایا جاتا ہے کہ درخت کے اندر تمام ترمیم کے فاصلے کا مجموعہ کم سے کم ہو جائے۔ قابل انتظام درخت کے سائز اور کمپیوٹیشنل کوشش کے درمیان مختلف تجارت کے ساتھ کئی الگورتھم میں سے ایک کا استعمال کرتے ہوئے درخت کی صف بندی کو پورا کیا جا سکتا ہے۔ تعریف ان پٹ: ترتیبات کا ایک مجموعہ، ایک فائیلوجنیٹک ٹری لیف لیبلڈ اور ترتیبات کے درمیان ایک ایڈیٹ ڈسٹنس فنکشن۔ آؤٹ پٹ: اس طرح کے اندرونی عمودی حصوں کی لیبلنگ جو کم سے کم ہو، جہاں کے اختتامی نکات کے درمیان ترمیم کا فاصلہ ہے۔ کام این پی سخت ہے۔ پس منظر کی ترتیب کی صف بندی بائیو انفارمیٹکس میں، انفارمیشن پروسیسنگ کا بنیادی طریقہ ترتیب کے ڈیٹا کا موازنہ کرنا ہے۔ ماہر حیاتیات اس کا استعمال حیاتیاتی ترتیبات میں فنکشن، ساخت اور ارتقائی معلومات کو دریافت کرنے کے لیے کرتے ہیں۔ مندرجہ ذیل تجزیے ترتیب اسمبلی پر مبنی ہیں: فائیلوجنیٹک تجزیہ، ہیپلوٹائپ کا موازنہ، اور آر این اے کی ساخت کی پیش گوئی۔ لہذا، ترتیب کی صف بندی کی کارکردگی ان مسائل کو حل کرنے کی افادیت کو براہ راست متاثر کرے گی۔ ایک عقلی اور موثر ترتیب کی صف بندی کو ڈیزائن کرنے کے لیے، الگورتھم مشتق بائیو انفارمیٹکس کے میدان میں تحقیق کی ایک اہم شاخ بن جاتا ہے۔ عام طور پر، ترتیب کی صف بندی کا مطلب ہے حروف کو شامل کرکے، حروف کو حذف کرکے، یا ہر تار کے لیے جگہ شامل کرکے سب سے زیادہ مماثلت کے ساتھ دو یا زیادہ تاروں سے ایک تار بنانا۔ ایک سے زیادہ ترتیب کی صف بندی کا مسئلہ عام طور پر جوڑی کے لحاظ سے ترتیب کی صف بندی پر مبنی ہوتا ہے اور فی الحال، جوڑی کے لحاظ سے ترتیب کی صف بندی کے مسئلے کے لیے، ماہر حیاتیات اس کا بہترین حل حاصل کرنے کے لیے ایک متحرک پروگرامنگ نقطہ نظر استعمال کر سکتے ہیں۔ تاہم، متعدد ترتیب کی صف بندی کا مسئلہ اب بھی بائیو انفارمیٹکس میں زیادہ چیلنجنگ مسائل میں سے ایک ہے۔ اس کی وجہ یہ ہے کہ متعدد ترتیب کی صف بندی کے لیے بہترین حل تلاش کرنا ایک این پی مکمل مسئلہ کے طور پر ثابت ہوا ہے اور صرف ایک قریب ترین بہترین حل حاصل کیا جا سکتا ہے۔ ڈسٹنس میٹرکس میتھڈ ڈسٹنس میتھڈ حروف کے اندراج، حذف کرنے اور متبادل کے کم از کم آپریشن نمبر کی پیمائش کرتا ہے جو تاروں کے جوڑے پر چلائے جانے پر ایک ترتیب u کو دوسری ترتیب v میں تبدیل کرنے کے لیے درکار ہوتے ہیں۔ ترمیم کے فاصلے کا حساب متحرک پروگرامنگ پر مبنی ہو سکتا ہے، اور مساوات O (|u | × |v |) وقت میں ہے، جہاں |u | اور |v | u اور v کی لمبائی ہیں۔ ترمیم کے فاصلے کا موثر تخمینہ ضروری ہے کیونکہ فاصلہ کا طریقہ کمپیوٹیشنل حیاتیات میں ایک بنیادی اصول ہے۔ موروثی خصوصیات کے افعال کے لیے "سمیٹریزیشن" استعمال کیا جا سکتا ہے۔ ترمیم کے فاصلے کا حساب لگانے کے لیے استعمال ہونے والے افعال کی ایک سیریز کی وجہ سے، مختلف افعال کے نتیجے میں مختلف نتائج سامنے آسکتے ہیں۔ ٹری الائنمنٹ کے مسئلے کے لیے زیادہ سے زیادہ ایڈیٹ ڈسٹنس فنکشن تلاش کرنا ضروری ہے۔ درخت کی صف بندی کا مسئلہ NP-سخت مسئلہ کا باعث بنتا ہے، جہاں اسکورنگ کے طریقے اور حروف تہجی کے سائز محدود ہوتے ہیں۔ یہ ایک الگورتھم کے طور پر پایا جا سکتا ہے، جو بہتر حل تلاش کرنے کے لیے استعمال ہوتا ہے۔ تاہم، اس کی کارکردگی اور تعداد کے سلسلے کے درمیان ایک متغیر تعلق ہے، جس کا مطلب ہے کہ جب ترتیب کی لمبائی بہت زیادہ ہوتی ہے، تو نتائج حاصل کرنے کے لیے درکار حساب کا وقت بہت زیادہ ہوتا ہے۔ قریب ترین بہتر حل حاصل کرنے کے لیے ستاروں کی صف بندی کا استعمال درختوں کی صف بندی کے استعمال سے زیادہ تیز ہے۔ تاہم، متعدد ترتیب کی مماثلت کی ڈگری جو بھی ہو، ستارے کی صف بندی کی وقت کی پیچیدگی کا ترتیب نمبر کے مربع اور ترتیب کی اوسط لمبائی کے مربع کے ساتھ متناسب تعلق ہوتا ہے۔ ہمیشہ کی طرح، ایم ایس اے میں ترتیب اتنی لمبی ہے کہ یہ غیر موثر یا ناقابل قبول بھی ہے۔ لہذا، وقت کی پیچیدگی کو لکیری تک کم کرنے کا چیلنج درختوں کی صف بندی کے بنیادی مسائل میں سے ایک ہے۔ مشترکہ اصلاح کی حکمت عملی مشترکہ اصلاح ایم ایس اے کے مسائل کو حل کرنے کے لیے ایک اچھی حکمت عملی ہے۔ مشترکہ اصلاح کی حکمت عملی کا خیال یہ ہے کہ اس مسئلے کو حل کرنے کے لیے متعدد ترتیب کی صف بندی کو جوڑی ترتیب کی صف بندی میں تبدیل کیا جائے۔ اس کی تبدیلی کی حکمت عملی پر منحصر ہے، مشترکہ اصلاح کی حکمت عملی کو ٹری الائنمنٹ الگورتھم اور اسٹار الائنمنٹ الگورتھم میں تقسیم کیا جا سکتا ہے۔ کسی دیئے گئے کثیر ترتیب والے سیٹ = {,.,} کے لیے، ایک ارتقائی درخت تلاش کریں جس میں n پتی کے نوڈس ہوں اور اس ارتقائی درخت اور سیٹ کے درمیان ایک سے ایک تعلق قائم کریں۔ ارتقائی درخت کے اندرونی نوڈس کو ترتیب تفویض کرکے، ہم ہر کنارے کے کل اسکور کا حساب لگاتے ہیں، اور تمام کناروں کے اسکور کا مجموعہ ارتقائی درخت کا اسکور ہوتا ہے۔ درخت کی صف بندی کا مقصد ایک تفویض کردہ ترتیب تلاش کرنا ہے، جو زیادہ سے زیادہ اسکور حاصل کر سکے، اور ارتقائی درخت اور اس کے نوڈس کے تفویض کردہ ترتیب سے حتمی مماثل نتیجہ حاصل کر سکے۔ ستاروں کی صف بندی کو درخت کی صف بندی کے ایک خاص معاملے کے طور پر دیکھا جا سکتا ہے۔ جب ہم ستاروں کی صف بندی کا استعمال کرتے ہیں، تو ارتقائی درخت میں صرف ایک اندرونی نوڈ اور n پتی کے نوڈ ہوتے ہیں۔ اندرونی نوڈ کو تفویض کردہ ترتیب کو بنیادی ترتیب کہا جاتا ہے۔ کلیدی لفظ ٹری تھیوری اور آہو-کوراسک سرچ الگورتھم جب متعدد ترتیب کی صف بندی کو جوڑی ترتیب کی صف بندی میں تبدیل کرنے کے لیے مشترکہ اصلاح کی حکمت عملی کا استعمال کیا جاتا ہے، تو بنیادی مسئلہ کو "متعدد ترتیب کی صف بندی کی کارکردگی کو کیسے بہتر بنایا جائے" سے "جوڑی ترتیب کی صف بندی کی کارکردگی کو کیسے بہتر بنایا جائے" میں تبدیل کر دیا جاتا ہے۔ کلیدی لفظ ٹری تھیوری اور آہو-کوراسک سرچ الگورتھم جوڑی کے لحاظ سے ترتیب کی صف بندی کے مسئلے کو حل کرنے کے لیے ایک موثر نقطہ نظر ہے۔ کلیدی لفظ ٹری تھیوری اور آہو-کوراسک سرچ الگورتھم کو یکجا کرنے کا مقصد اس قسم کے مسئلے کو حل کرنا ہے: ایک دی گئی لمبی تار اور مختصر تاروں کے ایک سیٹ کے لیے = {,,.,} (z bul N, z> 1)، سب کا مقام تلاش کریں۔ سیٹ کے ذریعہ تیار کردہ مطلوبہ الفاظ کا درخت استعمال کیا جاتا ہے، اور پھر آہو-کوراسک سرچ الگورتھم کے ذریعے اس مطلوبہ الفاظ کے درخت کے ساتھ تلاش کیا جاتا ہے۔ T میں تمام کے مقام کو تلاش کرنے کے لیے اس طریقہ کار کو استعمال کرنے کی کل وقت کی پیچیدگی O (+ +) ہے، جہاں = | | (کی لمبائی)، = ‡ | | (تمام کی لمبائی کا مجموعہ) اور اس کا مطلب ہے تمام کے لیے واقع ہونے کا مجموعہ۔ کلیدی لفظ ٹری تھیوری سیٹ کا کلیدی لفظ ٹری = {,,.,} (z bul N, z> 1) ایک جڑا ہوا درخت ہے، جس کی جڑ کو K سے ظاہر کیا جاتا ہے، اور یہ کلیدی لفظ ٹری مطمئن کرتا ہے: (1): ہر کنارے واضح طور پر ایک حرف کی حد بندی کرتا ہے۔ (2): ایک ہی نوڈ سے الگ ہونے والے کسی بھی دو کناروں کو مختلف حروف کے مطابق ہونا چاہیے۔ (3) ہر نمونہ (i = 1,2,., z) ایک نوڈ سے مطابقت رکھتا ہے، اور جڑ K سے نوڈ تک کا راستہ سٹرنگ کو بالکل درست طریقے سے ہجے کر سکتا ہے۔ اس کے درخت کے ہر پتی کے نوڈ کے لیے، یہ سیٹ کے مخصوص نمونوں میں سے ایک سے مطابقت رکھتا ہے۔ اس کا استعمال اس سٹرنگ کی نمائندگی کرنے کے لیے کیا جاتا ہے جو جڑ نوڈ سے نوڈ سے جڑا ہوا ہے۔ اس کے بعد طویل ترین لاحقہ کی لمبائی کی نمائندگی کرنے کے لیے استعمال کیا جائے گا (نیز، یہ لاحقہ سیٹ میں موجود نمونوں میں سے ایک کا سابقہ ہے)۔ کلیدی لفظ کے درخت میں جڑ نوڈ سے اس سابقہ کو تلاش کرنا، اور آخری نوڈ کی طرف اشارہ کیا جاتا ہے جب تلاش ختم ہو جاتی ہے۔ مثال کے طور پر، سیٹ = {آلو، ٹیٹو، تھیٹر، دیگر}، اور مطلوبہ الفاظ کا درخت دائیں طرف دکھایا گیا ہے۔ اس مثال میں، اگر = پوٹاٹ، تو = |tat | = 3، اور نوڈ کا ناکامی لنک اس شکل میں دکھایا گیا ہے۔ ناکامی لنک قائم کرنا اہو-کوراسک الگورتھم کی وقت کی پیچیدگی کو بہتر بنانے کی کلید ہے۔ اس کا استعمال اصل کثیر الجہتی وقت کو تلاش کے لیے لکیری وقت تک کم کرنے کے لیے کیا جا سکتا ہے۔ لہذا، کلیدی لفظ کے درخت کے نظریہ کا بنیادی مقصد لکیری وقت میں کلیدی لفظ کے درخت کے تمام ناکامی کے لنکس (جس کا مطلب تمام ایس تلاش کرنا بھی ہے) کو تلاش کرنا ہے۔ یہ فرض کیا جاتا ہے کہ ان تمام نوڈس میں سے ہر ایک، جس کا جڑ نوڈ سے فاصلہ کم یا برابر ہے، پایا جا سکتا ہے۔ اس نوڈ کا جس کا جڑ نوڈ سے فاصلہ + 1 ہے پھر تلاش کیا جا سکتا ہے۔ اس کا پیرنٹ نوڈ ہے، اور نوڈ اور کی نمائندگی کرنے والا حرف ہے۔ (1): اگر نوڈ کا اگلا حرف ہے، تو اس کنارے کے دوسرے نوڈ کو، اور = کے طور پر سیٹ کیا جا سکتا ہے۔ (2): اگر تمام حروف اور اس کے چائلڈ نوڈس کے درمیان تمام کناروں کو تلاش کرنے سے نہیں ہیں، تو یہ پلس کا لاحقہ ہے۔ چونکہ یہ لاحقہ جڑ نوڈ سے شروع ہونے والے سٹرنگ سے ملتا جلتا ہے (سابقہ سے ملتا جلتا)، اس کے بعد کا پتہ لگایا جا سکتا ہے یا نہیں۔ اگر نہیں، تو یہ عمل اس وقت تک جاری رکھا جا سکتا ہے جب تک کہ جڑ نوڈ نہ مل جائے۔ کلیدی لفظ کے درخت میں تمام ناکامی کے لنکس قائم کرنے کے بعد، آہو-کوراسک سرچ الگورتھم کا استعمال لکیری وقت میں تمام (i = 1,2,., z) کے مقامات کو تلاش کرنے کے لیے کیا جاتا ہے۔ اس مرحلے میں وقت کی پیچیدگی O (m + k) ہے۔ دیگر حکمت عملیاں ایم ایس اے، ڈی این اے، آر این اے، اور پروٹین میں، ترتیبات عام طور پر تیار کیے جاتے ہیں اور ان کے بارے میں خیال کیا جاتا ہے کہ ان کا ارتقائی تعلق ہے۔ آر این اے، ڈی این اے کے تیار کردہ نقشوں اور ارتقائی خاندانوں کے ترتیبات کا موازنہ کرکے، لوگ پروٹین کے تحفظ کا اندازہ لگا سکتے ہیں اور ارتقائی ترتیبات کے درمیان فرق کا موازنہ کرکے فعال جین ڈومینز تلاش کر سکتے ہیں۔ عام طور پر، متعدد ترتیب کی صف بندی کے مسائل کو حل کرنے کے لیے ہیورسٹک الگورتھم اور ٹری الائنمنٹ گراف بھی اپنائے جاتے ہیں۔ ہیورسٹک الگورتھم عام طور پر، ہیورسٹک الگورتھم تکراری حکمت عملی پر انحصار کرتے ہیں، جس کا مطلب ہے کہ موازنہ کے طریقہ کار کی بنیاد پر، تکراری عمل کے ذریعے متعدد ترتیب کی صف بندی کے نتائج کو بہتر بنانا۔ ڈیوی ایم نے متعدد ترتیب کی صف بندی کے مسئلے کو حل کرنے کے لیے پارٹیکل سوارم آپٹیمائزیشن الگورتھم کا استعمال کرنے کی تجویز پیش کی۔ اکیڈا تکاہیرو نے ایک ہیورسٹک الگورتھم کی تجویز پیش کی جو اے * سرچ الگورتھم پر مبنی ہے۔ ای برنی نے سب سے پہلے متعدد ترتیب کی صف بندی کے مسئلے کو حل کرنے کے لیے پوشیدہ مارکوف ماڈل کا استعمال کرنے کی تجویز پیش کی۔ اور بہت سے دوسرے ماہر حیاتیات اسے حل کرنے کے لیے جینیاتی الگورتھم کا استعمال کرتے ہیں۔ یہ تمام الگورتھم عام طور پر مضبوط اور ترتیبات کی تعداد کے لیے غیر حساس ہوتے ہیں، لیکن ان میں خامیاں بھی ہیں۔ مثال کے طور پر، پارٹیکل سوارم آپٹیمائزیشن الگورتھم کے نتائج غیر مستحکم ہوتے ہیں اور اس کی خوبیوں کا انحصار بے ترتیب نمبروں کے انتخاب پر ہوتا ہے، اے * سرچ الگورتھم کا رن ٹائم بہت لمبا ہوتا ہے، اور جینیاتی الگورتھم کو مقامی بہترین میں ڈالنا آسان ہوتا ہے۔ درختوں کی صف بندی کا گراف تقریبا، درختوں کی صف بندی کے گراف کا مقصد درختوں کو گراف میں صف بندی کرنا اور آخر میں اعداد و شمار تیار کرنے کے لیے ان کی ترکیب کرنا ہے۔ حیاتیات میں، درختوں کی صف بندی کے گراف (ٹی اے جی) کا استعمال درختوں کے سیٹوں سے ارتقائی تنازعات یا اوور لیپنگ ٹیکس کو دور کرنے کے لیے کیا جاتا ہے اور پھر غیر یقینی صورتحال اور تنازعات کو تلاش کرنے کے لیے ان سے پوچھ گچھ کی جا سکتی ہے۔ صف بندی، ترکیب اور تجزیہ کے طریقوں کو مربوط کرکے، ٹی اے جی کا مقصد متضاد تعلقات اور وسیع پیمانے پر ترتیبات سے حاصل کردہ جزوی اوور لیپنگ ٹیکسون سیٹوں کو حل کرنا ہے۔ اس کے علاوہ، درختوں کی صف بندی کا گراف سپر ٹری اور گرافٹنگ کی مشقوں کے لیے ایک بنیادی نقطہ نظر کے طور پر کام کرتا ہے، جن کا بیری نے سپر ٹری بنانے کے لیے کامیابی سے تجربہ کیا ہے۔ چونکہ درختوں سے گراف میں تبدیلی ان کے ماخذ درختوں سے اسی طرح کے نوڈس اور کناروں پر مشتمل ہوتی ہے، ٹی اے جی مزید تجزیہ کے لیے اصل ماخذ درختوں کا اخراج بھی فراہم کر سکتے ہیں۔ ٹی اے جی صف بندی کرنے والے درختوں کے مجموعے کا ایک مجموعہ ہے۔ یہ متضاد مفروضوں کے ارتقائی تعلقات کو ذخیرہ کر سکتا ہے اور ارتقائی مفروضوں کو تیار کرنے کے لیے ماخذ کے درختوں کی ترکیب کر سکتا ہے۔ لہذا، یہ دیگر صف بندی کے مسائل کو حل کرنے کا ایک بنیادی طریقہ ہے۔ یہ بھی دیکھیں کہ عام درخت کی صف بندی حوالہ جات کمپیوٹیشنل فائیلوجینیٹکس