Maximal unique match
ایک زیادہ سے زیادہ منفرد میچ یا ایم یو ایم، مختصر طور پر، کمپیوٹیشنل بائیولوجی میں جینومز کی متعدد ترتیب کی صف بندی میں ایک اہم قدم کا حصہ ہے۔ ایم یو ایم اور دیگر ممکنہ اینکرز کی شناخت، ایم یو ایممر جیسے بڑے صف بندی کے نظام میں پہلا قدم ہے۔ اینکر دو جینوم کے درمیان کے علاقے ہیں جہاں وہ انتہائی ملتے جلتے ہیں۔ یہ سمجھنے کے لیے کہ ایم یو ایم کیا ہے ہم مخفف میں ہر لفظ کو انفرادی طور پر توڑا جا سکتا ہے۔ مماثلت کا مطلب یہ ہے کہ سبسٹرنگ سیدھا ہونے کے لیے دونوں ترتیبات میں ہوتی ہے۔ منفرد کا مطلب یہ ہے کہ سبسٹرنگ ہر ترتیب میں صرف ایک بار ہوتی ہے۔ آخر میں، زیادہ سے زیادہ بیان کرتا ہے کہ سبسٹرنگ کسی اور بڑی تار کا حصہ نہیں ہے جو دونوں سابقہ ضروریات کو پورا کرتی ہے۔ اس کے پیچھے خیال یہ ہے کہ لمبے سلسلے جو بالکل ملتے جلتے ہیں اور ہر جینوم میں صرف ایک بار پائے جاتے ہیں تقریبا یقینی طور پر عالمی صف بندی کا حصہ ہیں۔ رسمی تعریف "دو جینوم اے اور بی کو دیکھتے ہوئے، میکسمل یونیک میچ (ایم یو ایم) سبسٹرنگ اے اور بی کا ایک عام سبسٹرنگ ہے جس کی لمبائی ایک مخصوص کم از کم لمبائی ڈی (ڈیفالٹ ڈی = 20) سے زیادہ ہے، یعنی اسے کسی بھی سرے پر بغیر کسی مطابقت کے بڑھایا نہیں جا سکتا ؛ اور یہ دونوں ترتیبات میں منفرد ہے" الگورتھم دو بہت طویل جینوم ترتیبات میں ایم یو ایم کے سیٹ کی شناخت کرنا کمپیوٹیشنل طور پر معمولی نہیں ہے۔ متعدد ترتیب کی صف بندی میں ایم یو ایم کی شناخت کرنے کے کئی الگورتھمک طریقے ہیں۔ سب سے آسان اور سست ترین طریقہ بروٹ فورس کا استعمال کرنا ہے جہاں جینوم میں ہر انڈیکس اور جینوم میں ہر انڈیکس کے لیے، آپ اور کے طویل ترین مشترکہ سابقہ کا حساب لگاتے ہیں۔ اگلا آپ کو اس بات کی ضمانت دینی چاہیے کہ لمبائی کم از کم کہاں ہے جہاں کم از کم ایم یو ایم سائز متعین ہے۔ آخر میں آپ کو یہ یقینی بنانا چاہیے کہ یہ دونوں جینوموں میں منفرد ہے۔ بروٹ فورس طریقہ کار کی پیچیدگی اس طرح ہے۔ حقیقت میں اگرچہ ایم یو ایم کی شناخت اور کے لیے ایک عمومی لاحقہ درخت بنا کر کی جاتی ہے۔ اس کے بعد تمام اندرونی نوڈس کے لیے ایک فہرست بنائی جاتی ہے جس میں ہر جینوم کی ترتیب سے بالکل ایک بچہ ہوتا ہے۔ ان نوڈس میں سے ہر ایک کے لیے (ہم جینوم سے بچوں کی شناخت کریں گے اور جینوم سے بچوں کی شناخت کریں گے) اس کی جانچ کریں اور ان لوگوں کے لیے جہاں یہ حالات ہیں، ہم جانتے ہیں کہ یہ ایک ایم یو ایم ہے۔ اس صورت میں پیچیدگی کم ہو جاتی ہے۔ نیچے دی گئی مثال میں ابتدائی سٹرنگ اور 1 کا اے دیا گیا ہے، ایم یو ایم جی اور ٹی اے ہونے چاہئیں۔ سرخ پتی اس بات کی نشاندہی کرتی ہے کہ پتی سٹرنگ S سے آئی ہے اور نیلی پتی سٹرنگ کی نشاندہی کرتی ہے۔ A پر اندرونی نوڈ کو مسترد کر دیا گیا تھا کیونکہ اس کا مطلب ہے کہ دونوں A سے پہلے آنے والا کردار ایک جیسا (T) ہے، یہ وہ حالت ہے جہاں ترتیبات ایک بڑی منفرد ترتیب سے تعلق رکھتے ہیں۔ سی پر اندرونی نوڈ کو خارج کر دیا جاتا ہے کیونکہ اس کے ایس سے دو بچے ہیں۔ یہ ہمیں جی اور ٹی اے کے ایم یو ایم کے ساتھ چھوڑ دیتا ہے۔ مثال ایم یو ایم کی مزید وضاحت کے لیے، ہم مندرجہ ذیل مثال لیتے ہیں۔ فرض کریں کہ d = 3 اور ہمارے دو جینوم مندرجہ ذیل ہیں: S = CTACTCTCATCTCTCAGTCAAGTCAGTCAGGCTAAGTCAGTCAGTCAGTCTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT $TGT کم از کم d لمبائی میں ہے، دونوں ترتیبات میں صرف ایک بار ہوتا ہے، اور بائیں طرف کے حروف اور ایک ایسی مثال کی وضاحت کرنے کے لیے جہاں توسیع کی ضرورت ہے تاکہ یہ یقینی بنایا جا سکے کہ ہمارا ایم یو ایم ایک بڑی ترتیب کا حصہ نہیں ہے اور منفرد ہے، مندرجہ ذیل کو لیں: S = CTACCCTCAAGTCATCGCGGCTT #T = CTGGCTAAGTCAGGCGTCTGGCTTT $اے ٹی جی کو ایم یو ایم کے طور پر جانچنے کے معاملے میں دو مسائل ہیں کیونکہ اے ٹی جی منفرد نہیں ہے اور یہ ایک بڑے تسلسل کا بھی حصہ ہے جیسا کہ یہاں دکھایا گیا ہے: S = CTACCCTCTAAGTCAGGCGGCTGTCTTT #T = CTGGCTAAGTCAGTCGGTCTTT $لہذا اس ترتیب کی توسیع اس طریقہ کار کا استعمال کرتے ہوئے بار بار ایک حتمی پروڈکٹ تیار ہوتا ہے جہاں وضاحت کے لیے ہر ایم یو ایم کی شناخت کی جاتی ہے ہر ایم یو ایم رنگین کوڈڈ ہوتا ہے: ایس = سی ٹی اے سی سی جی #ٹی = اے سی ٹی ٹی جی ٹی $زیادہ سے زیادہ عین مطابق میچ (ایم ای ایم) ایم یو ایم ایک بڑے سیٹ کا ذیلی سیٹ ہے جسے زیادہ سے زیادہ عین مطابق میچ یا ایم ای ایم ایس کہا جاتا ہے۔ ایم ای ایم میں ایم یو ایم کی انفرادیت کی حالت میں نرمی کی جاتی ہے۔ ایم ای ایم مقامی صف بندی کی طرح ہوتے ہیں لیکن اس معاملے میں صرف ان ترتیبات کی نشاندہی کرتے ہیں جہاں کوئی خلا نہیں ہوتا ہے۔ یہ بھی دیکھیں کہ ملٹی پل سیکوینس ایلائنمنٹ حوالہ جات سیکوینس ایلائنمنٹ الگورتھم