Smith–Waterman algorithm
اسمتھ-واٹرمین الگورتھم مقامی ترتیب کی صف بندی انجام دیتا ہے ؛ یعنی، نیوکلک ایسڈ کی ترتیب یا پروٹین کی ترتیب کے دو تاروں کے درمیان اسی طرح کے علاقوں کا تعین کرنے کے لیے۔ پوری ترتیب کو دیکھنے کے بجائے، اسمتھ-واٹرمین الگورتھم تمام ممکنہ لمبائی کے حصوں کا موازنہ کرتا ہے اور مماثلت کی پیمائش کو بہتر بناتا ہے۔ الگورتھم سب سے پہلے ٹیمپل ایف اسمتھ اور مائیکل ایس واٹر مین نے 1981 میں تجویز کیا تھا۔ نیڈل مین-ونش الگورتھم کی طرح، جس میں یہ ایک تغیر ہے، اسمتھ-واٹر مین ایک متحرک پروگرامنگ الگورتھم ہے۔ اس طرح، اس میں مطلوبہ خاصیت ہے کہ اسے استعمال کیے جانے والے اسکورنگ سسٹم کے حوالے سے زیادہ سے زیادہ مقامی صف بندی تلاش کرنے کی ضمانت دی جاتی ہے (جس میں متبادل میٹرکس اور گیپ اسکورنگ اسکیم شامل ہے)۔ نیڈل مین-ونش الگورتھم میں بنیادی فرق یہ ہے کہ منفی اسکورنگ میٹرکس خلیات کو صفر پر سیٹ کیا جاتا ہے، جو (اس طرح مثبت اسکورنگ) مقامی صف بندی کو ظاہر کرتا ہے۔ ٹریس بیک کا طریقہ کار سب سے زیادہ اسکور کرنے والے میٹرکس سیل سے شروع ہوتا ہے اور اس وقت تک جاری رہتا ہے جب تک کہ صفر اسکور والے سیل کا سامنا نہ ہو، جس سے سب سے زیادہ اسکور کرنے والی مقامی صف بندی حاصل ہوتی ہے۔ اس کی کیوبک ٹائم پیچیدگی کی وجہ سے، اسے اکثر بڑے پیمانے کے مسائل پر عملی طور پر لاگو نہیں کیا جا سکتا اور اس کی جگہ کمپیوٹیشنل طور پر زیادہ موثر متبادل جیسے (گوٹوہ، 1982)، (الٹسچل اور ایرکسن، 1986)، اور (مائرز اور ملر، 1988) کے حق میں لے لی جاتی ہے۔ 1970 میں، ساؤل بی نیڈل مین اور کرسچن ڈی ونش نے ترتیب کی صف بندی کے لیے ایک ہیورسٹک ہومیولوجی الگورتھم کی تجویز پیش کی، جسے نیڈل مین-ونش الگورتھم بھی کہا جاتا ہے۔ یہ ایک عالمی صف بندی الگورتھم ہے جس میں حساب کے مراحل کی ضرورت ہوتی ہے (اور یہ دونوں ترتیبات کی لمبائی ہوتی ہے)۔ یہ عالمی صف بندی کو ظاہر کرنے کے مقصد سے میٹرکس کے تکراری حساب کا استعمال کرتا ہے۔ اگلی دہائی میں، سنکوف، ریچرٹ، بیئر اور دیگر نے جین کے ترتیبات کا تجزیہ کرنے کے لیے متبادل ہیورسٹک الگورتھم وضع کیے۔ فروخت کنندگان نے ترتیب کے فاصلے کی پیمائش کے لیے ایک نظام متعارف کرایا۔ 1976 میں، واٹر مین اور دیگر۔ خلا کے تصور کو اصل پیمائش کے نظام میں شامل کیا۔ 1981 میں، اسمتھ اور واٹر مین نے مقامی صف بندی کا حساب لگانے کے لیے اپنا اسمتھ-واٹر مین الگورتھم شائع کیا۔ اسمتھ-واٹرمین الگورتھم کافی حد تک وقت کا مطالبہ کرتا ہے: لمبائی کے دو سلسلے کو سیدھ میں لانے کے لیے وقت درکار ہوتا ہے۔ گوٹوہ اور الٹسچل نے الگورتھم کو مراحل کے مطابق بہتر بنایا۔ خلا کی پیچیدگی کو مائرز اور ملر نے (لکیری) سے بہتر بنایا تھا، جہاں مختصر ترتیب کی لمبائی ہے، اس صورت کے لیے جہاں بہت سے ممکنہ بہترین صف بندی میں سے صرف ایک مطلوب ہے۔ چودھری، لی، اور رامچندرن نے بعد میں ان پٹ ترتیب کی کل لمبائی میں جگہ کے استعمال کو لکیری رکھتے ہوئے الگورتھم کی کیش کی کارکردگی کو بہتر بنایا۔ تحریک حالیہ برسوں میں، مختلف قسم کے حیاتیات پر کیے گئے جینوم پروجیکٹوں نے جین اور پروٹین کے لیے بڑے پیمانے پر ترتیب کے اعداد و شمار تیار کیے، جن کے لیے کمپیوٹیشنل تجزیہ کی ضرورت ہوتی ہے۔ ترتیب کی صف بندی جینوں کے درمیان یا پروٹین کے درمیان تعلقات کو ظاہر کرتی ہے، جس سے ان کی ہم آہنگی اور فعالیت کی بہتر تفہیم ہوتی ہے۔ ترتیب کی صف بندی محفوظ ڈومینز اور نقشوں کو بھی ظاہر کر سکتی ہے۔ مقامی صف بندی کے لیے ایک محرک دور سے متعلق حیاتیاتی ترتیبات کے درمیان کم مماثلت والے علاقوں میں درست صف بندی حاصل کرنے میں دشواری ہے، کیونکہ تغیرات نے ارتقائی وقت کے دوران بہت زیادہ 'شور' کا اضافہ کیا ہے تاکہ ان علاقوں کا بامعنی موازنہ کیا جا سکے۔ مقامی صف بندی ایسے علاقوں سے مکمل طور پر گریز کرتی ہے اور مثبت اسکور والے علاقوں پر توجہ مرکوز کرتی ہے، یعنی۔ وہ جن کے پاس ارتقاء کے لحاظ سے محفوظ کردہ مماثلت کا اشارہ ہے۔ مقامی صف بندی کے لیے ایک شرط منفی متوقع سکور ہے۔ متوقع اسکور کی تعریف اوسط اسکور کے طور پر کی جاتی ہے جو اسکورنگ سسٹم (متبادل میٹرکس اور گیپ پینلٹیز) بے ترتیب ترتیب کے لیے حاصل کرے گا۔ مقامی صف بندی کو استعمال کرنے کا ایک اور محرک یہ ہے کہ زیادہ سے زیادہ مقامی صف بندی کے لیے ایک قابل اعتماد شماریاتی ماڈل (کارلن اور الٹسچل کے ذریعے تیار کردہ) موجود ہے۔ غیر متعلقہ ترتیبات کی صف بندی زیادہ سے زیادہ مقامی صف بندی کے اسکور پیدا کرتی ہے جو انتہائی قدر کی تقسیم کی پیروی کرتی ہے۔ یہ خاصیت پروگراموں کو دو ترتیبات کی زیادہ سے زیادہ مقامی صف بندی کے لیے ایک متوقع قدر پیدا کرنے کی اجازت دیتی ہے، جو اس بات کی پیمائش ہے کہ کتنی بار دو غیر متعلقہ ترتیبات ایک زیادہ سے زیادہ مقامی صف بندی پیدا کریں گی جس کا اسکور مشاہدہ شدہ اسکور سے زیادہ یا اس کے برابر ہے۔ بہت کم متوقع اقدار اس بات کی نشاندہی کرتی ہیں کہ زیر بحث دو ترتیبات یکساں ہو سکتے ہیں، یعنی وہ ایک مشترکہ آباؤ اجداد کا اشتراک کر سکتے ہیں۔ الگورتھم صف بندی کرنے کے لیے ترتیبات ہونے دیں، جہاں اور بالترتیب لمبائی ہیں۔ متبادل میٹرکس اور گیپ پینلٹی اسکیم کا تعین کریں۔ - ان عناصر کا مماثلت اسکور جو دو ترتیبات کو تشکیل دیتے ہیں-ایک ایسے وقفے کا جرمانہ جس کی لمبائی ہو ایک اسکورنگ میٹرکس بنائیں اور اس کی پہلی صف اور پہلے کالم کو شروع کریں۔ اسکورنگ میٹرکس کا سائز ہے۔ میٹرکس 0 پر مبنی انڈیکسنگ کا استعمال کرتا ہے۔ درج ذیل مساوات کا استعمال کرتے ہوئے اسکورنگ میٹرکس کو پر کریں۔ صف بندی کا اسکور کہاں ہے اور، اگر لمبائی کے وقفے کے آخر میں اسکور ہے، اگر لمبائی کے وقفے کے آخر میں ہے، تو اس کا مطلب ہے کہ اور تک کوئی مماثلت نہیں ہے۔ ٹریس بیک۔ اسکورنگ میٹرکس میں سب سے زیادہ اسکور سے شروع کرتے ہوئے اور ایک میٹرکس سیل پر ختم ہوتا ہے جس کا اسکور 0 ہوتا ہے، بہترین مقامی صف بندی پیدا کرنے کے لیے ہر اسکور کے ماخذ کی بنیاد پر بار بار ٹریس بیک کریں۔ اسمتھ-واٹرمین الگورتھم دو ترتیبات کو مماثلتوں/مماثلتوں (جسے متبادل بھی کہا جاتا ہے)، اندراجات، اور حذفیوں کے ذریعہ سیدھا کرتا ہے۔ اندراج اور حذف دونوں وہ کارروائیاں ہیں جو خلا کو متعارف کراتی ہیں، جن کی نمائندگی ڈیش کے ذریعے کی جاتی ہے۔ اسمتھ-واٹرمین الگورتھم کے کئی مراحل ہیں: متبادل میٹرکس اور گیپ پینلٹی اسکیم کا تعین کریں۔ ایک متبادل میٹرکس بیس یا امینو ایسڈ کے ہر جوڑے کو میچ یا مماثلت کے لیے ایک اسکور تفویض کرتا ہے۔ عام طور پر میچوں میں مثبت اسکور ملتے ہیں، جبکہ مماثلتوں میں نسبتا کم اسکور ملتے ہیں۔ گیپ پینلٹی فنکشن گیپس کو کھولنے یا بڑھانے کے لیے اسکور لاگت کا تعین کرتا ہے۔ یہ تجویز کیا جاتا ہے کہ صارفین اہداف کی بنیاد پر مناسب اسکورنگ سسٹم کا انتخاب کریں۔ اس کے علاوہ، متبادل میٹرکس اور گیپ پنالٹی کے مختلف امتزاج کو آزمانا بھی ایک اچھا عمل ہے۔ اسکورنگ میٹرکس کو شروع کریں۔ اسکورنگ میٹرکس کے طول و عرض بالترتیب ہر ترتیب کی 1 + لمبائی ہیں۔ پہلی صف اور پہلے کالم کے تمام عناصر کو 0 پر سیٹ کیا گیا ہے۔ اضافی پہلی قطار اور پہلا کالم کسی بھی پوزیشن پر ایک ترتیب کو دوسرے سے صف بندی کرنا ممکن بناتا ہے، اور انہیں 0 پر ترتیب دینے سے ٹرمینل گیپ جرمانے سے پاک ہو جاتا ہے۔ اسکورنگ۔ ہر عنصر کو بائیں سے دائیں، میٹرکس میں اوپر سے نیچے تک اسکور کریں، متبادل کے نتائج (اخترن اسکور) یا خلا (افقی اور عمودی اسکور) کو شامل کرنے پر غور کریں۔ اگر اسکور میں سے کوئی بھی مثبت نہیں ہے، تو اس عنصر کو 0 ملتا ہے۔ بصورت دیگر سب سے زیادہ اسکور استعمال کیا جاتا ہے اور اس اسکور کا ماخذ ریکارڈ کیا جاتا ہے۔ ٹریس بیک۔ سب سے زیادہ اسکور والے عنصر سے شروع کرتے ہوئے، ہر اسکور کے ماخذ کی بنیاد پر بار بار ٹریس بیک کریں، جب تک کہ 0 کا سامنا نہ ہو۔ وہ حصے جن میں دیئے گئے اسکورنگ سسٹم کی بنیاد پر سب سے زیادہ مماثلت کا اسکور ہوتا ہے اس عمل میں پیدا ہوتا ہے۔ دوسری بہترین مقامی صف بندی حاصل کرنے کے لیے، بہترین صف بندی کے نشان سے باہر دوسرے سب سے زیادہ اسکور سے شروع ہونے والے ٹریس بیک کے عمل کو لاگو کریں۔ نیڈل مین-ونش الگورتھم کے ساتھ موازنہ اسمتھ-واٹر مین الگورتھم حصوں کو دو ترتیبات میں ڈھونڈتا ہے جن میں مماثلت ہوتی ہے جبکہ نیڈل مین-ونش الگورتھم دو مکمل ترتیبات کو سیدھا کرتا ہے۔ اس لیے وہ مختلف مقاصد کی تکمیل کرتے ہیں۔ دونوں الگورتھم متبادل میٹرکس، گیپ پینلٹی فنکشن، اسکورنگ میٹرکس، اور ٹریس بیک عمل کے تصورات کا استعمال کرتے ہیں۔ تین اہم فرق یہ ہیں: سب سے اہم فرق یہ ہے کہ اسمتھ-واٹرمین الگورتھم کے اسکورنگ سسٹم میں کوئی منفی اسکور تفویض نہیں کیا گیا ہے، جو مقامی صف بندی کو قابل بناتا ہے۔ جب کسی عنصر کا اسکور صفر سے کم ہوتا ہے، تو اس کا مطلب یہ ہے کہ اس پوزیشن تک کے سلسلے میں کوئی مماثلت نہیں ہے۔ اس عنصر کو پھر صفر پر سیٹ کیا جائے گا تاکہ پچھلی صف بندی سے اثر کو ختم کیا جا سکے۔ اس طرح، حساب بعد میں کسی بھی پوزیشن میں صف بندی تلاش کرنا جاری رکھ سکتا ہے۔ اسمتھ-واٹرمین الگورتھم کا ابتدائی اسکورنگ میٹرکس ایک ترتیب کے کسی بھی حصے کو دوسری ترتیب میں صوابدیدی پوزیشن پر سیدھ کرنے کے قابل بناتا ہے۔ نیڈل مین-ونش الگورتھم میں، تاہم، مکمل ترتیبات کو سیدھا کرنے کے لیے اینڈ گیپ پینلٹی پر بھی غور کرنے کی ضرورت ہے۔ متبادل میٹرکس ہر بیس متبادل یا امینو ایسڈ متبادل کو ایک اسکور تفویض کیا جاتا ہے۔ عام طور پر، میچوں کو مثبت اسکور تفویض کیے جاتے ہیں، اور عدم مطابقت کو نسبتا کم اسکور تفویض کیا جاتا ہے۔ ڈی این اے کی ترتیب کو ایک مثال کے طور پر لیں۔ اگر میچ + 1 حاصل کرتے ہیں، عدم مطابقت-1 حاصل کرتے ہیں، تو متبادل میٹرکس یہ ہے: اس متبادل میٹرکس کو اس طرح بیان کیا جا سکتا ہے: مختلف بیس متبادل یا امینو ایسڈ متبادل کے مختلف اسکور ہو سکتے ہیں۔ امینو ایسڈ کا متبادل میٹرکس عام طور پر بیس کے مقابلے میں زیادہ پیچیدہ ہوتا ہے۔ پی اے ایم، بلوسم دیکھیں۔ گیپ پینلٹی گیپ پینلٹی داخل کرنے یا حذف کرنے کے لیے اسکور کو نامزد کرتی ہے۔ ہر وقفے کے لیے فکسڈ اسکور کا استعمال کرنا ایک سادہ گیپ پینلٹی حکمت عملی ہے۔ تاہم، حیاتیات میں، عملی وجوہات کی بناء پر اسکور کو مختلف طریقے سے شمار کرنے کی ضرورت ہے۔ ایک طرف، دو ترتیبات کے درمیان جزوی مماثلت ایک عام رجحان ہے ؛ دوسری طرف، ایک واحد جین اتپریورتن واقعہ کے نتیجے میں ایک طویل وقفہ داخل ہو سکتا ہے۔ لہذا، طویل وقفہ بنانے والے جڑے ہوئے وقفے عام طور پر متعدد بکھرے ہوئے، مختصر وقفوں سے زیادہ پسند کیے جاتے ہیں۔ اس فرق کو مدنظر رکھنے کے لیے گیپ اوپننگ اور گیپ ایکسٹینشن کے تصورات کو اسکورنگ سسٹم میں شامل کیا گیا ہے۔ گیپ اوپننگ اسکور عام طور پر گیپ ایکسٹینشن اسکور سے زیادہ ہوتا ہے۔ مثال کے طور پر، ای ایم بی او ایس ایس واٹر میں ڈیفالٹ پیرامیٹرز یہ ہیں: گیپ اوپننگ = 10، گیپ ایکسٹینشن = 0.0۔ یہاں ہم گیپ پینلٹی کے لیے دو عام حکمت عملیوں پر تبادلہ خیال کرتے ہیں۔ مزید حکمت عملیوں کے لیے گیپ پینلٹی دیکھیں۔ لمبائی کے وقفے کے لیے گیپ پینلٹی فنکشن ہونے دیں: لکیری گیپ پینلٹی میں وقفہ کھولنے اور بڑھانے کے لیے یکساں اسکور ہوتے ہیں:، جہاں ایک وقفے کی قیمت ہے۔ وقفہ جرمانہ وقفہ کی لمبائی کے براہ راست متناسب ہوتا ہے۔ جب لکیری گیپ پینلٹی کا استعمال کیا جاتا ہے، تو اسمتھ-واٹرمین الگورتھم کو آسان بنایا جا سکتا ہے: آسان الگورتھم اقدامات کا استعمال کرتا ہے۔ جب کسی عنصر کو اسکور کیا جا رہا ہو، تو صرف ان عناصر کے فرق کے جرمانے پر غور کرنے کی ضرورت ہے جو اس عنصر سے براہ راست ملحقہ ہیں۔ ایک افائن گیپ پینلٹی گیپ اوپننگ اور ایکسٹینشن کو الگ سے سمجھتی ہے:، گیپ اوپننگ پینلٹی کہاں ہے، اور گیپ ایکسٹینشن پینلٹی ہے۔ مثال کے طور پر، لمبائی 2 کے وقفے کے لیے جرمانہ ہے۔ اصل اسمتھ-واٹرمین الگورتھم پیپر میں ایک من مانی وقفہ جرمانہ استعمال کیا گیا تھا۔ یہ اقدامات کا استعمال کرتا ہے، اس لیے وقت کا کافی مطالبہ ہے۔ گوٹوہ نے ایک افائن گیپ پینلٹی کے لیے مراحل کو بہتر بنایا، لیکن بہتر کردہ الگورتھم صرف ایک بہترین صف بندی تلاش کرنے کی کوشش کرتا ہے، اور زیادہ سے زیادہ صف بندی ملنے کی ضمانت نہیں ہے۔ الٹسچل نے کمپیوٹیشنل پیچیدگی کو برقرار رکھتے ہوئے تمام بہترین صف بندی تلاش کرنے کے لیے گوٹوہ کے الگورتھم میں ترمیم کی۔ بعد میں، مائرز اور ملر نے نشاندہی کی کہ گوٹوہ اور الٹسچل کے الگورتھم کو اس طریقہ کار کی بنیاد پر مزید ترمیم کی جا سکتی ہے جو 1975 میں ہرشبرگ نے شائع کیا تھا، اور اس طریقہ کو لاگو کیا۔ مائرز اور ملر کا الگورتھم خلا کا استعمال کرتے ہوئے دو ترتیبات کو سیدھا کر سکتا ہے، جس میں مختصر ترتیب کی لمبائی ہوتی ہے۔ چودھری، لی، اور رامچندرن نے بعد میں دکھایا کہ کس طرح ہرشبرگ کے استعمال کردہ حکمت عملی سے مختلف تکراری تقسیم اور فتح کی حکمت عملی کا استعمال کرتے ہوئے لکیری جگہ میں گوٹوہ کے کیش الگورتھم کو موثر طریقے سے چلایا جاتا ہے۔ نتیجے میں الگورتھم اپنی اعلی کیش کارکردگی کی وجہ سے عملی طور پر مائرز اور ملر کے الگورتھم سے زیادہ تیزی سے چلتا ہے۔ گیپ پینلٹی کی مثال ترتیبات کی صف بندی اور ایک مثال کے طور پر لیں۔ جب لکیری گیپ پینلٹی فنکشن استعمال کیا جاتا ہے، تو نتیجہ یہ ہوتا ہے (ای ایم بی او ایس ایس واٹر کے ذریعے انجام دی گئی صف بندی۔ متبادل میٹرکس ڈی این اے فل ہے (مماثلت اسکور: + 5 حروف سے ملنے کے لیے بصورت دیگر-4)۔ گیپ اوپننگ اور ایکسٹینشن بالترتیب 0.0 اور 1 ہیں): جب افائن گیپ پینلٹی استعمال کی جاتی ہے، تو نتیجہ یہ ہوتا ہے (گیپ اوپننگ اور ایکسٹینشن بالترتیب 5.0 اور 1.0 ہوتے ہیں): اس مثال سے پتہ چلتا ہے کہ افائن گیپ پینلٹی بکھرے ہوئے چھوٹے وقفوں سے بچنے میں مدد کر سکتی ہے۔ اسکورنگ میٹرکس کا کام دو ترتیبات میں تمام اجزاء کے درمیان ون ٹو ون موازنہ کرنا اور بہترین صف بندی کے نتائج کو ریکارڈ کرنا ہے۔ اسکورنگ کا عمل متحرک پروگرامنگ کے تصور کی عکاسی کرتا ہے۔ حتمی بہترین صف بندی بڑھتی ہوئی بہترین صف بندی کو بار بار بڑھا کر پائی جاتی ہے۔ دوسرے لفظوں میں، موجودہ زیادہ سے زیادہ صف بندی یہ فیصلہ کرنے سے پیدا ہوتی ہے کہ کون سا راستہ (میچ/مماثلت یا خلا داخل کرنا) پچھلے زیادہ سے زیادہ صف بندی سے سب سے زیادہ اسکور دیتا ہے۔ میٹرکس کا سائز ایک ترتیب کی لمبائی جمع 1 دوسرے ترتیب کی لمبائی جمع 1 ہے۔ اضافی پہلی صف اور پہلا کالم ایک ترتیب کو دوسری ترتیب میں کسی بھی پوزیشن پر صف بندی کرنے کے مقصد کو پورا کرتا ہے۔ پہلی لائن اور پہلا کالم دونوں کو 0 پر سیٹ کیا گیا ہے تاکہ اختتامی فرق کو سزا نہ دی جائے۔ ابتدائی اسکورنگ میٹرکس یہ ہے: مثال کے طور پر ڈی این اے کے ترتیبات کی صف بندی لیں اور ایک مثال کے طور پر۔ مندرجہ ذیل اسکیم کا استعمال کریں: متبادل میٹرکس: گیپ پینلٹی: (کا ایک لکیری گیپ پینلٹی) شروع کریں اور اسکورنگ میٹرکس کو پر کریں، جو ذیل میں دکھایا گیا ہے۔ یہ اعداد و شمار پہلے تین عناصر کے اسکورنگ کے عمل کو ظاہر کرتا ہے۔ پیلا رنگ ان اڈوں کی نشاندہی کرتا ہے جن پر غور کیا جا رہا ہے۔ سرخ رنگ اسکور کیے جانے والے سیل کے لیے سب سے زیادہ ممکنہ اسکور کی نشاندہی کرتا ہے۔ ختم شدہ اسکورنگ میٹرکس نیچے بائیں طرف دکھایا گیا ہے۔ نیلا رنگ سب سے زیادہ سکور ظاہر کرتا ہے۔ ایک عنصر ایک سے زیادہ عناصر سے اسکور حاصل کر سکتا ہے، اگر اس عنصر کا سراغ لگایا جائے تو ہر ایک ایک مختلف راستہ بنائے گا۔ ایک سے زیادہ سب سے زیادہ اسکور کی صورت میں، ٹریس بیک ہر سب سے زیادہ اسکور سے شروع کیا جانا چاہیے۔ ٹریس بیک کا عمل نیچے دائیں طرف دکھایا گیا ہے۔ بہترین مقامی صف بندی الٹی سمت میں پیدا ہوتی ہے۔ صف بندی کا نتیجہ یہ ہے: اسمتھ-واٹر مین الگورتھم کا نفاذ، SSEARCH، یو وی اے فاسٹا ڈاؤن لوڈ سے فاسٹا ترتیب تجزیہ پیکیج میں دستیاب ہے۔ اس نفاذ میں پاور پی سی جی 4 اور جی 5 پروسیسرز کے لیے الٹیویک ایکسلریٹڈ کوڈ شامل ہے جو ووزنیاک، 1997 کے نقطہ نظر میں ترمیم کا استعمال کرتے ہوئے موازنہ کو تیز کرتا ہے، اور فرار کی طرف سے تیار کردہ ایس ایس ای 2 ویکٹرائزیشن جو زیادہ سے زیادہ پروٹین سیکوینس ڈیٹا بیس کی تلاش کو کافی عملی بناتی ہے۔ ایک لائبریری، ایس ایس ڈبلیو، اسمتھ-واٹر مین کے بہترین اسکور کے علاوہ صف بندی کی معلومات کو واپس کرنے کے لیے فرار کے نفاذ میں توسیع کرتی ہے۔ تیز تر ورژن ایف پی جی اے کری نے ایف پی جی اے چپس پر مبنی دوبارہ تشکیل پذیر کمپیوٹنگ پلیٹ فارم کا استعمال کرتے ہوئے اسمتھ-واٹرمین الگورتھم کی ایکسلریشن کا مظاہرہ کیا، جس کے نتائج معیاری مائکرو پروسیسر پر مبنی حل پر 28x تک کی رفتار دکھاتے ہیں۔ اسمتھ واٹرمین الگورتھم کا ایک اور ایف پی جی اے پر مبنی ورژن ایف پی جی اے (ورٹیکس-4) کو 2.2 گیگا ہرٹز اوپٹرون پروسیسر پر 100x تک تیز کرتا ہے۔ ٹائم لاجک ڈی سائفر اور کوڈ کیوسٹ سسٹم پی سی آئی ای ایف پی جی اے کارڈز کا استعمال کرتے ہوئے اسمتھ واٹر مین اور فریم سرچ کو بھی تیز کرتے ہیں۔ 2011 کے ماسٹر کے مقالے میں ایف پی جی اے پر مبنی اسمتھ واٹرمین ایکسلریشن کا تجزیہ شامل ہے۔ زیلنکس ایس ڈی اے سی ایل کے ساتھ مرتب کردہ 2016 کی اشاعت اوپن سی ایل کوڈ میں جینوم کی ترتیب کو تیز کرتا ہے، سی پی یو/جی پی یو کی کارکردگی/ڈبلیو کو 12-21 x سے شکست دیتا ہے، ایک بہت ہی موثر نفاذ پیش کیا گیا تھا۔ زیلنکس ورٹیکس-7 2000 ٹی ایف پی جی اے سے لیس ایک پی سی آئی ای ایف پی جی اے کارڈ کا استعمال کرتے ہوئے، فی واٹ سطح کی کارکردگی سی پی یو/جی پی یو سے 12-21 ایکس سے بہتر تھی۔ جی پی یو لارنس لیورمور نیشنل لیبارٹری اور ریاستہائے متحدہ (یو ایس) کے محکمہ توانائی کے جوائنٹ جینوم انسٹی ٹیوٹ نے گرافکس پروسیسنگ یونٹس (جی پی یو) کا استعمال کرتے ہوئے اسمتھ-واٹرمین مقامی ترتیب کی صف بندی کی تلاشوں کا ایک تیز تر ورژن نافذ کیا جس کے ابتدائی نتائج سافٹ ویئر کے نفاذ پر 2x کی رفتار کو ظاہر کرتے ہیں۔ اسی طرح کا طریقہ بائیوفیسیٹ سافٹ ویئر میں 1997 سے پہلے ہی اسی اسپیڈ اپ فیکٹر کے ساتھ نافذ کیا جا چکا ہے۔ این ویڈیا کے سی یو ڈی اے سی پلیٹ فارم میں الگورتھم کے کئی جی پی یو نفاذ بھی دستیاب ہیں۔ جب فرار کے ذریعہ سب سے مشہور سی پی یو نفاذ (x86 فن تعمیر پر SIMD ہدایات کا استعمال کرتے ہوئے) کے مقابلے میں، ایک واحد NVidia GeForce 8800 GTX کارڈ کا استعمال کرتے ہوئے اس حل کی کارکردگی کے ٹیسٹ چھوٹے ترتیبات کے لیے کارکردگی میں معمولی اضافہ ظاہر کرتے ہیں، لیکن بڑے کے لیے کارکردگی میں معمولی کمی۔ تاہم، دوہری این ویڈیا جی فورس 8800 جی ٹی ایکس کارڈز پر چلنے والے وہی ٹیسٹ ٹیسٹ کیے گئے تمام ترتیب کے سائز کے لیے فرار کے نفاذ سے تقریبا دوگنا تیز ہیں۔ ایس ڈبلیو کا ایک نیا جی پی یو سی یو ڈی اے نفاذ اب دستیاب ہے جو پچھلے ورژن سے تیز ہے اور استفسار کی لمبائی پر حدود کو بھی دور کرتا ہے۔ CUDASW + + دیکھیں۔ سی یو ڈی اے پر گیارہ مختلف ایس ڈبلیو نفاذ کی اطلاع دی گئی ہے، جن میں سے تین 30 ایکس کی رفتار کی اطلاع دیتے ہیں۔ SIMD 2000 میں، اسمتھ-واٹرمین الگورتھم کے تیزی سے نفاذ کو انٹیل پینٹیم ایم ایم ایکس پروسیسرز میں دستیاب سنگل انسٹرکشن، ملٹیپل ڈیٹا (SIMD) ٹیکنالوجی اور اسی طرح کی ٹیکنالوجی کا استعمال کرتے ہوئے روگنس اور سیبرگ کی ایک اشاعت میں بیان کیا گیا تھا۔ ووزنیاک (1997) کے نقطہ نظر کے برعکس، نیا نفاذ استفسار کی ترتیب کے متوازی ویکٹرز پر مبنی تھا، نہ کہ اخترن ویکٹرز پر۔ کمپنی سینسل بائیو انفارمیٹکس نے اس نقطہ نظر کا احاطہ کرتے ہوئے پیٹنٹ کے لیے درخواست دی ہے۔ سینسل سافٹ ویئر کو مزید ترقی دے رہا ہے اور تعلیمی استعمال کے لیے قابل عمل آلات مفت فراہم کرتا ہے۔ الگورتھم کا ایک SSE2 ویکٹرائزیشن (فرار، 2007) اب دستیاب ہے جو SSE2 ایکسٹینشنز کے ساتھ انٹیل/AMD پروسیسرز پر ایک 8-16-fold اسپیڈ اپ فراہم کرتا ہے۔ کور مائیکرو آرکیٹیکچر کا استعمال کرتے ہوئے انٹیل پروسیسر پر چلتے وقت ایس ایس ای 2 کا نفاذ 20 گنا اضافہ حاصل کرتا ہے۔ فرار کا ایس ایس ای 2 نفاذ فاسٹا ترتیب موازنہ پیکیج میں ایس ایس ای آر سی ایچ پروگرام کے طور پر دستیاب ہے۔ SSEARCH یورپی بائیو انفارمیٹکس انسٹی ٹیوٹ کے مماثلت تلاش کرنے والے پروگراموں میں شامل ہے۔ عوامی طور پر دستیاب وائٹ پیپر کے مطابق ڈینش بائیو انفارمیٹکس کمپنی سی ایل سی بائیو نے انٹیل 2.17 گیگا ہرٹز کور 2 ڈوو سی پی یو پر ایس ایس ای 2 کے ساتھ معیاری سافٹ ویئر کے نفاذ میں 200 کے قریب کی رفتار حاصل کی ہے۔ انٹیل اور ایڈوانسڈ مائیکرو ڈیوائسز (اے ایم ڈی) پر مبنی لینکس سرورز پر اسمتھ-واٹرمین الگورتھم کا تیز تر ورژن، جین کور 6 پیکیج کے ذریعے سپورٹ کیا جاتا ہے، جسے بائیوسلریشن کے ذریعے پیش کیا جاتا ہے۔ اس سافٹ ویئر پیکیج کے کارکردگی کے معیارات ایک ہی پروسیسر پر معیاری سافٹ ویئر کے نفاذ کے مقابلے میں 10 گنا تیز رفتار دکھاتے ہیں۔ فی الحال بائیو انفارمیٹکس میں واحد کمپنی جو اسمتھ واٹر مین کو تیز کرتے ہوئے ایس ایس ای اور ایف پی جی اے دونوں حل پیش کرتی ہے، سی ایل سی بائیو نے سی ایل سی بائیو انفارمیٹکس کیوب کے ساتھ معیاری سافٹ ویئر کے نفاذ میں 110 سے زیادہ کی رفتار حاصل کی ہے۔ ایس ایس ایس ای 3 کے ساتھ سی پی یوز پر الگورتھم کا تیز ترین نفاذ سویپ سافٹ ویئر (روگنس، 2011) پایا جا سکتا ہے، جو جی این یو افیرو جنرل پبلک لائسنس کے تحت دستیاب ہے۔ متوازی طور پر، یہ سافٹ ویئر سولہ مختلف ڈیٹا بیس ترتیبات سے باقیات کا موازنہ ایک استفسار کے باقیات سے کرتا ہے۔ 375 بقیہ استفسار کی ترتیب کا استعمال کرتے ہوئے ڈوئل انٹیل زیون ایکس 5650 چھ کور پروسیسر سسٹم پر 106 بلین سیل اپ ڈیٹس فی سیکنڈ (جی سی یو پی ایس) کی رفتار حاصل کی گئی، جو فرار کے 'سٹرپڈ' اپروچ پر مبنی سافٹ ویئر سے چھ گنا زیادہ تیز ہے۔ BLOSUM50 میٹرکس کا استعمال کرتے وقت یہ BLAST سے زیادہ تیز ہوتا ہے۔ سی اور سی + + میں ڈائیگنلز ڈبلیو نامی اسمتھ-واٹر مین کا نفاذ، SIMD انسٹرکشن سیٹ (x86 پلیٹ فارم کے لیے SSE4.1 اور پاور پی سی پلیٹ فارم کے لیے AltiVec) کا استعمال کرتا ہے۔ یہ ایک اوپن سورس ایم آئی ٹی لائسنس کے تحت جاری کیا گیا ہے۔ سیل براڈ بینڈ انجن 2008 میں، فرار نے سٹرپڈ اسمتھ-واٹر مین کی بندرگاہ کو سیل براڈ بینڈ انجن میں بیان کیا اور آئی بی ایم کیو ایس 20 بلیڈ اور سونی پلے اسٹیشن 3 پر بالترتیب 32 اور 12 جی سی یو پی ایس کی رفتار کی اطلاع دی۔ حدود جینیاتی اعداد و شمار کی تیز رفتار توسیع موجودہ ڈی این اے ترتیب صف بندی الگورتھم کی رفتار کو چیلنج کرتی ہے۔ ڈی این اے مختلف قسم کی دریافت کے لیے ایک موثر اور درست طریقہ کار کے لیے ضروری ضروریات حقیقی وقت میں متوازی پروسیسنگ کے لیے جدید طریقوں کا مطالبہ کرتی ہیں۔ آپٹیکل کمپیوٹنگ کے طریقوں کو موجودہ برقی نفاذ کے امید افزا متبادل کے طور پر تجویز کیا گیا ہے۔ آپٹ کیم اس طرح کے طریقوں کی ایک مثال ہے۔ بائیو انفارمیٹکس سیکوئنس الائنمنٹ بھی دیکھیں۔ سیکوئنس مائننگ نیڈل مین ونش الگورتھم لیونشٹین فاصلہ فاسٹ حوالہ جات بیرونی لنکس جے ایلینر-اسمتھ واٹر مین الگورتھم B.A.B.A کا ایک اوپن سورس جاوا نفاذ۔ - ایک ایپلٹ (ماخذ کے ساتھ) جو EBI UGENE اسمتھ-واٹرمین پلگ ان میں الگورتھم فاسٹا/SSEARCH-سروسز پیج کی بصری وضاحت کرتا ہے-C + + OPAL میں لکھے گئے گرافیکل انٹرفیس کے ساتھ الگورتھم کا ایک اوپن سورس SSEARCH ہم آہنگ نفاذ-بڑے پیمانے پر بہترین ترتیب کی صف بندی کے لیے ایک SIMD C/C + + لائبریری-MIT لائسنس ایس ایس ڈبلیو کے تحت SIMD انسٹرکشن سیٹس (خاص طور پر SSE4.1) کے ساتھ ایک اوپن سورس C/C + + نفاذ-ایک اوپن سورس C + + لائبریری جو MIT لائسنس میلوڈک ترتیب صف بندی کے تحت اسمتھ-واٹرمین الگورتھم کے SIMD نفاذ کو API فراہم کرتی ہے-میلوڈک ترتیب کے لیے ایک جاوا اسکرپٹ نفاذ۔