نبذة سريعة عن خوارزمية سميث-واترمان

خوارزمية سميث-واترمان (الإنجليزية: Smith–Waterman algorithm) هي خوارزمية تُستخدم في المعلوماتية الحيوية لإجراء المحاذاة المحلية للتسلسلات، أي تحديد المناطق المتشابهة بين سلسلتين من الأحماض النووية أو البروتينات. بدلاً من مقارنة التسلسل بأكمله، تقارن هذه الخوارزمية مقاطع بجميع الأطوال الممكنة وتُحسّن مقياس التشابه.

اقترح الخوارزمية لأول مرة كلٌّ من تمبل إف. سميث ومايكل إس. واترمان عام 1981، وهي تعمل بأسلوب البرمجة الديناميكية مثلما تعمل خوارزمية نيدلمان-وونش التي تُعدّ أصلاً لها. تمتاز بكونها مضمونة لإيجاد المحاذاة المحلية المثلى وفق نظام الترقيم المستخدم.

الفرق الرئيسي بينها وبين خوارزمية نيدلمان-وونش هو أن الخلايا ذات القيم السلبية في مصفوفة الترقيم تُضبط على الصفر. تبدأ عملية التتبع العكسي من الخلية الأعلى درجةً وتستمر حتى تصادف خلية ذات قيمة صفر.

قراءة المقال الكامل على ويكيبيديا ←