الگوریتم دوبه‌دو
الگوریتم دوبه‌دو[۱] از روش‌های هم‌ترازسازی توالی در بیوانفورماتیک به‌شمار می‌آید. از کاربردهای آن می‌توان به هم‌ترازسازی یک رشتهٔ پروتئینی با ترجمهٔ پنجره‌های سه‌تایی یک رشتهٔ دی‌ان‌ای اشاره کرد. این الگوریتم از روش برنامه‌ریزی پویا استفاده می‌کند و از آن‌جا که اجازهٔ در نظر گرفتن جهش دگرقالب را در هم‌ترازسازی می‌دهد، نسبت به سایر الگوریتم‌های هم‌ترازسازی توالی بین پروتئین و رشتهٔ دنا انعطاف‌پذیری بیشتری دارد.
مسئله
ویرایشدر مسئلهٔ هم‌ترازسازی رشتهٔ پروتئینی با رشتهٔ دی‌ان‌ای، رشتهٔ دی‌ان‌ای به پنجره‌های سه‌تایی تقسیم می‌شود که هر پنجره به یک پروتئین ترجمه می‌شود. سپس با استفاده از الگوریتم‌های هم‌ترازسازی توالی دو رشتهٔ پروتئینی هم‌ترازسازی می‌شوند. الگوریتم اسمیت واترمن یکی از این الگوریتم‌هاست که بهترین هم‌ترازسازی محلی بین دو رشته را پیدا می‌کند. در فرایند هم‌ترازسازی این الگوریتم، امتیاز تطابق و هزینه‌های آغاز و ادامه پیدا کردن یک فاصله در هم‌ترازسازی لحاظ می‌شوند.
با این حال الگوریتم اسمیت واترمن در مقابل جهش دگرقالب مقاوم نیست. در این جهش تقسیم‌بندی رشتهٔ دی‌ان‌ای به پنجره‌های سه‌تایی دستخوش تغییر می‌شود و در نتیجه ترجمهٔ دی‌ان‌ای به رشتهٔ پروتئینی دچار خطا می‌شود. اما این الگوریتم قابلیت تشخیص این خطای به وجود آمده را ندارد و در نتیجه ممکن است فاصلهٔ بین دو رشته را بیش از حد گزارش کند.
راه حل
ویرایشدر الگوریتم دوبدو علاوه بر امتیازها و هزینه‌های فوق، هزینهٔ بازشدن و ادامه پیدا کردن یک پنجره هم لحاظ شده‌است تا تفاوت‌های به وجود آمدهٔ ناشی از جهش دگرقالب هم قابل پیشبینی باشند. به این شکل که در رشتهٔ دی‌ان‌ای امکان تغییر تقسیم‌بندی رشته به پنجره‌های سه‌تایی با پرداخت یک هزینهٔ متناسب وجود دارد. در نتیجهٔ آن الگوریتم می‌تواند با جا انداختن بخش‌هایی از رشته با پرداخت هزینهٔ متناسب با آن به دنبال هم‌ترازسازی‌های بهتری بگردد. در واقع در الگوریتم‌های پیشین فرض بر نبود اختلال‌هایی مثل جهش دگرقالب بود اما در الگوریتم دوبدو امکان وجود چنین اختلال‌هایی هم لحاظ می‌شود.
مثال
ویرایشدر گام نخست هم‌ترازسازی بدون امکان تغییر پنجره‌ها بین رشتهٔ دی‌ان‌ای و رشتهٔ پروتئینی صورت گرفته‌است و در نتیجهٔ آن سه تطابق پیدا شده‌است.
اما با در نظر گرفتن امکان تغییر پنجره‌ها با پرداخت هزینهٔ آن، هم‌ترازسازی بسیار بهتری پیدا می‌شود که در آن پنج تطابق داریم و الگوریتم توانسته نسبت به جهش دگرقالب مقاوم باشد و هم‌چنان یک هم‌ترازسازی مناسب پیدا کند.
جستارهای وابسته
ویرایشمنابع
ویرایش- ↑ Birney, E.; Thompson, J.; Gibson, T. (1996). "PairWise and SearchWise: Finding the optimal alignment in a simultaneous comparison of a protein profile against all DNA translation frames". Nucleic Acids Research. 24 (14): 2730–2739. doi:10.1093/nar/24.14.2730. PMC 145991. PMID 8759004.