جریمه پرش کیست؟ توضیح بده.
از جریمه‌های پرش برای هم‌ترازسازی توالی استفاده می‌شود. جریمه‌های پرش به محاسبهٔ کلی امتیاز تطابق‌ها کمک می‌کنند، و بنابراین، نسبت اندازهٔ جریمهٔ پرش به تعداد درایه‌های ماتریس شباهت (similarity matrix) تطابقی که نهایتاً انتخاب می‌شود را تحت تأثیر قرار می‌دهد.جریمهٔ پرش ثابت (Constant gap penalty).جریمهٔ پرش ثابت از ساده‌ترین مدل‌های جریمهٔ پرش است. در این روش زمانی که یک پرش برای اولین بار در توالی به کار گرفته می‌شود فقط یک پارامتر d، به امتیاز تطابق اضافه می‌شود و این بدین معناست که هر پرش یک جریمهٔ یکسان دریافت می‌کند، مستقل از اینکه این پرش دارای چه اندازه ایست.جریمهٔ پرش خطی (Linear gap penalty).جریمهٔ پرش خطی فقط یک پارامترِ d دارد که معرف جریمه در واحد طول پرش است. این مقدار در اکثر مواقع مقداری منفی است، بنابراین تطابق با تعداد پرش‌های کمتر بهتر است از تطابق با پرش‌های بیشتر. در روش جریمهٔ پرش خطی، جریمهٔ کلی برای یک پرش بزرگ همانند جریمهٔ کلی برای چندین پرش کوچک است.جریمهٔ پرش نسبی (Affine gap penalty).در برخی توالی‌ها بیشتر این احتمال وجود دارد که یک پرش بزرگ داشته باشیم به جای چندین پرش کوچک. برای مثال رخ دادن یک پرش به طول دو محتمل‌تر از حالت دیگر است. این تفاوت در هنگام استفاده از جریمهٔ پرش نسبی، لحاظ می‌شود، ولی در سایر سیاست‌های پرش، هر دو حالت یک امتیاز می‌گیرند. این جریمه به صورت σ + (L - 1). ε مدل می‌شود، که در آن σ، جریمهٔ اولین پرش (gap opening penalty)با هر طولی می‌باشد. ε، جریمهٔ امتداد پرش‌های (gap extension penalty) ایجاد شده به طول ۱ می‌باشد. L هم تعداد کل پرش‌ها می‌باشد. به‌طور مثال، در صورتی که ۵ پرش پشت سر هم رخ دهند، جریمهٔ آن به صورت σ + 4ε مدل می‌شود.معمولاً معیار خاصی برای تعیین کردن مقادیر ε و σ وجود ندارد و این مقادیر با توجه به هدف ما از هم‌ترازسازی توالی‌ها تفاوت می‌کنند. معمولاً هنگامی که به دنبال دنباله‌های نزدیک به هم هستیم، مقدار جریمهٔ ایجاد شکاف (σ)، نسبتاً بزرگتر از زمانی است که دنبال رشته‌های متفاوت از هم می‌باشیم.الگوریتم‌هایی برای هم‌ترازسازی توالی‌ها با استفاده از این جریمه وجود دارند که دو نمونه از آن‌ها که زمان اجرای متفاوتی دارند، در زیر بررسی می‌شوند.الگوریتم از مرتبهٔ زمانی (O(n3.برای هم‌ترازسازی توالی‌ها، روش‌هایی بر مبنای برنامه‌ریزی پویا معرفی شده‌اند که از معروف‌ترین آن‌ها، الگوریتم نیدلمن-وانچ می‌باشد. برای هم‌تراز سازی توالی‌ها با استفاده از جریمهٔ پرش نسبی، از الگوریتمی مانند الگوریتم نیدلمن-وانچ استفاده می‌کند. بدین صورت که گراف ویرایش (edit graph) را بدین صورت تغییر می‌دهد که یال‌های عمودی و افقی میان رأس‌ها و رأس‌های بعدیشان اضافه می‌کنیم، به طوری که هر یال به طول x، وزن σ + (ε - 1).x داشته باشد. با اضافه‌کردن این یال‌ها، زمان اجرای الگوریتم از (O(n2 به (O(n3 افزایش می‌دهد.الگوریتم از مرتبهٔ زمانی (O(n2.برای کاهش زمان اجرای الگوریتم، به جای افزایش تعداد یال‌ها، تعداد رأس‌ها را افزایش می‌دهیم. دنبالهٔ اول را v و دنبالهٔ دوم را w می‌نامیم. با فرض اینکه طول این دنباله‌ها به ترتیب برابر با n و m باشد، برای پیدا کردن هم‌ترازی میان آن‌ها، به یک ماتریس n.m نیاز داریم. در حالتی که بخواهیم جریمهٔ پرش نسبی را هم لحاظ کنیم، به سه ماتریس n.m نیاز داریم. هر کدام از این ماتریس‌ها را مانند یک سطح در نظر می‌گیریم، ماتریس وسطی را با M نشان می‌دهیم، که بیانگر تطابق (Match) یا عدم تطابق میان w و v است. ماتریس بالایی را با U نشان می‌دهیم، که نشان‌گر حذف در w است. ماتریس پایینی هم با L نمایش می‌دهیم که بیانگر حذف در v است؛ بنابراین فرمول زیر با استفاده از مفاهیم برنامه‌ریزی پویا بدست می‌آید:formula_1formula_2formula_3تابع score در فرمول بالا، تابعی است که به ازای دو دو عنصر رشته‌های ورودی، میزان شباهت آن‌ها را مشخص می‌کند. به عنوان مثال برای هم‌ترازی توالی‌های پروتئینی، می‌توان از ماتریس بلوسام به عنوان تابع score استفاده کرد.با (O(n2 عملیات، هر سه ماتریس پر می‌شود و امتیاز بیشینهٔ هم‌ترازی میان v و w با استفاده از جریمهٔ پرش نسبی، برابر:formula_4می‌باشد.