جریمه پرش

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

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

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

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

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

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

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

الگوریتم از مرتبه‌ی زمانی (O(n3

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

الگوریتم از مرتبه‌ی زمانی (O(n2

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