موضوع مقاله: الگوریتم نیدلمن-وانچ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم نیدلمن-وانچ | مقدمه: الگوریتم نیدلمن وانچ یک همترازی سراسری بر دو ترتیب متوالی (مانند A و B) انجام می‌دهد. | ## بخش 1: الگوریتم نیدلمن-وانچ | معمولاً در بیوانفورماتیک برای همترازی توالی‌های پروتئینی یا نوکلئوتیدی کاربرد دارد. این الگوریتم نمونه‌ای از برنامه‌ریزی پویا است و اولین کاربرد برنامه‌ریزی پویا در مقایسهٔ توالی‌های زیستی است. انتخاب سیستم امتیاز دهی هنگام هم تراز سازی دو رشته، ممکن است سه حالت برای حروف رخ دهد: تطابق: دو حرف موجود در جایگاه کنونی باهم یکسان باشند. به هر یک از این حالات یک امتیاز اختصاص داده می شود و امتیاز یک هم تراز سازی از جمع امتیاز های هر جفت از حروف متناظر به دست می آید. سیستم های متفاوتی برای امتیاز دهی وجود دارند که تعدادی از آن ها در بخش سیستم های امتیاز دهی ذکر شده اند. سیستم استفاده شده در اینجا، همان سیستم الگوریتم نیدلمن-وانچ است که در آن امتیاز تطابق 1+ و امتیاز عدم تطابق، درج یا حذف 1- می باشد. این امتیاز از اضافه کردن امتیاز خانه مجاور سمت چپ، بالا یا بالا چپ (به صورت قطری) به امتیاز مناسب برای تطابق، عدم تطابق یا درج-حذف به دست می آید. در واقع برای محاسبه امتیاز 3 گزینه وجود دارد: مسیری که از خانه سمت چپ یا بالا می آید، باعث ایجاد یک درج و حذف می شود پس باید امتیاز خانه چپ یا بالا را با امتیاز درج-حذف جمع کرد. مسیر قطری باعث ایجاد یک تطابق یا عدم تطابق می شود پس اگر حروف متناظر این سطر و ستون با یکدیگر برابر بودند، باید امتیاز خانه بالا چپ را با امتیاز تطابق و در غیر این صورت با امتیاز عدم تطابق جمع کرد. در نهایت امتیاز نهایی این خانه با بیشترین امتیاز در میان سه امتیاز به دست آمده برابر است. با توجه به اینکه خانه های سطر دوم دارای خانه بالا یا بالا-چپ نیستند، پس تنها خانه سمت چپ می تواند برای محاسبه امتیاز استفاده شود. به این ترتیب سطر دوم به ترتیب از چپ دارای امتیاز های 0، 1-، 2-، 3-،...،7- می شود. استدلالی مشابه برای ستون دوم نیز به کار می رود که در نتیجه آن جدولی به شکل زیر حاصل می شود. T C G T A C G 7- 6- 5- 3- 3- 2- 1- 0 1- G 2- A 3- T 4- T 5- A 6- C 7- A حال برای محاسبه امتیاز خانه سطر سوم و ستون سوم، 3 حالت وجود دارد: همسایه قطری این خانه دارای امتیاز 0 بوده و با توجه به اینکه دو حرف متناظر این سطر و ستون(G وG) با یکدیگر تطابق دارند، پس باید این عدد را با امتیاز تطابق یعنی 1 جمع کرد. همسایه بالایی این خانه دارای امتیاز 1- است و با توجه به اینکه مسیر عمودی نشان دهنده یک فاصله است پس باید این عدد را با 1- جمع کرد. | ## بخش 2: الگوریتم نیدلمن-وانچ | همسایه چپ این خانه نیز دارای امتیاز 1- است و با توجه به اینکه مسیر افقی نشان دهنده یک فاصله است پس باید این عدد را با 1- جمع کرد. هم چنین باید پیکان مربوط را ذخیره کرد که یک پیکان قطری از خانه(3,3) به خانه (2,2) است. G 1- 0 1 1- G به همین ترتیب تمامی خانه های جدول پر می شوند تا امتیاز نهایی بهترین هم ترازی به دست آید. کامل شده این جدول در شکل 1 آمده است و طبق آن امتیاز بهترین هم ترازی این دو رشته برابر با 0 است. بازگشت به مبداء به وسیله تعدادی پیکان مسیری را از گوشه پایین-راست جدول به گوشه بالا-چپ جدول نشان دار کنید. سپس از طریق این مسیر و طبق قوانین زیر توالی متناظر مسیر را بسازید: هر پیکان قطری نشان دهنده یک تطابق یا عدم تطابق است پس 2 حرف متناظر سطر و ستون خانه مبدا پیکان با یک دیگر تراز می شوند. پیکان افقی یک جای خالی("-") را با حرف ستون متناظر مبدا پیکان و پیکان عمودی حرف سطر متناظر مبدا پیکان را با یک جای خالی تراز می کند. اگر دو یا تعداد بیشتری از شاخه ها مسیری از گوشه پایین-راست به بالا-چپ باشند، همگی هم ترازی هایی برای دو توالی هستند. با توجه به قواعد بالا و طبق شکل 1، یکی از بهترین هم ترازی ها برای دو رشته ذکر شده در زیر آمده است: GCA-TGCT G-ATTACA سیستم های امتیاز دهی سیستم پایه ساده ترین سیستم امتیاز دهی به هر یک از سه حالت تطابق، عدم تطابق و درج-حذف یک مقدار نسبت می دهد. به عنوان مثال ممکن است امتیاز تطابق برابر 1 و امتیاز عدم تطابق یا درج-حذف 1- در نظر گرفته شود. به عنوان مثالی دیگر ممکن است به تطابق امتیاز 0 و به عدم تطابق و درج-حذف امتیاز 1- نسبت داده شود. به عنوان مثال اگر وجود فاصله را اتفاق بدی در هم ترازی در نظر بگیریم، میتوانیم از امتیاز بندی مانند مثال زیر استفاده کنیم: امتیاز تطابق =1+ امتیاز عدم تطابق=1- امتیاز فاصله=7- ماتریس مشابهت سیستم های امتیاز دهی پیچیده تر، نه تنها برای نوع جایگزینی بلکه برای حروف مختلف نیز امتیاز های متفاوتی در نظر میگیرند. به عنوان مثال، ممکن است به تطابق بین 2 حرف A امتیاز 1 و به تطابق بین 2 حرف G امتیاز 3 داده شود. به عنوان مثال ممکن است به دو حرف A,G امتیاز 1- و به دو حرف T,G امتیاز 2- اختصاص داده شود. ماتریس زیر نمونه ای از ماتریس های مشابهت برای مثال بالاست: GATC 1- 1- 1- 1 C 2- 1- 1 1- T 1- 1 1- 1- A 3 1- 2- 1- G به عنوان مثال، ماتریس زیر، ماتریس مشابهت امتیاز گذاری مورد استفاده در شکل 1 است: GATC 1- 1- 1- 1 C 1- 1- 1 1- T 1- 1 1- 1- A 1 1- 1- 1- G با توجه به اینکه امتیاز عدم تطابق دو حرف مثلا A و T با امتیاز عدم تطابق T و A برابر است، ماتریس مشابهت ماتریسی متقارن است. | ## بخش 3: الگوریتم نیدلمن-وانچ | ماتریس های امتیاز دهی مختلف برای دادن وزن های متفاوت و مناسب شرایط به حالات مختلفی که ممکن است رخ دهند، ساخته می شوند. این ماتریس های وزن دار به ویژه در هم تراز سازی توالی های پروتئینی کاربرد دارند زیرا فراوانی آمینو اسید های مختلف با یکدیگر متفاوت است. جریمه پرش هنگام هم ترازی توالی ها معمولا درج-حذف به وجود می آید که گاهی تعداد زیادی از آن ها پشت سر هم قرار میگیرند. از نظر زیستی، یک فاصله بزرگ با احتمال بیشتری از یک حذف بزرگ ناشی می شود تا از چندین حذف کوچک. راه ساده و معمول این امتیاز دهی این است که برای شروع یک فاصله که در واقع یک درج-حذف جدید است یک جریمه بالا و برای گسترش فاصله که در واقع گسترش درج-حذف هاست جریمه پایین تری در نظر بگیریم. برای مثال، برای درج-حذف جدید می توان امتیاز 6- و برای گسترش آن امتیاز 1- را در نظر گرفت. یک ارائهٔ جدید امتیازها برای کارکترهای همتراز شده توسط ماتریس تطابق مشخص می‌شود. در اینجا تطابقی برای کارکترهای a و b به‌شمار می‌رود که از یک جریمه پرش خطی، که اینجا d نامیده می‌شود. برای محاسبهٔ یک همترازی که دقیقاً این امتیاز را دهد، باید از خانهٔ پایین-راست جدول شروع کنید و مقدار آن را با سه منبع ممکن(تطبیق، درج و حذف) مقایسه کنید تا بفهمید هر یک از کدام منبع به دست آمده‌است. یادداشت‌های تاریخی نیدلمن و وانچ، الگوریتم خود را برای حالتی که تنها از طریق تطابق و عدم تطابق، دارای جریمه هستیم و پرش‌ها هیچ گونه جریمه‌ای را ایجاد نمی‌کنند(d=۰)، به‌طور واضح توصیف کردند. عامل جریمه عددی کاهش یافته‌است که برای هر پرش ساخته شده‌است و می‌تواند به عنوان سدی برای قبول پرش‌ها مورد ارزیابی قرار بگیرد. یک الگوریتم بهتر برای همان مسئله(بدون جریمه پرش) که باز هم از روش برنامه نویسی پویا استفاده کرده‌است و زمان اجرای آن درجه دو است، در سال ۱۹۷۲ توسط دیوید سنکوف ارائه شد. الگوریتم‌های دیگری با همان درجه زمان اجرا، توسط وینتسیوک، در سال ۱۹۶۸ برای پردازش گفتار، و روبرت ونگر و مایکل فایکر، در سال ۱۹۷۴ برای تطابق رشته‌ای ارائه شده‌است. | ## جمع‌بندی | امروزه «نیدلمن-وانج» به یک الگوریتم همترازی سراسری اشاره می‌کند که برای جریمه پرش‌های خطی، زمان اجرایی از درجه دو دارد.