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

رده	هم‌ترازسازی توالی
کارایی بدترین حالت	${\displaystyle O(mn)}$
پیچیدگی فضایی	${\displaystyle O(mn)}$

الگوریتم نیدلمن وانچ (به انگلیسی: Needleman–Wunsch algorithm) یک همترازی سراسری بر دو ترتیب متوالی (مانند A و B) انجام می‌دهد. معمولاً در بیوانفورماتیک برای همترازی توالی‌های پروتئینی یا نوکلئوتیدی کاربرد دارد. این الگوریتم در سال ۱۹۷۰ توسط سول نیدلمن و کریستین وانچ ارائه شد.

این الگوریتم نمونه‌ای از برنامه‌ریزی پویا است و اولین کاربرد برنامه‌ریزی پویا در مقایسهٔ توالی‌های زیستی است.

شکل 1:هم تراز سازی دو رشته به وسیله الگوریتم نیدلمن وانچ

مقدمه

این الگوریتم را می توان برای هرجفت رشته ای به کار برد. در راهنمای زیر از دو توالی دی ان ای کوتاه به عنوان مثال استفاده می شود:

 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

سیستم های امتیاز دهی

سیستم پایه

ساده ترین سیستم امتیاز دهی به هر یک از سه حالت تطابق، عدم تطابق و درج-حذف یک مقدار نسبت می دهد. به عنوان مثال ممکن است امتیاز تطابق برابر 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- را در نظر گرفت. مثلا هم ترازی زیر

 CTTTTTTG
 C-T-T--G

که پیش ازاین دارای چندین هم ترازی معادل بود، اکنون به شکل زیر هم تراز می شود:

 CTTTTTTG
 CTT----G

زیرا فاصله به طول 4 بر چندین فاصله با طول کمتر ارجحیت دارد.

یک ارائهٔ جدید

امتیازها برای کارکترهای همتراز شده توسط ماتریس تطابق مشخص می‌شود. در اینجا ${\displaystyle S(a,b)}$ تطابقی برای کارکترهای a و b به‌شمار می‌رود که از یک جریمه پرش خطی، که اینجا d نامیده می‌شود.
برای نمونه، اگر ماتریس تطابق این باشد:

همترازی آن:

AGACTAGTTAC
CGA‒‒‒GACGT

با جریمه پرش ۵-، امتیاز زیر را خواهد داشت:

در طی پردازش الگوریتم، ${\displaystyle F_{ij}}$ به عنوان امتیاز بهینه برای همترازی اولین ${\displaystyle i=0,...,n}$ کارکتر در A و اولین ${\displaystyle j=0,...,n}$ کارکتر در B، در نظر گرفته می‌شود. اصل بهینه سازی به صورت زیر آورده شده‌است.

Basis:
  ${\displaystyle F_{0j}=d*j}$
  ${\displaystyle F_{i0}=d*i}$
  Recursion, based on the principle of optimality:
  ${\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)}$

کد زیر برای محاسبه ماتریس F به کار می‌رود:

for i=0 to length(A)
    F(i,0) ← d*i
  for j=0 to length(B)
    F(0,j) ← d*j
  for i=1 to length(A)
    for j=1 to length(B)
    {
      Match ← F(i-1,j-1) + S(Ai, Bj)
      Delete ← F(i-1, j) + d
      Insert ← F(i, j-1) + d
      F(i,j) ← max(Match, Insert, Delete)
   }

