پاورپوینت یافتن طولانیترین زیر رشته مشترک با رویکرد تقسیم و حل

بخشی از پاورپوینت

اسلاید 2 :

اهداف درس این جلسه
یافتن طولانیترین زیر رشته مشترک با رویکرد تقسیم و حل

اسلاید 3 :

و) طولانیترین زیررشته مشترک (Longest Common Substring)
در کاربردهای زیستشناسی اغلب میخواهیم DNA دو یا چند موجود زنده را با هم مقایسه کنیم.
یک رشته DNA شامل رشتهای از مولکولها است که به آنها پایه (base) میگویند.

DNA مربوط به یک موجود زنده:
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
DNA مربوط به به یک موجود زنده دیگر:
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA

اسلاید 4 :

و) طولانیترین زیررشته مشترک
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA
به دلایل متعددی زیستشناسان میخواهند تا دو رشته DNA را با هم مقایسه کنند.
مثلا نیاز است تا بررسی کنند که دو رشته که مربوط به دو اورگانیسم است چقدر به هم شبیه هستند.
در هر علمی، شباهت را به روشهای مختلفی میتوان تعریف کرد.
مثلا میتوانیم بگوییم که دو رشته DNA به هم شبیه هستند چنانچه یکی دقیقا زیر رشته دیگری باشد.
پس در مثال بالا، S1 و S2 هیچکدام زیر رشته دیگری نیستند.
یا میتوانیم شباهت را اینگونه تعریف کنیم که .
دو رشته به هم شبیه هستند چنانچه تعداد تغییراتی که نیاز است در یکی صورت پذیرد تا به دیگری تبدیل شود، اندک باشد.

اسلاید 5 :

و) طولانیترین زیررشته مشترک
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA
راه دیگری برای بیان شباهت بین دو رشته S1 و S2 آن است تا .
زیر رشته سومی مانند S3 بیابیم که پایههایی که در آن هستند، در S1 و S2 نیز باشد.
این پایهها نیاز است تا با همان ترتیبی که در S3 هستند در S1 و S2 نیز باشند و نیازی نیست که .
دقیقا متوالی باشند.
هر چه این زیر رشته مشترک (S3)، طولانیتر باشد، آنگاه دو رشته S1 و S2 بیشتر به هم شبیه هستند.
برای مثال بالا، طولانیترین زیر رشته مشترک (S3) به صورت زیر میباشد:
GTCGTCGGAAGCCGGCCGAA.

اسلاید 6 :

و) طولانیترین زیررشته مشترک
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA
S3=GTCGTCGGAAGCCGGCCGAA

این مساله با عنوان طولانیترین زیر رشته مشترک .
(Longest Common Subsequence (LCS)) تعریف میشود که .
در ادامه این جلسه میخواهیم راه حلی برای آن با رویکرد برنامهنویسی پویا بیابیم.

اسلاید 7 :

و) طولانیترین زیررشته مشترک
فرض کنید رشته X= داده شده است.
رشته دیگری مانند Z= گفته میشود که .
زیر رشته X است چنانچه .
حداقل یک دنبالهای از اندیسهای X به صورت صعودی () وجود داشته باشد چنانچه برای j=1,2,…,k داشته باشیم xij =zj
به عنوان مثال Z= زیررشتهای از X= است چرا که .
دنبالهای از اندیسها (؟) به صورت صعودی وجود دارد که xij =zj
<2,3,5,7>

اسلاید 8 :

و) طولانیترین زیررشته مشترک
دو رشته X و Y داده شده است. گفته میشود که رشته Z، زیر رشته مشترک X و Y است چنانچه .
Z زیر رشته مشترک هر دوی X و Y باشد.
به عنوان مثال اگر X= و Y= باشند .
رشته زیر رشته مشترک هر دوی X و Y هست.
بزرگترین زیر رشته مشترک نیست چرا که .
طول آن 3 است و رشته .
با طول 4، نیز زیر رشته مشترک این دو رشته میباشد.

اسلاید 9 :

و) طولانیترین زیررشته مشترک
در مساله طولانیترین زیر رشته مشترک، دو رشته .
X= و Y= داده شده که میخواهیم .
زیر رشته مشترکی بین X و Y با طولانیترین طول پیدا کنیم.

اسلاید 10 :

و) طولانیترین زیررشته مشترک
چنانچه بخواهیم با رویکرد brute-force پاسخ را بیابیم .
باید تمامی زیر رشتههای X را ایجاد کنیم و برای هرکدام چک کنیم که آیا زیر رشته Y نیز میباشد یا خیر.
از آنجایی که هر زیر رشته X معادل است با زیر مجموعهای از اندیسهای .
{1,2,…,m} از X که اعضایش مرتب شدهاند .
بنابراین نیاز است تا در فرآیندی تمامی این زیرمجموعهها ایجاد شوند .
که دارای پیچیدگی محاسباتی 2m خواهد بود که برای m های بزرگ این روش قابلیت استفاده ندارد.

اسلاید 11 :

و) طولانیترین زیررشته مشترک
آیا اصل بهینگی در LCS برقرار است؟
قضیه: اگر X= و Y= دو رشته باشند و Z= زیر رشتهای مشترک با طولانیترین طول (LCS) باشد .

اسلاید 12 :

و) طولانیترین زیررشته مشترک
با توجه به این قضیه، این اصل بهینگی در این مساله وجود دارد یعنی
چناچه Zk ای پاسخ مساله Xm و Yn باشد در این صورت باتوجه به شرایط تعریف شده در قضیه، زیر راهحلهای آن (Zk یا Zk-1) پاسخی برای زیر مسائل (مثلا Xm-1 و Yn-1 میباشد)

اسلاید 13 :

فرض کنید c[i,j] را طول LCS بین دنبالههای Xi و Yj درنظر بگیریم.
اگر i=0 یا j=0 آنگاه طول LCS برابر صفر خواهد بود.
میتوان ویژگی بازگشتی زیر را باتوجه به قشیه بالا برای این مساله به صورت زیر تعریف کرد:

اسلاید 14 :

function [lcsValue,B]=LCS-LENGTH(X,Y)
m=length(X);n=length(Y);
%It is assumed that index 0 is accepted in Matlab
C=zeros(m,n);B=zeros(m,n);
for i=1:m
C(i,0)=0;
end
for j=1:n
C(0,j)=0;
end
for i=1:m
for j=1:n
if X(i)==Y(i)
C(i,j)=C(i-1,j-1)+1;
B(i,j)='√';
else if C(i-1,j)>=C(i,j-1)
%X(i) is not in LCS
C(i,j)=C(i-1,j);
B(i,j)='↑';
else
C(i,j)=C(i,j-1);
%Y(i) is not in LCS
B(i,j)='←';
end
end
end
end
lcsValue=C(m,n);
end

اسلاید 15 :

و) طولانیترین زیررشته مشترک

اسلاید 16 :

و) طولانیترین زیررشته مشترک
با استفاده از ماتریس B میتوانیم LCS را تولید کنیم.
چگونه؟
از B(m,n) شروع میکنیم و با توجه به علایم LCS را ایجاد میکنیم.
هر گاه به علامت ‘√’ در B(i,j) رسیدیم یعنی xi=yi المانی از LCS میباشد.

اسلاید 17 :

و) طولانیترین زیررشته مشترک
function PRINT_LCS(B,i,j)
global X;
if (i==0) || (j==0)
else if strcmp(B(i,j),' √ ')
PRINT_LCS(B,i-1,j-1);
disp(X(i));
else if strcmp(B(i,j),' ↑ ')
PRINT_LCS(B,i-1,j);
else
PRINT_LCS(B,i,j-1);
end
end
end
end

اسلاید 18 :

و) طولانیترین زیررشته مشترک