الگوریتم نیدلمن وانچ

الگوریتم نیدلمن وانچ ( به انگلیسی: Needleman–Wunsch algorithm ) یک همترازی سراسری بر دو ترتیب متوالی ( مانند A و B ) انجام می دهد. معمولاً در بیوانفورماتیک برای همترازی توالی های پروتئینی یا نوکلئوتیدی کاربرد دارد. این الگوریتم در سال ۱۹۷۰ توسط سول نیدلمن و کریستین وانچ ارائه شد. [ ۱]
این الگوریتم نمونه ای از برنامه ریزی پویا است و اولین کاربرد برنامه ریزی پویا در مقایسهٔ توالی های زیستی است.
این الگوریتم را می توان برای هرجفت رشته ای به کار برد. در راهنمای زیر از دو توالی دی ان ای کوتاه به عنوان مثال استفاده می شود:
GCATGCT GATTACA ساخت جدول ابتدا جدولی مانند زیر بسازید:
در سطر اول، جدول رشته اول قرار می گیرد و محل شروع این رشته ستون سوم است. هم چنین رشته دوم در ستون اول قرار گرفته و محل شروع آن از سطر سوم است.
در ابتدا هیچ عددی در جدول وجود ندارد.
هنگام هم تراز سازی دو رشته، ممکن است سه حالت برای حروف رخ دهد:
• تطابق: دو حرف موجود در جایگاه کنونی باهم یکسان باشند.
• عدم تطابق: دو حرف موجود در جایگاه کنونی با یکدیگر متفاوت باشند.
• درج یا حذف: یک حرف از یک رشته با یک جای خالی ( فاصله ) از رشته دیگر هم تراز شود.
به هر یک از این حالات یک امتیاز اختصاص داده می شود و امتیاز یک هم تراز سازی از جمع امتیاز های هر جفت از حروف متناظر به دست می آید.
سیستم های متفاوتی برای امتیاز دهی وجود دارند که تعدادی از آن ها در بخش سیستم های امتیاز دهی ذکر شده اند.
سیستم استفاده شده در اینجا، همان سیستم الگوریتم نیدلمن - وانچ است که در آن امتیاز تطابق 1+ و امتیاز عدم تطابق، درج یا حذف 1 - می باشد. [ ۱] به طور مثال امتیاز هم ترازی زیر برابر 2 - است زیرا:
GCATG - CT GATT - ACA +1 - 1 - 1+1 - 1 - 1+1 - 1=3 - 5= - 2 پر کردن جدول از ستون دوم سطر دوم شروع کنید و در آن مقدار 0 را قرار دهید. سپس سطر به سطر پیش روید و امتیاز هر خانه را محاسبه کنید. این امتیاز از اضافه کردن امتیاز خانه مجاور سمت چپ، بالا یا بالا چپ ( به صورت قطری ) به امتیاز مناسب برای تطابق، عدم تطابق یا درج - حذف به دست می آید.
در واقع برای محاسبه امتیاز 3 گزینه وجود دارد:
• مسیری که از خانه سمت چپ یا بالا می آید، باعث ایجاد یک درج و حذف می شود پس باید امتیاز خانه چپ یا بالا را با امتیاز درج - حذف جمع کرد.