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

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

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

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

	A	G	C	T
A	۱۰	-۱	-۳	-۴
G	-۱	۷	-۵	-۳
C	-۳	-۵	۹	۰
T	-۴	-۳	۰	۸

همترازی آن:

AGACTAGTTAC
CGA‒‒‒GACGT

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

$S(A,C)+S(G,G)+S(A,A)+(3\times d)+S(G,G)+S(T,A)+S(T,C)+S(A,G)+S(C,T)$$S(A,C)+S(G,G)+S(A,A)+(3\times d)+S(G,G)+S(T,A)+S(T,C)+S(A,G)+S(C,T)$

$=-3+7+10-(3\times 5)+7+-4+0+-1+0=1$$=-3+7+10-(3\times 5)+7+-4+0+-1+0=1$

برای پیدا کردن همترازی با بیشترین امتیاز، یک آرایهٔ دو بعدی (یا ماتریس) F تخصیص داده شده‌است. درایهٔ سطر iام, ستون jام با $F_{ij}$$F_{ij}$ نشان داده می‌شود. یک ستون برای هر کارکتر در توالی A، و یک سطر برای هر کارکتر در توالی B وجود دارد. بنابراین، اگر ما بخواهیم دو توالی با اندازهٔ m و n را همتراز کنیم، مقدار حافظه ی مصرفی برابر است با $O(nm)$$O(nm)$. (الگوریتم هایزنبرگ می‌تواند یک همترازی بهینه را با حافظه $\Theta (\min\{n,m\})$$\Theta (\min\{n,m\})$، و سرعت اجرا حدوداً دو برابر محاسبه کند.)
در طی پردازش الگوریتم، $F_{ij}$$F_{ij}$ به عنوان امتیاز بهینه برای همترازی اولین $i=0,...,n$$i=0,...,n$ کارکتر در A و اولین $j=0,...,n$$j=0,...,n$ کارکتر در B، در نظر گرفته می‌شود. اصل بهینه سازی به صورت زیر آورده شده‌است.

Basis:
  $F_{0j}=d*j$$F_{0j}=d*j$
  $F_{i0}=d*i$$F_{i0}=d*i$
  Recursion, based on the principle of optimality:
  $F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)$$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 محاسبه شد، مقدار درایه $F_{nm}$$F_{nm}$، بیشترین امتیاز در بین همترازی‌ها را به ما می‌دهد. برای محاسبهٔ یک همترازی که دقیقاً این امتیاز را دهد، باید از خانهٔ پایین-راست جدول شروع کنید و مقدار آن را با سه منبع ممکن(تطبیق، درج و حذف) مقایسه کنید تا بفهمید هر یک از کدام منبع به دست آمده‌است. اگر از طریق تطابق به دست آمده بود، $A_{i}$$A_i$ و $B_{j}$$B_{j}$ با هم همترازند. اگر از طریق حذف به دست آمده‌است، $A_{i}$$A_i$ با یک پرش همتراز شده‌است و اگر از طریق درج به دست آمده بود $B_{j}$$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
 }

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

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

$F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}$$F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}$.

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

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

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

• بلاست
• فاصله لون‌اشتاین