جریمه پرش

از جریمه‌های پرش برای هم‌ترازسازی توالی استفاده می‌شود. جریمه‌های پرش به محاسبهٔ کلی امتیاز تطابق‌ها کمک می‌کنند، و بنابراین، نسبت اندازهٔ جریمهٔ پرش به تعداد درایه‌های ماتریس شباهت (similarity matrix) تطابقی که نهایتاً انتخاب می‌شود را تحت تأثیر قرار می‌دهد.

جریمهٔ پرش ثابت (Constant gap penalty)

جریمهٔ پرش ثابت از ساده‌ترین مدل‌های جریمهٔ پرش است. در این روش زمانی که یک پرش برای اولین بار در توالی به کار گرفته می‌شود فقط یک پارامتر d، به امتیاز تطابق اضافه می‌شود و این بدین معناست که هر پرش یک جریمهٔ یکسان دریافت می‌کند، مستقل از اینکه این پرش دارای چه اندازه ایست.

جریمهٔ پرش خطی (Linear gap penalty)

جریمهٔ پرش خطی فقط یک پارامترِ d دارد که معرف جریمه در واحد طول پرش است. این مقدار در اکثر مواقع مقداری منفی است، بنابراین تطابق با تعداد پرش‌های کمتر بهتر است از تطابق با پرش‌های بیشتر. در روش جریمهٔ پرش خطی، جریمهٔ کلی برای یک پرش بزرگ همانند جریمهٔ کلی برای چندین پرش کوچک است.

جریمهٔ پرش نسبی (Affine gap penalty)

در برخی توالی‌ها بیشتر این احتمال وجود دارد که یک پرش بزرگ داشته باشیم به جای چندین پرش کوچک. برای مثال رخ دادن یک پرش به طول دو محتمل‌تر از حالت دیگر است. این تفاوت در هنگام استفاده از جریمهٔ پرش نسبی، لحاظ می‌شود، ولی در سایر سیاست‌های پرش، هر دو حالت یک امتیاز می‌گیرند. این جریمه به صورت σ + (L - 1). ε مدل می‌شود، که در آن σ، جریمهٔ اولین پرش (gap opening penalty)با هر طولی می‌باشد. ε، جریمهٔ امتداد پرش‌های (gap extension penalty) ایجاد شده به طول ۱ می‌باشد. L هم تعداد کل پرش‌ها می‌باشد. به‌طور مثال، در صورتی که ۵ پرش پشت سر هم رخ دهند، جریمهٔ آن به صورت σ + 4ε مدل می‌شود. معمولاً معیار خاصی برای تعیین کردن مقادیر ε و σ وجود ندارد و این مقادیر با توجه به هدف ما از هم‌ترازسازی توالی‌ها تفاوت می‌کنند. معمولاً هنگامی که به دنبال دنباله‌های نزدیک به هم هستیم، مقدار جریمهٔ ایجاد شکاف (σ)، نسبتاً بزرگتر از زمانی است که دنبال رشته‌های متفاوت از هم می‌باشیم. الگوریتم‌هایی برای هم‌ترازسازی توالی‌ها با استفاده از این جریمه وجود دارند که دو نمونه از آن‌ها که زمان اجرای متفاوتی دارند، در زیر بررسی می‌شوند.

