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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم نیدلمن وانچ (به انگلیسی: Needleman–Wunsch algorithm) یک همترازی سراسری بر دو ترتیب متوالی (مانند 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)

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


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

Basis:
  F_{0j} = d*j
  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 به کار می‌رود:

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}، بیشترین امتیاز در بین همترازی‌ها را به ما می‌دهد. برای محاسبهٔ یک همترازی که دقیقاً این امتیاز را دهد، باید از خانهٔ پایین-راست جدول شروع کنید و مقدار آن را با سه منبع ممکن(تطبیق، درج و حذف) مقایسه کنید تا بفهمید هر یک از کدام منبع به دست آمده‌است. اگر از طریق تطابق به دست آمده بود، A_i و B_j با هم همترازند. اگر از طریق حذف به دست آمده‌است، A_i با یک پرش همتراز شده‌است و اگر از طریق درج به دست آمده بود 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) \}.


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


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

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. Needleman, Saul B. ; and Wunsch, Christian D. (1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology 48 (3): 443–53. doi:10.1016/0022-2836(70)90057-4. PMID 5420325. 
  2. Sankoff, D. (1972). "Matching sequences under deletion/insertion constraints". Proceedings of the National Academy of Sciences of the USA 69 (1): 4–6. doi:10.1073/pnas.69.1.4. PMC 427531. PMID 4500555. 
  3. Vintsyuk, T. K. (1968). "Speech discrimination by dynamic programming". Kibernetika 4: 81–88. 
  4. Wagner, R. A. and Fischer, M. J. (1974). "The string-to-string correction problem". Journal of the ACM 21 (1): 168–173. doi:10.1145/321796.321811. 
  5. Sellers, P. H. (1974). "On the theory and computation of evolutionary distances". SIAM Journal on Applied Mathematics 26 (4): 787–793. doi:10.1137/0126070.