بخشی از پاورپوینت
اسلاید 1 :
بلند ترين زير دنباله مشترك
Longest common subsequence (LCS)
اسلاید 2 :
About DNA
دی ان ای مولکولی است که دستورهای ژنتیکی مورد استفاده در توسعه و عملکرد تمام موجودات زنده شناخته شده و بسیاری از ویروسها را کدگذاری میکند.
دی ان ای اسید نوکلئیکی است که شامل پروتئین و کربوهیدراتها میباشد.
اسیدهای نوکلئیک از سه ماکرو مولکول اصلی تشکیل شده اند که
برای زندگی همه گونههای شناخته شده ضروری میباشد.
اکثر مولکول دی ان ای از دو رشته پلیمری زیستی تشکیل میشوند
که به صورت حلقه دور هم پیچ خورده و به شکل یک مارپیچ دوگانه درآمده اند.
اسلاید 3 :
About DNA
هر نوکلئوتید از یک باز آلی،
گوانین (G)، یا
سیتوزین (C)، یا
آدنین (A)، یا
تیمین (T)، و
از یک قند مونوساکاریدی به نام دئوکسی ریبوز و یک گروه فسفات
تشکیل شده است.
نوکلئوتیدها به وسیله پیوند کوالانسی به صورت زنجیرهای به هم متصل میشوند،
نوکلئوتیدها از محل قند یک نوکلئوتید با فسفات نوکلئوتید دیگر پیوند ایجاد کرده و ساختاری شبیه ستون فقرات (رشته بلند) قند و فسفاتی را ایجاد میکنند.
اسلاید 4 :
About DNA
در هر کروموزوم واحدهای توارثی منفردی بهنان ژن هست.
هر ژن بخشی از مولکول اسید دیوکسی ریبونوکلئیک دیاناِ DNA است که
حامل اصلی اطلاعات وراثت محسوب میشود.
همه مولکولهای دیاناِ ترکیب شیمیائی واحدی دارند.
بهسبب ویژگیهای ساختاری این بازها، همواره A با T و G با C جفت میشود.
این بازها بهترتیبهای گوناگون در طول رشته قرار میگیرند و
این ترتیب، همان رمز توارث است.
آرایشهای گوناگون بازها، تنوع بسیار به دیاناِ از جهت پیامهای وراثتی (ژنتیک) میدهد.
اسلاید 5 :
About DNA
همین چهار باز تعیینکننده ویژگیهای همه جانداران هستند و
اینکه جاندار پرنده بشود یا ماهی یا شیر یا انسان،
ناشی از آرایش این بازها است.
G : گوانین
C : سیتوزین
A : آدنین
T : تیمین
اسلاید 6 :
بلند ترين زير دنباله مشترك Longest common subsequence (LCS)
در كاربرد هاي بيولوژي ، وقتيكه ميخواهيم DNA دو ارگان متفاوت را با هم مقايسه كنيم، ميتوانيم از مفهوم بلند ترين زير دنباله مشترك استفاده نماییم.
يك رشته DNA شامل يك دنباله اي از مولكول هائي است كه به آنها Base ميگويند.
برخي از اين Base ها عبارتند از
, Guanine, Cytosine, Thymine Adenine
هركدام از اين Base ها با حرف اول خود نشان داده ميشوند.
بعنوان مثال {A, G, C, T } ميتواند يك رشته DNA باشد.
اسلاید 7 :
بلند ترين زير دنباله مشترك Longest common subsequence (LCS)
یک هدف مقایسه دو رشته DNA پیدا کردن میزان شباهت بین آنها است.
این شباهت را میتوان از جمله به یکی از سه روش زیر پیدا کرد:
الف - اگر با حد اقل تعداد تغییرات روی base ها ، یک رشته به رشته دیگر
تبدیل گردد.
ب - اگر یک رشته زیر دنباله رشته دیگر باشد.
اسلاید 8 :
بلند ترين زير دنباله مشترك Longest common subsequence (LCS)
ج – برای دو رشته S1, S2 ، رشته جدیدی مانند S3 پیدا کنید بطوریکه، base های S3 در S1 و S2 ظاهر شوند ، اما ترتیب حضور این base ها در S1 و S2 باید همان ترتیب حضور در S3 باشد.
طبق تعریف، عناصر یک زیر دنباله در لیست میتوانند دقیقا بطور متوالی ظاهرنشوند.
هر چقدر رشته S3 طولانی تر باشد ، شباهت بیشتری بین S1 و S2 وجود دارد.
اسلاید 9 :
بلند ترين زير دنباله مشترك Longest common subsequence (LCS)
اسلاید 10 :
بلند ترين زير دنباله مشترك Longest common subsequence (LCS)
اسلاید 11 :
بلند ترين زير دنباله مشترك (LCS)
اسلاید 12 :
چكونه ميتوانيم LCS دو رشته را پيدا كنيم
يك راه حل بنظر ساده ولي غير معقول اين است كه
ابتدا كليه زير دنباله هاي موجود در رشته X را پيدا كنيم
سپس ببينيم كدام يك از اين زير دنباله ها در Y وجود دارند
و از بین زیر دنباله هائی که درY وجود داشتند، آن زير دنباله اي را انتخاب
كنيم كه بلند ترين طول را دارد.
اسلاید 13 :
چكونه ميتوانيم LCS دو رشته را پيدا كنيم
اسلاید 14 :
چكونه ميتوانيم LCS دو رشته را پيدا كنيم
مسئله LCS دارای یک خصوصیت زیر ساختاری بهینه
(Optimal sub-structure) است که باعث میشود بتوانیم آنرا به زیر مسئله های کوچکتر تقسیم کنیم.
این زیر مسئله ها مربوط میشوند به ذوج پیشوند های (Prefixes) دو دنباله ورودی.
اسلاید 15 :
مدل داده ليست List Data Model
اسلاید 16 :
چكونه ميتوانيم LCS دو رشته را پيدا كنيم
تعریف پیشوند:
اسلاید 17 :
بلند ترين زير دنباله مشترك (LCS)
اسلاید 18 :
چكونه ميتوانيم LCS دو رشته را پيدا كنيم
مسئله LCS دارای یک خصوصیت زیر ساختاری بهینه
(Optimal sub-structure) است که باعث میشود بتوانیم آنرا به زیر مسئله های کوچکتر تقسیم کنیم.
اسلاید 19 :
قضيه : زير ساختار بهينه براي يك LCS
اسلاید 20 :
يك راه حل بازگشتي براي پيدا كردن LCS