زمانی که ماتریس F محاسبه شد، مقدار درایه ${\displaystyle F_{nm}}$، بیشترین امتیاز در بین همترازی‌ها را به ما می‌دهد. برای محاسبهٔ یک همترازی که دقیقاً این امتیاز را دهد، باید از خانهٔ پایین-راست جدول شروع کنید و مقدار آن را با سه منبع ممکن(تطبیق، درج و حذف) مقایسه کنید تا بفهمید هر یک از کدام منبع به دست آمده‌است. اگر از طریق تطابق به دست آمده بود، ${\displaystyle A_{i}}$ و ${\displaystyle B_{j}}$ با هم همترازند. اگر از طریق حذف به دست آمده‌است، ${\displaystyle A_{i}}$ با یک پرش همتراز شده‌است و اگر از طریق درج به دست آمده بود ${\displaystyle B_{j}}$ نیز با یک پرش همتراز شده‌است.(عموماً برای یک مقدار، بیش از یک انتخاب داریم که همه آن‌ها می‌توانند ما را به سمت همترازی بهینه هدایت کنند)

  AlignmentA ← ""
  AlignmentB ← ""
  i ← length(A)
  j ← length(B)
  while (i> 0 and j> ۰)
  {
    Score ← F(i,j)
    ScoreDiag ← F(i - 1, j - 1)
    ScoreUp ← F(i, j - 1)
    ScoreLeft ← F(i - 1, j)
    if (Score == ScoreDiag + S(Ai, Bj))
    {
      AlignmentA ← Ai + AlignmentA
      AlignmentB ← Bj + AlignmentB
      i ← i - 1
      j ← j - 1
   }
    else if (Score == ScoreLeft + d)
    {
      AlignmentA ← Ai + AlignmentA
      AlignmentB ← «-» + AlignmentB
      i ← i - 1
   }
    otherwise (Score == ScoreUp + d)
    {
      AlignmentA ← «-» + AlignmentA
      AlignmentB ← Bj + AlignmentB
      j ← j - 1
   }
 }
  while (i> ۰)
  {
    AlignmentA ← Ai + AlignmentA
    AlignmentB ← «-» + AlignmentB
    i ← i - 1
 }
  while (j> ۰)
  {
    AlignmentA ← «-» + AlignmentA
    AlignmentB ← Bj + AlignmentB
    j ← j - 1
 }

پیچیدگی

محاسبه امتیاز هر خانه از جدول دارای پیچیدگی ${\displaystyle O(1)}$ است. در نتیجه پیچیدگی زمانی الگوریتم برای دو توالی به طول ${\displaystyle m}$ و ${\displaystyle n}$ ، ${\displaystyle O(mn)}$ است. ثابت شده است که با استفاده از Method of Four russians می توان زمان اجرا را به ${\displaystyle O(mn/\log n)}$ بهبود بخشید.

با توجه به اینکه الگوریتم جدولی ${\displaystyle m\times n}$ را پر می کند، پیچیدگی حافظه آن ${\displaystyle O(mn)}$ می باشد.

یادداشت‌های تاریخی

نیدلمن و وانچ، الگوریتم خود را برای حالتی که تنها از طریق تطابق و عدم تطابق، دارای جریمه هستیم و پرش‌ها هیچ گونه جریمه‌ای را ایجاد نمی‌کنند(d=۰)، به‌طور واضح توصیف کردند. اویلین انتشار عمومی آن‌ها در سال ۱۹۷۰، به راه حلی بازگشتی اشاره داشت.

عامل جریمه عددی کاهش یافته‌است که برای هر پرش ساخته شده‌است و می‌تواند به عنوان سدی برای قبول پرش‌ها مورد ارزیابی قرار بگیرد. عامل جریمه می‌تواند تابعی از اندازه و/یا مسیر پرش باشد.

یک الگوریتم بهتر برای همان مسئله(بدون جریمه پرش) که باز هم از روش برنامه نویسی پویا استفاده کرده‌است و زمان اجرای آن درجه دو است، در سال ۱۹۷۲ توسط دیوید سنکوف ارائه شد. الگوریتم‌های دیگری با همان درجه زمان اجرا، توسط وینتسیوک، در سال ۱۹۶۸ برای پردازش گفتار، و روبرت ونگر و مایکل فایکر، در سال ۱۹۷۴ برای تطابق رشته‌ای ارائه شده‌است.
وانچ و نیدلمن، الگوریتم خود را به صورت بیشینه شباهت، فرموله کردند. یک امکان دیگر، کمینه کردن تغییرات بین دو توالی است. که ولادمیر لونشتین آن را معرفی کرد. در سال ۱۹۷۴، پیتر سلرز نشان که این دو الگوریتم در واقع معادل همند.
امروزه «نیدلمن-وانج» به یک الگوریتم همترازی سراسری اشاره می‌کند که برای جریمه پرش‌های خطی، زمان اجرایی از درجه دو دارد.

جستارهای وابسته

• فاصله لون‌اشتاین
• هم‌ترازسازی توالی
• الگوریتم اسمیت واترمن
• برنامه‌نویسی پویا