الگوریتم نیدلمن-وانچ
الگوریتم نیدلمن وانچ (به انگلیسی: Needleman–Wunsch algorithm) یک همترازی سراسری بر دو ترتیب متوالی (مانند A و B) انجام میدهد. معمولاً در بیوانفورماتیک برای همترازی توالیهای پروتئینی یا نوکلئوتیدی کاربرد دارد. این الگوریتم در سال ۱۹۷۰ توسط سول نیدلمن و کریستین وانچ ارائه شد.[۱] این الگوریتم نمونهای از برنامهریزی پویا است و اولین کاربرد برنامهریزی پویا در مقایسهٔ توالیهای زیستی است.
یک ارائهٔ جدید[ویرایش]
امتیازها برای کارکترهای همتراز شده توسط ماتریس تطابق مشخص میشود. در اینجا تطابقی برای کارکترهای a و b بهشمار میرود که از یک جریمه پرش خطی، که اینجا d نامیده میشود.
برای نمونه، اگر ماتریس تطابق این باشد:
A | G | C | T | |
---|---|---|---|---|
A | ۱۰ | -۱ | -۳ | -۴ |
G | -۱ | ۷ | -۵ | -۳ |
C | -۳ | -۵ | ۹ | ۰ |
T | -۴ | -۳ | ۰ | ۸ |
همترازی آن:
AGACTAGTTAC CGA‒‒‒GACGT
با جریمه پرش ۵-، امتیاز زیر را خواهد داشت:
برای پیدا کردن همترازی با بیشترین امتیاز، یک آرایهٔ دو بعدی (یا ماتریس) F تخصیص داده شدهاست. درایهٔ سطر iام, ستون jام با نشان داده میشود. یک ستون برای هر کارکتر در توالی A، و یک سطر برای هر کارکتر در توالی B وجود دارد. بنابراین، اگر ما بخواهیم دو توالی با اندازهٔ m و n را همتراز کنیم، مقدار حافظه ی مصرفی برابر است با . (الگوریتم هایزنبرگ میتواند یک همترازی بهینه را با حافظه ، و سرعت اجرا حدوداً دو برابر محاسبه کند.)
در طی پردازش الگوریتم، به عنوان امتیاز بهینه برای همترازی اولین کارکتر در A و اولین کارکتر در B، در نظر گرفته میشود. اصل بهینه سازی به صورت زیر آورده شدهاست.
Basis: Recursion, based on the principle of optimality:
کد زیر برای محاسبه ماتریس 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 محاسبه شد، مقدار درایه ، بیشترین امتیاز در بین همترازیها را به ما میدهد. برای محاسبهٔ یک همترازی که دقیقاً این امتیاز را دهد، باید از خانهٔ پایین-راست جدول شروع کنید و مقدار آن را با سه منبع ممکن(تطبیق، درج و حذف) مقایسه کنید تا بفهمید هر یک از کدام منبع به دست آمدهاست. اگر از طریق تطابق به دست آمده بود، و با هم همترازند. اگر از طریق حذف به دست آمدهاست، با یک پرش همتراز شدهاست و اگر از طریق درج به دست آمده بود نیز با یک پرش همتراز شدهاست.(عموماً برای یک مقدار، بیش از یک انتخاب داریم که همه آنها میتوانند ما را به سمت همترازی بهینه هدایت کنند)
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=۰)، بهطور واضح توصیف کردند. اویلین انتشار عمومی آنها در سال ۱۹۷۰، به راه حلیبازگشتی اشاره داشت.
.
- عامل جریمه عددی کاهش یافتهاست که برای هر پرش ساخته شدهاست و میتواند به عنوان سدی برای قبول پرشها مورد ارزیابی قرار بگیرد. عامل جریمه میتواند تابعی از اندازه و/یا مسیر پرش باشد.
یک الگوریتم بهتر برای همان مسئله(بدون جریمه پرش) که باز هم از روش برنامه نویسی پویا استفاده کردهاست و زمان اجرای آن درجه دو است، در سال ۱۹۷۲ توسط دیوید سنکوف[۲] ارائه شد. الگوریتمهای دیگری با همان درجه زمان اجرا، توسط وینتسیوک[۳]، در سال ۱۹۶۸ برای پردازش گفتار، و روبرت ونگر و مایکل فایکر[۴]، در سال ۱۹۷۴ برای تطابق رشتهای ارائه شدهاست.
وانچ و نیدلمن، الگوریتم خود را به صورت بیشینه شباهت، فرموله کردند. یک امکان دیگر، کمینه کردن تغییرات بین دو توالی است. که ولادمیر لونشتین آن را معرفی کرد. در سال ۱۹۷۴، پیتر سلرز[۵] نشان که این دو الگوریتم در واقع معادل همند.
امروزه «نیدلمن-وانج» به یک الگوریتم همترازی سراسری اشاره میکند که برای جریمه پرشهای خطی، زمان اجرایی از درجه دو دارد.
جستارهای وابسته[ویرایش]
منابع[ویرایش]
- ↑ Needleman, Saul B. ; and Wunsch, Christian D. (۱۹۷۰). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology. ۴۸ (۳): ۴۴۳–۵۳. doi:۱۰.۱۰۱۶/۰۰۲۲-۲۸۳۶(۷۰)۹۰۰۵۷-۴ Check
|doi=
value (کمک). PMID ۵۴۲۰۳۲۵ Check|pmid=
value (کمک). - ↑ Sankoff, D. (۱۹۷۲). "Matching sequences under deletion/insertion constraints". Proceedings of the National Academy of Sciences of the USA. ۶۹ (۱): ۴–۶. doi:10.1073/pnas.69.1.4. PMC 427531. PMID ۴۵۰۰۵۵۵ Check
|pmid=
value (کمک). - ↑ Vintsyuk, T. K. (۱۹۶۸). "Speech discrimination by dynamic programming". Kibernetika. ۴: ۸۱–۸۸.
- ↑ Wagner, R. A. and Fischer, M. J. (۱۹۷۴). "The string-to-string correction problem". Journal of the ACM. ۲۱ (۱): ۱۶۸–۱۷۳. doi:۱۰.۱۱۴۵/۳۲۱۷۹۶.۳۲۱۸۱۱ Check
|doi=
value (کمک). - ↑ Sellers, P. H. (۱۹۷۴). "On the theory and computation of evolutionary distances". SIAM Journal on Applied Mathematics. ۲۶ (۴): ۷۸۷–۷۹۳. doi:۱۰.۱۱۳۷/۰۱۲۶۰۷۰ Check
|doi=
value (کمک).