الگوریتم اسمیت واترمن

الگوریتم اسمیت واترمن (به انگلیسی: Smith–Waterman algorithm)‏ برای انجام دادن یک هم‌ترازسازی توالی محلی به کار گرفته می‌شود و برای مشخص کردن مناطق مشابه بین دو توالی اسید نوکلئیک یا پروتین استفاده می‌شود. به جای در نظر گرفتن تمام توالی این الگوریتم سعی می‌کند که با در نظر گرفتن بخشهای مختلف با همهٔ طولهای ممکن میزان شباهت را بهینه کند.

پیشینه

این الگوریتم برای اولین با توسط Temple F. Smith و Michael S. Waterman در سال ۱۹۸۱ ارائه شد. که مانندالگوریتم نیدلمن-وانچ با یک سری تفاوت‌ها یک الگوریتم برنامه‌ریزی پویا می‌باشد. این الگوریتم دارای این خصوصیت است که بر حسب سیستم امتیاز دهی (شامل ماتریس جایگزنی و جریمه پرش) که استفاده می‌شود تضمین می‌کند که به جواب بهینه برسد. تفاوتی که با الگوریتم نیدلمن-وانچ دارد این است که در ماتریس جایگذاری آن مقادیر منفی با صفر جابگزین می‌شوند. عمل برگشت به عقب در این الگوریتم از خانه ایی که مقدار بیشنه را دارد شروع شده و به خانه ایی که مقدار صفر دارد ختم می‌شود. که این مسیر بیشترن امتیاز همترازسازی محلی را دارد.

شرح الگوریتم

مانند همه برنامه ریزی‌های پویا یک ماتریس را باید پر کنیم. ماترییس $H$ به اینصورت ساخته می‌شود.

$H(i,0) = 0,\; 0\le i\le m$

$H(0,j) = 0,\; 0\le j\le n$

$\text{ if} a_i = b_j$ $w(a_i, b_j) = w\text{(Match)}$ $\text{ or if} a_i!= b_j$ $w(a_i, b_j) = w\text{(Mismatch)}$

$H(i,j) = \max \begin{Bmatrix} 0 \\ H(i-1,j-1) + \ w(a_i,b_j) & \text{Match/Mismatch} \\ H(i-1,j) + \ w(a_i,-) & \text{Deletion} \\ H(i,j-1) + \ w(-,b_j) & \text{Insertion} \end{Bmatrix} ,\; 1\le i\le m, 1\le j\le n$

که:

• $a, b$ = رشته‌هایی روی الفبا $\Sigma$
• $m = \text{length}(a)$
• $n = \text{length}(b)$
• $H(i,j)$ - مقدار بیشینه امتیاز شباهت یک پسوند [a[1...i و یک پسوند [b[1...j
• $w(c,d),\; c, d\in\Sigma\cup\{'-'\}$, که '-' نمایش جریمه پرش است

مثال

• رشته 1 = ACACACTA
• رشته 2 = AGCACACA
• w(پرش) = -۱
• w(تطابق) = +۲
• $w(a,-) = w(-,b) = w(mismatch) = -1$

$H = \begin{pmatrix} &-&A&C&A&C&A&C&T&A \\ -&0&0&0&0&0&0&0&0&0 \\ A&0&2&1&2&1&2&1&0&2 \\ G&0&1&1&1&1&1&1&0&1 \\ C&0&0&3&2&3&2&3&2&1 \\ A&0&2&2&5&4&5&4&3&4 \\ C&0&1&4&4&7&6&7&6&5 \\ A&0&2&3&6&6&9&8&7&8 \\ C&0&1&4&5&8&8&11&10&9 \\ A&0&2&3&6&7&10&10&10&12 \\ \end{pmatrix}$

برای به دست آوردن بهترین همترازی محلی، از خانه ایی از ماتریس با بیشترین ارزش شروع می‌کنیم (خانه (i,j)) و به عقب بر می‌گردیم و به یکی از خانه‌های (i-1,j), (i,j-1) و (i-1,j-1) می‌رویم با توجه به مسیری که ماتریس ساخته شده‌است. این رویه را آنقدر تکرار می‌کنیم که یا به خانه ایی با مقدار صفر برسیم و یا در خانه (۰٬۰) باشیم. برای مثال خانه با بیشترین مقدار در جایگاه (۸،۸) است و با توجه به ماتریس مسیر (۸٬۸), (۷٬۷), (۷٬۶), (۶٬۵), (۵٬۴), (۴٬۳), (۳٬۲), (۲٬۱), (۱٬۱) و (۰٬۰) را به عقب بر می‌گردیم.

وقتی عمل برگشت تمام شد به این ترتیب همتراز سازی را نتیجه می‌گیریم:

• حرکت روی قطر نشاندهنده یک همتراز سازی است (تطابق یا عدم تطابق)
• یک حرکت بالا به پایین نشانده یک حذف است
• یک حرکت چپ به راست نشان دهنده یک درج است.

برای مثال خواهیم داشت:

رشته 1 = A-CACACTA
رشته 2 = AGCACAC-A

منابع

http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm