UT-alg-S94-CA2 هم‌ترازی زیررشته‌اي
Time Limit: 30 Seconds Memory Limit: 32768 KB
مسئله‌ی هم‌ترازی رشته‌ها (sequence alignment) را در نظر بگیرید با این تفاوت که یکی از دو رشته (متن یا text) خیلی بزرگ‌تر از رشته‌ی دیگر (پرسمان یا query) است و هدف پیدا کردن زیررشتهای از متن است که بیشترین شباهت را به پرسمان داشته باشد. تعریف دقیق مسئله به این شکل است:
دو رشته‌ی T=t_1, t_2, ..., t_n و Q=q_1, q_2, ..., q_m داده شده. هدف پیدا کردن زیررشتهای از T مثلا T_{i,j}=t_i, ..., t_j است به طوری‌که بیشترین امتیاز هم‌ترازی (alignment score) بین T_i,j و Q بیشینه باشد. این مسئله را هم‌ترازی زیررشتهای می‌نامیم.
یادآوری: یک هم‌ترازی دو رشته با قرار دادن تعدادی فاصله بین حروف هر کدام از رشته‌ها ایجاد می‌شود. هزینه‌ی اضافه کردن هر فاصله s- و هزینه‌ی عدم تطابق دو حرف d- است و پاداش هر تطابق (دو حرف مشابه) برابر ده (۱۰) است.
مثال: اگر T=ACCTTGAATACCTGA باشد و Q=CTTATGTC، در این‌صورت امتیاز هم‌ترازی (alignment) زیر بین T_۳,۱۱ و Q برابر است با:
60-3s-d
C | A | - | T | A | A | G | T | T | C | T_۳,۱۱: |
C | T | G | T | A | - | - | T | T | C | Q: |
توجه کنید که برای حروفی که از ابتدا و انتهای T حذف شده‌اند، جریمه‌ای در نظر گرفته نشده. همچنین بسته به مقدار و ، این هم‌ترازی ممکن است به‌ترین هم‌ترازی باشد یا نباشد.
الف) برای مثال بالا با فرض s =۱۰ وd =۲، آیا زیررشته‌ی دیگری از T وجود دارد که هم‌ترازی به‌تری از مثال بالا داشته باشد؟ اگر وجود دارد یک زیررشته و هم‌ترازی به‌تر ارائه کنید.
ب) الگوریتم هم‌ترازی رشته‌ها که در کلاس دیدیم را طوری تغییر دهید که مسئله‌ی هم‌ترازی زیررشتهای را حل کند. الگوریتم شما باید کماکان در زمان (O(mn و با حافظه‌ی (O(mn اجرا شود. نشان دهید که چگونه هم زیررشته‌ی T_i,j و هم به‌ترین هم‌ترازی بین Q و T_i,j را می‌توانید با این زمان و حافظه محاسبه کنید.
پ) فرض کنید، فقط مقدار جواب، یعنی امتیاز به‌ترین هم‌ترازی زیررشتهای، را باید به‌دست آوریم و خود هم‌ترازی را نیاز نداریم. چطور می‌توان در زمان (O(mn و با حافظه‌ی (O(m این مقدار را حساب کرد؟
ت) الگوریتم قسمت (پ) را با سی، سی‌پلاس‌پلاس، یا جاوا پیاده سازی کنید. توجه کنید با توجه به محدودیت حافظه و حداکثر اندازه‌ی ورودی برای این مسئله، لازم است الگوریتم قسمت (پ) و نه (ب) را پیاده سازی کنید. برنامه‌ی شما باید داده‌های ورودی را از stdin بخواند و پاسخ را در stdout بنویسد. فرض کنید طول متن حداکثر چهارصدهزار (n < ۴۰۰,۰۰۰) و طول پرسمان حداکثر چهارصد حرف است (m < ۴۰۰). برنامه‌ی شما باید در کمتر از ۱۰ ثانیه به ازاء هر تست (بر روی کارگزار Share Code) و با صرف حداکثر یک مگابایت حافظه پاسخ را بیابد. قالب ورودی و خروجی باید به شکل زیر باشد:
ورودی: خط اول، یک عدد صحیح و مثبت k<۲۰ نوشته شده که برابر تعداد مجموعه‌های ورودی است. بعد از آن به ازاء هر مجموعه‌ی ورودی، سه خط نوشته شده. خط اول شامل n، m، ، و است که همگی اعداد صحیح غیر منفی‌اند. سطر بعد حروف متن (بدون فاصله) و سطر بعد از آن حروف پرسمان (بدون فاصله) نوشته شده است. می‌توانید فرض کنید دنباله‌ها، رشته‌های DNA اند، یعنی در آن‌ها فقط از A, T, C, G استفاده شده است، همچنین m n.
خروجی: به ازاء هر زوج متن و پرسمان ورودی، مقدار به‌ترین هم‌ترازی زیررشتهای را در یک خط بنویسید.
Sample Input
2 11 5 1 1 ATGGTTCCTAG ACCGT 11 5 5 1 ATGGTTCCTAG ACCGT
Sample Output
34 28Submit