» همردیفی گلوبال

همردیفی گلوبال

الگوریتم نیدلمن وانچ (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 گزینه وجود دارد:

• مسیری که از خانه سمت چپ یا بالا می آید، باعث ایجاد یک درج و حذف می شود پس باید امتیاز خانه چپ یا بالا را با امتیاز درج-حذف جمع کرد.

• مسیر قطری باعث ایجاد یک تطابق یا عدم تطابق می شود پس اگر حروف متناظر این سطر و ستون با یکدیگر برابر بودند، باید امتیاز خانه بالا چپ را با امتیاز تطابق و در غیر این صورت با امتیاز عدم تطابق جمع کرد.

در نهایت امتیاز نهایی این خانه با بیشترین امتیاز در میان سه امتیاز به دست آمده برابر است.

با توجه به اینکه خانه های سطر دوم دارای خانه بالا یا بالا-چپ نیستند، پس تنها خانه سمت چپ می تواند برای محاسبه امتیاز استفاده شود. به این ترتیب سطر دوم به ترتیب از چپ دارای امتیاز های 0، 1-، 2-، 3-،…،7- می شود.

استدلالی مشابه برای ستون دوم نیز به کار می رود که در نتیجه آن جدولی به شکل زیر حاصل می شود.

حال برای محاسبه امتیاز خانه سطر سوم و ستون سوم، 3 حالت وجود دارد:

• همسایه قطری این خانه دارای امتیاز 0 بوده و با توجه به اینکه دو حرف متناظر این سطر و ستون(G وG) با یکدیگر تطابق دارند، پس باید این عدد را با امتیاز تطابق یعنی 1 جمع کرد. پس امتیاز به دست آمده در این حالت برابر 1 است.
• همسایه بالایی این خانه دارای امتیاز 1- است و با توجه به اینکه مسیر عمودی نشان دهنده یک فاصله است پس باید این عدد را با 1- جمع کرد. بنا بر این امتیاز این حالت برابر 2- می شود.
• همسایه چپ این خانه نیز دارای امتیاز 1- است و با توجه به اینکه مسیر افقی نشان دهنده یک فاصله است پس باید این عدد را با 1- جمع کرد. بنا بر این امتیاز این حالت نیز برابر 2- می شود.

در نهایت بیشترین امتیاز در میان این 3 یعنی عدد 1 وارد این خانه می شود. هم چنین باید پیکان مربوط را ذخیره کرد که یک پیکان قطری از خانه(3,3) به خانه (2,2) است.

به همین ترتیب تمامی خانه های جدول پر می شوند تا امتیاز نهایی بهترین هم ترازی به دست آید. کامل شده این جدول در شکل 1 آمده است و طبق آن امتیاز بهترین هم ترازی این دو رشته برابر با 0 است.

بازگشت به مبداء

به وسیله تعدادی پیکان مسیری را از گوشه پایین-راست جدول به گوشه بالا-چپ جدول نشان دار کنید. سپس از طریق این مسیر و طبق قوانین زیر توالی متناظر مسیر را بسازید:

• هر پیکان قطری نشان دهنده یک تطابق یا عدم تطابق است پس 2 حرف متناظر سطر و ستون خانه مبدا پیکان با یک دیگر تراز می شوند.

• هر پیکان عمودی یا افقی نشان دهنده یک درج-حذف است.

پیکان افقی یک جای خالی(“-“) را با حرف ستون متناظر مبدا پیکان و پیکان عمودی حرف سطر متناظر مبدا پیکان را با یک جای خالی تراز می کند.

• وجود چندین پیکان برای انتخاب، نشان از چند شاخه شدن هم ترازی ها دارد. اگر دو یا تعداد بیشتری از شاخه ها مسیری از گوشه پایین-راست به بالا-چپ باشند، همگی هم ترازی هایی برای دو توالی هستند.

با توجه به قواعد بالا و طبق شکل 1، یکی از بهترین هم ترازی ها برای دو رشته ذکر شده در زیر آمده است:

GCA-TGCT

G-ATTACA