خوارزمية سميث-واترمان
بدايةً، خوارزمية سميث-واترمان هي خوارزمية تُستعمل في المعلوماتية الحيوية لإجراء المحاذاة المحلية للتسلسلات، أي تحديد المناطق المتشابهة بين سلسلتين من الأحماض النووية أو البروتينات. بدلاً من مقارنة التسلسل بأكمله، تقارن هذه الخوارزمية مقاطع بجميع الأطوال الممكنة وتُحسّن مقياس التشابه. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
وفي السياق ذاته، الفرق الرئيسي بينها وبين خوارزمية نيدلمان-وونش هو أن الخلايا ذات القيم السلبية في مصفوفة الترقيم تُضبط على الصفر. تبدأ عملية التتبع العكسي من الخلية الأعلى درجةً وتستمر حتى تصادف خلية ذات قيمة صفر.
في هذا الإطار، اقترح الخوارزمية لأول مرة كلٌّ من تمبل إف. سميث ومايكل إس. واترمان عام 1981، وهي تعمل بأسلوب البرمجة الديناميكية مثلما تعمل خوارزمية نيدلمان-وونش التي تُعدّ أصلاً لها. تمتاز بكونها مضمونة لإيجاد المحاذاة المحلية المثلى وفق نظام الترقيم المستعمل.
التاريخ
ومن جهة أخرى، من الناحية الحسابية، تستلزم الخوارزمية لمحاذاة تسلسلين بطولَي m وn وقتاً قدره O(mn). وقد طوّر غوتوه وألتشول الخوارزمية بتحسينات ملحوظة، فيما خفّض مايرز وميلر التعقيد الفضائي إلى O(n) خطي.
من جانب آخر، في سنة 1970، اقترح سول نيدلمان وكريستيان وونش خوارزمية نيدلمان-وونش للمحاذاة الشاملة. وفي العقد التالي، قدّم عدد من الباحثين خوارزميات بديلة. عام 1976 أضاف واترمان وزملاؤه مفهوم الفجوات إلى نظام القياس، ثم نشر سميث وواترمان خوارزميتهما للمحاذاة المحلية عام 1981.
الخوارزمية
مقارنة مع خوارزمية نيدلمان-وونش
كذلك، تجد خوارزمية سميث-واترمان المقاطع المتشابهة بين تسلسلين، بينما تُحاذي خوارزمية نيدلمان-وونش تسلسلين كاملين.
عقوبة الفجوة
وعلى صعيد آخر، تُحدد عقوبة الفجوة الدرجة المخصومة عند الإدراج أو الحذف. من الناحية البيولوجية، يُفضَّل وجود فجوة طويلة متصلة على فجوات قصيرة متعددة، لأن حدثاً طفرياً واحداً يمكن أن يُنتج فجوة طويلة. لذلك يُستعمل مفهوما فتح الفجوة وتمديد الفجوة، حيث تكون درجة الفتح أعلى عادةً. المعاملات الافتراضية في برنامج EMBOSS Water مثلاً: فتح الفجوة = 10، تمديد الفجوة = 0.5.
التطبيقات
إضافةً إلى ذلك، البحث في قواعد البيانات البيولوجية: يُعدّ BLAST من أشهر التطبيقات المستوحاة من هذه الخوارزمية.
- الطب الشرعي الجيني: تُستعمل لمقارنة عينات الحمض النووي في التطبيقات الجنائية.
- انظر كذلك
- معلوماتية حيوية
- خوارزمية نيدلمان-وونش
- محاذاة التسلسلات
- BLAST
- مصفوفة BLOSUM
كذلك، اكتشاف المجالات المحفوظة والنمط الحركي: تساعد في الكشف عن المجالات المحفوظة في التسلسلات البيولوجية.
وعلى صعيد آخر، تحليل الجينوم: في أعقاب مشروع الجينوم البشري، باتت محاذاة التسلسلات ضرورة لفهم العلاقات بين الجينات والبروتينات.
الدافع
من جهة ثانية، دافع آخر هو وجود نموذج إحصائي موثوق طوّره كارلين وألتشول للمحاذاة المحلية المثلى، يتيح إنتاج قيمة توقعية تقيس مدى احتمال حصول تسلسلين غير مترابطين على درجة مشابهة. القيم المنخفضة جداً تُشير إلى أن التسلسلين قد يكونان متماثلين ويشتركان في سلف مشترك.
إضافةً إلى ذلك، أحد دوافع استخدام المحاذاة المحلية هو صعوبة الحصول على محاذاة صحيحة في المناطق ذات التشابه المنخفض بين التسلسلات المتباعدة تطورياً، إذ تضيف الطفرات "ضوضاء" كثيرة عبر الزمن التطوري. لذلك تتجنب المحاذاة المحلية هذه المناطق وتُركّز على تلك التي لها درجة موجبة.
مصفوفة الاستبدال
كذلك، تُعيَّن لكل استبدال قاعدة أو حمض أميني درجة محددة. التطابقات تحصل على درجات موجبة وعدم التطابقات على درجات أقل. مثال لمصفوفة استبدال الحمض النووي (تطابق = +1، عدم تطابق = −1):
وفي هذا الصدد، بالنسبة للأحماض الأمينية تكون المصفوفة أكثر تعقيداً، ومن أشهرها مصفوفة BLOSUM ومصفوفة PAM.
الخطوات
وفي هذا السياق، ملء المصفوفة باستخدام المعادلة: H(i,j) = max { 0، H(i-1,j-1)+s(aᵢ,bⱼ)، max{H(i-k,j)−W(k)}، max{H(i,j-k)−W(k)} }
في هذا الإطار، تحديد مصفوفة الاستبدال ونظام ترقيم الفجوات: s(aᵢ, bⱼ) هي درجة تشابه العنصرَين، وW(k) هي عقوبة الفجوة ذات الطول k.
من جانب آخر، لتكن A وB التسلسلَين المراد محاذاتهما، حيث m وn طولاهما على التوالي.
إضافةً إلى ذلك، إنشاء مصفوفة الترقيم وتهيئتها: أبعادها (m+1)×(n+1)، وتُضبط جميع عناصر الصف والعمود الأول على الصفر.
وفي السياق ذاته، التتبع العكسي: يبدأ من الخلية الأعلى درجةً وينتهي عند الصفر لتوليد أفضل محاذاة محلية.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