الگوریتم نیدلمن-وانچ
الگوریتم نیدلمن وانچ یک همترازی سراسری بر دو ترتیب متوالی (مانند A و B) انجام می‌دهد. معمولاً در بیوانفورماتیک برای همترازی توالی‌های پروتئینی یا نوکلئوتیدی کاربرد دارد. این الگوریتم در سال ۱۹۷۰ توسط سول نیدلمن و کریستین وانچ ارائه شد.
این الگوریتم نمونه‌ای از برنامه‌ریزی پویا است و اولین کاربرد برنامه‌ریزی پویا در مقایسهٔ توالی‌های زیستی است.
این الگوریتم را می توان برای هرجفت رشته ای به کار برد. در راهنمای زیر از دو توالی دی ان ای کوتاه به عنوان مثال استفاده می شود:
ابتدا جدولی مانند زیر بسازید:
در سطر اول، جدول رشته اول قرار می گیرد و محل شروع این رشته ستون سوم است. هم چنین رشته دوم در ستون اول قرار گرفته و محل شروع آن از سطر سوم است.
در ابتدا هیچ عددی در جدول وجود ندارد.
هنگام هم تراز سازی دو رشته، ممکن است سه حالت برای حروف رخ دهد:
به هر یک از این حالات یک امتیاز اختصاص داده می شود و امتیاز یک هم تراز سازی از جمع امتیاز های هر جفت از حروف متناظر به دست می آید.
سیستم های متفاوتی برای امتیاز دهی وجود دارند که تعدادی از آن ها در بخش سیستم های امتیاز دهی ذکر شده اند.
سیستم استفاده شده در اینجا، همان سیستم الگوریتم نیدلمن-وانچ است که در آن امتیاز تطابق 1+ و امتیاز عدم تطابق، درج یا حذف 1- می باشد. به طور مثال امتیاز هم ترازی زیر برابر 2- است زیرا:
از ستون دوم سطر دوم شروع کنید و در آن مقدار 0 را قرار دهید. سپس سطر به سطر پیش روید و امتیاز هر خانه را محاسبه کنید. این امتیاز از اضافه کردن امتیاز خانه مجاور سمت چپ، بالا یا بالا چپ (به صورت قطری) به امتیاز مناسب برای تطابق، عدم تطابق یا درج-حذف به دست می آید.
در واقع برای محاسبه امتیاز 3 گزینه وجود دارد: در نهایت امتیاز نهایی این خانه با بیشترین امتیاز در میان سه امتیاز به دست آمده برابر است.
با توجه به اینکه خانه های سطر دوم دارای خانه بالا یا بالا-چپ نیستند، پس تنها خانه سمت چپ می تواند برای محاسبه امتیاز استفاده شود. به این ترتیب سطر دوم به ترتیب از چپ دارای امتیاز های 0، 1-، 2-، 3-،...،7- می شود.
استدلالی مشابه برای ستون دوم نیز به کار می رود که در نتیجه آن جدولی به شکل زیر حاصل می شود.
حال برای محاسبه امتیاز خانه سطر سوم و ستون سوم، 3 حالت وجود دارد:در نهایت بیشترین امتیاز در میان این 3 یعنی عدد 1 وارد این خانه می شود. هم چنین باید پیکان مربوط را ذخیره کرد که یک پیکان قطری از خانه(3,3) به خانه (2,2) است.
به همین ترتیب تمامی خانه های جدول پر می شوند تا امتیاز نهایی بهترین هم ترازی به دست آید. کامل شده این جدول در شکل 1 آمده است و طبق آن امتیاز بهترین هم ترازی این دو رشته برابر با 0 است.
به وسیله تعدادی پیکان مسیری را از گوشه پایین-راست جدول به گوشه بالا-چپ جدول نشان دار کنید. سپس از طریق این مسیر و طبق قوانین زیر توالی متناظر مسیر را بسازید:پیکان افقی یک جای خالی("-") را با حرف ستون متناظر مبدا پیکان و پیکان عمودی حرف سطر متناظر مبدا پیکان را با یک جای خالی تراز می کند.با توجه به قواعد بالا و طبق شکل 1، یکی از بهترین هم ترازی ها برای دو رشته ذکر شده در زیر آمده است:
ساده ترین سیستم امتیاز دهی به هر یک از سه حالت تطابق، عدم تطابق و درج-حذف یک مقدار نسبت می دهد. به عنوان مثال ممکن است امتیاز تطابق برابر 1 و امتیاز عدم تطابق یا درج-حذف 1- در نظر گرفته شود. که در این حالت بیشترین امتیاز مربوط به کمترین فاصله ویرایش است.
به عنوان مثالی دیگر ممکن است به تطابق امتیاز 0 و به عدم تطابق و درج-حذف امتیاز 1- نسبت داده شود. که در این حالت امتیاز یک هم ترازی در واقع فاصله ویرایش میان دو رشته است.
سیستم های امتیاز دهی متفاوت برای شرایط مختلف طراحی شده اند. به عنوان مثال اگر وجود فاصله را اتفاق بدی در هم ترازی در نظر بگیریم، میتوانیم از امتیاز بندی مانند مثال زیر استفاده کنیم:
امتیاز تطابق =1+
امتیاز عدم تطابق=1-
امتیاز فاصله=7-
سیستم های امتیاز دهی پیچیده تر، نه تنها برای نوع جایگزینی بلکه برای حروف مختلف نیز امتیاز های متفاوتی در نظر میگیرند. به عنوان مثال، ممکن است به تطابق بین 2 حرف A امتیاز 1 و به تطابق بین 2 حرف G امتیاز 3 داده شود. که این به معناست که تطابق G ها از اهمیت بیشتری برای هم تراز سازی برخوردار است. از این روش امتیاز دهی برای عدم تطابق نیز می توان بهره گرفت. به عنوان مثال ممکن است به دو حرف A,G امتیاز 1- و به دو حرف T,G امتیاز 2- اختصاص داده شود.
برای نمایش همه حالات ممکن امتیاز دهی از ماتریس مشابهت استفاده می شود.
ماتریس زیر نمونه ای از ماتریس های مشابهت برای مثال بالاست:
به عنوان مثال، ماتریس زیر، ماتریس مشابهت امتیاز گذاری مورد استفاده در شکل 1 است:
با توجه به اینکه امتیاز عدم تطابق دو حرف مثلا A و T با امتیاز عدم تطابق T و A برابر است، ماتریس مشابهت ماتریسی متقارن است.
ماتریس های امتیاز دهی مختلف برای دادن وزن های متفاوت و مناسب شرایط به حالات مختلفی که ممکن است رخ دهند، ساخته می شوند. این ماتریس های وزن دار به ویژه در هم تراز سازی توالی های پروتئینی کاربرد دارند زیرا فراوانی آمینو اسید های مختلف با یکدیگر متفاوت است.
بلوسام(BLOSUM) و PAM دو نمونه پر کاربرد از این ماتریس های وزن دار هستند.
هنگام هم ترازی توالی ها معمولا درج-حذف به وجود می آید که گاهی تعداد زیادی از آن ها پشت سر هم قرار میگیرند. از نظر زیستی، یک فاصله بزرگ با احتمال بیشتری از یک حذف بزرگ ناشی می شود تا از چندین حذف کوچک. در نتیجه امتیاز 2 درج-حذف کوچک باید بدتر از یک درج-حذف بزرگ باشد. راه ساده و معمول این امتیاز دهی این است که برای شروع یک فاصله که در واقع یک درج-حذف جدید است یک جریمه بالا و برای گسترش فاصله که در واقع گسترش درج-حذف هاست جریمه پایین تری در نظر بگیریم.
برای مثال، برای درج-حذف جدید می توان امتیاز 6- و برای گسترش آن امتیاز 1- را در نظر گرفت. مثلا هم ترازی زیر
که پیش ازاین دارای چندین هم ترازی معادل بود، اکنون به شکل زیر هم تراز می شود:
زیرا فاصله به طول 4 بر چندین فاصله با طول کمتر ارجحیت دارد.
امتیازها برای کارکترهای همتراز شده توسط ماتریس تطابق مشخص می‌شود. در اینجا formula_1 تطابقی برای کارکترهای a و b به‌شمار می‌رود که از یک جریمه پرش خطی، که اینجا d نامیده می‌شود. برای نمونه، اگر ماتریس تطابق این باشد:
همترازی آن:
با جریمه پرش ۵-، امتیاز زیر را خواهد داشت:
formula_2
formula_3
در طی پردازش الگوریتم، formula_4 به عنوان امتیاز بهینه برای همترازی اولین formula_5 کارکتر در A و اولین formula_6 کارکتر در B، در نظر گرفته می‌شود. اصل بهینه سازی به صورت زیر آورده شده‌است. کد زیر برای محاسبه ماتریس F به کار می‌رود:
زمانی که ماتریس F محاسبه شد، مقدار درایه formula_10، بیشترین امتیاز در بین همترازی‌ها را به ما می‌دهد. برای محاسبهٔ یک همترازی که دقیقاً این امتیاز را دهد، باید از خانهٔ پایین-راست جدول شروع کنید و مقدار آن را با سه منبع ممکن(تطبیق، درج و حذف) مقایسه کنید تا بفهمید هر یک از کدام منبع به دست آمده‌است. اگر از طریق تطابق به دست آمده بود، formula_11 و formula_12 با هم همترازند. اگر از طریق حذف به دست آمده‌است، formula_11 با یک پرش همتراز شده‌است و اگر از طریق درج به دست آمده بود formula_12 نیز با یک پرش همتراز شده‌است.(عموماً برای یک مقدار، بیش از یک انتخاب داریم که همه آن‌ها می‌توانند ما را به سمت همترازی بهینه هدایت کنند)
محاسبه امتیاز هر خانه از جدول دارای پیچیدگی formula_15 است. در نتیجه پیچیدگی زمانی الگوریتم برای دو توالی به طول formula_16 و formula_17 ، formula_18 است. ثابت شده است که با استفاده از می توان زمان اجرا را به formula_19 بهبود بخشید.
با توجه به اینکه الگوریتم جدولی formula_20 را پر می کند، پیچیدگی حافظه آن formula_18 می باشد. نیدلمن و وانچ، الگوریتم خود را برای حالتی که تنها از طریق تطابق و عدم تطابق، دارای جریمه هستیم و پرش‌ها هیچ گونه جریمه‌ای را ایجاد نمی‌کنند("d"=۰)، به‌طور واضح توصیف کردند. اویلین انتشار عمومی آن‌ها در سال ۱۹۷۰، به راه حلی بازگشتی اشاره داشت.
F_{ij} = \max_{h. یک الگوریتم بهتر برای همان مسئله(بدون جریمه پرش) که باز هم از روش برنامه نویسی پویا استفاده کرده‌است و زمان اجرای آن درجه دو است، در سال ۱۹۷۲ توسط دیوید سنکوف ارائه شد. الگوریتم‌های دیگری با همان درجه زمان اجرا، توسط وینتسیوک، در سال ۱۹۶۸ برای پردازش گفتار، و روبرت ونگر و مایکل فایکر، در سال ۱۹۷۴ برای تطابق رشته‌ای ارائه شده‌است. وانچ و نیدلمن، الگوریتم خود را به صورت بیشینه شباهت، فرموله کردند. یک امکان دیگر، کمینه کردن تغییرات بین دو توالی است. که ولادمیر لونشتین آن را معرفی کرد. در سال ۱۹۷۴، پیتر سلرز نشان که این دو الگوریتم در واقع معادل همند. امروزه «نیدلمن-وانج» به یک الگوریتم همترازی سراسری اشاره می‌کند که برای جریمه پرش‌های خطی، زمان اجرایی از درجه دو دارد.