الگوریتم از مرتبهٔ زمانی (O(n³

برای هم‌ترازسازی توالی‌ها، روش‌هایی بر مبنای برنامه‌ریزی پویا معرفی شده‌اند که از معروف‌ترین آن‌ها، الگوریتم نیدلمن-وانچ می‌باشد. برای هم‌تراز سازی توالی‌ها با استفاده از جریمهٔ پرش نسبی، از الگوریتمی مانند الگوریتم نیدلمن-وانچ استفاده می‌کند. بدین صورت که گراف ویرایش (edit graph) را بدین صورت تغییر می‌دهد که یال‌های عمودی و افقی میان رأس‌ها و رأس‌های بعدیشان اضافه می‌کنیم، به طوری که هر یال به طول x، وزن σ + (ε - 1).x داشته باشد. با اضافه‌کردن این یال‌ها، زمان اجرای الگوریتم از (O(n² به (O(n³ افزایش می‌دهد.

تفاوت میان رخ دادن دو پرش و رخ دادن یک پرش به طول دو. رخ دادن یک پرش به طول دو محتمل‌تر از حالت دیگر است.

الگوریتم از مرتبهٔ زمانی (O(n²

برای کاهش زمان اجرای الگوریتم، به جای افزایش تعداد یال‌ها، تعداد رأس‌ها را افزایش می‌دهیم. دنبالهٔ اول را v و دنبالهٔ دوم را w می‌نامیم. با فرض اینکه طول این دنباله‌ها به ترتیب برابر با n و m باشد، برای پیدا کردن هم‌ترازی میان آن‌ها، به یک ماتریس n.m نیاز داریم. در حالتی که بخواهیم جریمهٔ پرش نسبی را هم لحاظ کنیم، به سه ماتریس n.m نیاز داریم. هر کدام از این ماتریس‌ها را مانند یک سطح در نظر می‌گیریم، ماتریس وسطی را با M نشان می‌دهیم، که بیانگر تطابق (Match) یا عدم تطابق میان w و v است. ماتریس بالایی را با U نشان می‌دهیم، که نشان‌گر حذف در w است. ماتریس پایینی هم با L نمایش می‌دهیم که بیانگر حذف در v است؛ بنابراین فرمول زیر با استفاده از مفاهیم برنامه‌ریزی پویا بدست می‌آید:

$U_{i,j}=max{\begin{cases}U_{i,j-1}-\epsilon &{\mbox{ gap extend in w}}\\M_{i,j-1}-\sigma &{\mbox{ gap open to w}}\end{cases}}$

$L_{i,j}=max{\begin{cases}L_{i,j-1}-\epsilon &{\mbox{ gap extend in v}}\\M_{i,j-1}-\sigma &{\mbox{ gap open to v}}\end{cases}}$

$M_{i,j}=max{\begin{cases}U_{i,j}&{\mbox{ end gap from top}}\\L_{i,j}&{\mbox{ end gap from bottom}}\\M_{i-1,j-1}+score(v_{i},w_{j})&{\mbox{ align }}\\\end{cases}}$

تابع score در فرمول بالا، تابعی است که به ازای دو دو عنصر رشته‌های ورودی، میزان شباهت آن‌ها را مشخص می‌کند. به عنوان مثال برای هم‌ترازی توالی‌های پروتئینی، می‌توان از ماتریس بلوسام به عنوان تابع score استفاده کرد. با (O(n² عملیات، هر سه ماتریس پر می‌شود و امتیاز بیشینهٔ هم‌ترازی میان v و w با استفاده از جریمهٔ پرش نسبی، برابر:

$max(U_{n,m},M_{n,m},L_{n,m})$

می‌باشد.

مطالعات بیشتر

• Taylor WR, Munro RE (1997). "Multiple sequence threading: conditional gap placement". Fold Des ۲ (۴): S۳۳–۹.
• Taylor WR (1996). "A non-local gap-penalty for profile alignment". Bull Math Biol ۵۸ (۱): ۱–۱۸. object identifier|doi:10.1007/BF02458279. Identifier|PMID ۸۸۱۹۷۵۱.
• Vingron M، Waterman MS (1994). "Sequence alignment and penalty choice. Review of concepts, case studies and implications". J Mol Biol ۲۳۵ (۱): ۱–۱۲. object doi:10.1016/S۰۰۲۲–۲۸۳۶(۰۵)۸۰۰۰۶–۳. PMID 8289235.
• Panjukov VV (1993). "Finding steady alignments: similarity and distance". Comput Appl Biosci ۹ (۳): ۲۸۵–۹۰. Identifier|PMID ۸۳۲۴۶۲۹.
• Alexandrov NN (1992). "Local multiple alignment by consensus matrix". Comput Appl Biosci ۸ (۴): ۳۳۹–۴۵. PMID ۱۴۹۸۶۸۹.
• Hein J (۱۹۸۹). "A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given". Mol Biol Evol ۶ (۶): ۶۴۹–۶۸. Identifier|PMID ۲۴۸۸۴۷۷.
• Henneke CM (1989). "A multiple sequence alignment algorithm for homologous proteins using secondary structure information and optionally keying alignments to functionally important sites". Comput Appl Biosci ۵ (۲): ۱۴۱–۵۰. Identifier|PMID ۲۷۵۱۷۶۴.
• Reich JG, Drabsch H، Daumler A (۱۹۸۴). "On the statistical assessment of similarities in DNA sequences". Nucleic Acids Res ۱۲ (۱۳): ۵۵۲۹–۴۳. object identifier|doi:10.1093/nar/12.13.5529. PMC 318937. PMID 6462914.