الگوریتم ژنتیک

به نام خدا

چکیده مطالب

Leonard M.adleman آزمایش هایی در سال 1994 انجام دادو ثابت کرد که می توان ا ز DNA computing استفاده کرد در حل(direct Hamiltonain path) که یکی از  مسایل معروف NP-camplete problems در علم کامپیوتر است.

این مقاله شرح می دهد روشی را درDNA computing  برای حل مسالهء ((The minimum spanning tree  (مینیممدرخت گسترده).برای به کار بردن این روش باید مجموعهء شهرها کدگذاری شود در

رشته های منفرد  20-mer آلگونکلوتیدی(oligonucleotide) .

حالا فواصل متغیره راه ها بایدرمزگذاری شود در فواصل متفاوت در رشته های آلگونکلوتیدی با دو قسمت   10-mer  ی چسپیده به انتهاها با کدگذاری متناظر راه ها.

بعد از مراحل بعدی مانند:پیوندزنی(هیبرید شدگیhybridization).انعقاد ligation .تقویت بسط توسعه amplification  . بایدDNA  متناوب رمزگذاری شده مسله minimum spanning tree باید تصویه شود و متناوب شود ازباند شامل کوتاهترین طول DNA در ژل الکتروفرسیس   ( حرکت ذرات معلق مایع بوسیله نیروی برق) (electrophoresis) .

لغات کلیدی: DNA computing Hamiltonian path problem minimum spanning tree problem

مقدمه

محاسبات DNA اطلاق می شود به خط مشی DNA  برای محاسبه به وسیله تکنیک های زیست مولکولی برای: کد گذاری اطلاعات وتولید بالقوه راه حل ها و انتخاب وتشخیص درست راه حل.

آدلمان انجام داد آزمایش های پیشگامانه ای در سال 1994 برای ثابت کردن اینکه DNA computing میتواند مورد استفاده قرار گیرد در حل مسله راه مستقیم همیلتون direct Hamiltonian path این مسله اولین بار پیشنهاد شد توسط William Rowan Hamilton 1805-1865 این مسله یک مسله معروف NP-complete  است و به نظر می رسد که وجود ندارد الگوریتم کارایی برای حل این مسله در چند جمله ای های زمانی.

مسله راه همیلتون را می توان به صورت زیر  توصیف کرد:

مجموعه ی مفروض شهرها را با نقاط شروع و پایان  و راه های ارتباطی بین انها در نظر می گیریم . ایا ممکن است که با عبور فقط یک بار از هر شهری از  همه انها عبور کرد؟

قرارداد ادلمان  به این صورت است که :شهرها کد گذاری شود با رشته های منفرد 20-mer الگونکلوتیدی به صورت متمایز( یعنی کد شهرها منحصر به فرد باشد) وراه بین شهرها در رشته های 20-mer الگونکلوتیدی با تناوب تکمیل کنند برای نصف تناوب ارتباط شهرها.

تناوب DNA کدگذاری می کند همه راه حل های بالقوه ای که می تواند تولید شود از پیوند زنی الگونکلوتیدها به نمایندگی شهر ها وراه ها.

بعد از انعقاد پیوند زنی الگونکلوتیدها.تناوب DNA که شروع می شود وپایان می یابد درست در شهرها می تواند تقویت شود  به وسیله PCR polymerase chain reaction با استرهای primers مخصوص.

سپس محصولات PCR می توانند به صورت متناوب  خالص شوند در میان سیستم biotin-avidin magnetic beads به وسیله هر نماینده الگونکلوتیدی در میان شهرها.

تناوب DNA با طول های درست می توانند خالص سازی ژلی gel-purified شود بعد از کار کردن gel electrophoresis.

ترتیب دهی تصویه DNA با طول درست اشکار خواهد کرد جزئیات مسیررا.

عملکرد رله های محاسباتیDNA در منطق هیبریدی (پیوندی) :

توانایی کدگذاری و حل مسائل محاسباتی به وسیله درست جفت کردن و جلوگیری از اشتباه پایه گذاری جفت ها.

به علت اینکه پیوند زنی DNAوابسته است به محاسبات موازی زیادی از ان انتظار می رود که بسیا عالی تر باشد از کامپیوترهای بیس سلیکونی.

مقایسه کامپیوتر های  سیلیکونی متعارف با DNA computing  :

محاسبات سخت افزاریی مبنی بر مواد سیلیکونی – کد گذاری باینری- منطق بولی- وپردازش سریالی

DNA computing   مشخصات متمایزی دارد مثل محاسبات سخت افزاری مبنی بر ملکول های DNA- کد گذاری چهار گانه (کواترنری)-

[i.e. A(Adenine) T(Thymine) G(Guanine) C(Cytosine)]

منطق هیبریدی- محاسبات موازی – و غیره....

در طول چند سال گذشته محاسبات DNA پیشنهاد شده برای حل مسائل مثل: مسله راه  همیلتون – مسله حداکثر مجموعه max  - مسله سوارکار – ساختن جمع اعداد صحیح – برای شکستگی اطلاعات پنهان شده استاندارد متعارف (DES) – 3-SAT problem   متغییر-20 – و در مسله کوتاهترین راه مسافرت فروشنده – و غیره...

این مقاله توضیح می دهد شیوه ی  محاسبات DNA شبیه قرار داد ادلمان در حل مسله مینیم گستردگی درخت .

قرار داد اصلی ادلمان مطرح شده بود برای یافتن راه در مسله راه درست همیلتون. بنابراین پارامترفاصله بین شهرها مورد ملاحضه نبود .

ما پیشنهاد می کنیم به الحاق کردن قطعه از جفت رشته های الگونکلوتیدی به نمایندگی از فاصله بین شهر ها  در رمزگذاری الگو نکلوتیدها ارتباط بین شهر ها.

 بعد از این تغییر اصلاحی در شکل محاسبات الگونکلوتیدی. قرار داد ادلمان می تواند مورد استفاده قرار گیرد در حل مسله ی کمترین گستردگی درخت.

2- دور نما( زمینه) (معلومات قبلی)  

مسله کوچکترین درخت گسترده  :

مسله ی کوچکترین درخت را می توان توضیح داد به صورت ساده به شرح زیر:

 فرض می کنیم مجموعه ای از شهرها را که همه شهرها مر تبط شده اند در درخت گسترده ای (درختی گسترده است که در گراف ان مرتبط شود همه شهرها به هم بدون اینکه گردشی (چرخشی) باشد) به این صورت که همه ی فاصله های درخت گسترده کوچکترین حالت شود.

شیوه مبنی است بر انتقال مستقیم برای پیدا کردن همه ی امکان های درخت گسترده و معیین ساختن همه طول ها.

بعد از مقایسه همهء براوردارزش ها کوچکترین درخت گسترده را می شود پیدا کرد.

با وجود این، این روش می تواند بسیار جامع باشد از انجایی که حالت های ممکن درخت گسترده تمایل دارد به افزایش زیاد همراه با افزایش در خصوص تعداد شهرها.

گراف مخصوص مضطرب در این مقاله نشان داده شده در تصویر  1-A 

و کوچکترین درخت گسترده برای مجموعه ی شهرها داده شده در شکل 1-B ما یازده شهر به عنوان مدل ومجموعه فاصله های بین شهرها را بطور قرار دادی انتخاب می کنیم .

الگوریتم برای مسله ی کوچکترین درخت گسترده :

مرحله اول : ساختن و تولید کردن راه های رندوم در میان گراف

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

مرحله سوم : پیدا کردن کوچکترین درخت گسترده

3- انجام الگوریتم .

3-1- کدگذاری طرح نقشه.

 شکل 2 تصویر کدگذاری درDNA است. ماکدگذاری می کنیم شهرهارا در رشته های منفرد 20-mer ی منحصربه فرد (شکل2-A ) الان متغییر فاصله های راه می تواند کد گذاری شود با فاصله های مختلف به وسیله ی رشته های جفت شده ی الگونکلوتیدی با دو برامدگی کد گذاری شده 10-mer  متناظر با راه که به انتها چسپیده شده است (شکل2-B).

برای مثال فاصله بین شهر های 3 و4 در مجموعه 10 بود بنابراین ما کد گذاری میکنیم 10-bp رشته جفت شده DNA  به نمایندگی فاصله ی  بخش (اینجا،ما تعریف می کنیم    1-bpرشته جفت شده   DNAبرای یک فاصله واحد) درازترین فاصله ما بین شهرها  کد گذاری می شود با درازترین طول رشته یجفت شده DNA.

علاوه بر این قسمت ذکر شده دوتا رشته 10-mer اضافی چسپیده به انتهاهای کدهای متناظر راه برای کدگذاری ما بین شهرها در ملکول DNA  خواهد بود.

برای هر راه مابین  شهرهای i to j رشته جفت شده  DNA  با دو بر جستگی چسپیده به انتها هامی تواند تولید شود به وسیله ی پیوند زن دو تا رشته الگونکلوتیدها:

یکی برای اینکه نماینده فاصله قطعه و نیز دیگری که شامل 3 تا 10-mer از Oi ( oligonucleotide i ) که دنبال شده به وسیله فاصله قطعه و 5 تا 10-mer از Oj

پیاده سازی :

برای پیاده سازیمرحله اول از الگوریتم همه الگونکلوتیدها کد گذاری می شوند  از اطلاعات شهر ها و راه ها (شامل فاصله ها ) .

برای  هر راه Oij ،الگونکلوتید سرویس میدهد به عنوان تراشه ای که به وجود می اورد اتحاد الگو نکلوتیدها را در جهت شهرهای مجاور با هم  برای بسته شدن (انعقاد) تصویر  .(2-c)

از این رو واکنش انعقاد نتیجه می دهد در شکل دادن از مبدا کد گذاری رندوم مولکولی DNA راه ها .پس محصول مرحله یک تقویت می شود توسط PCR استفاده شده اولیه همگانی.

بنا براین ،نمونه    DNAمی تواند تقویت شود .برای اجرا کردن مرحله دوم از الگوریتم محصول مرحله اول باید متناوبا خالص شود میان biotion-avidin magnetic beads  system 

با هر الگونکلوتید نماینده شهرهای در میان امده.فقط رشته منفرد مولکول DNA مکمل همه تناوبها کد گذاری شهرها باید نگه داری شود .

برای اجرای مرحله سوم الگوریتم محصول مرحله دوم باید تقویت شود توسط PCR و جدا شود توسط ژل الکتروفورسیس electrophoresis

بعد از اینکه اطلاعات مسافت ها کد گذاری  شد در راه های الگونکلوتیدها ، ما می توانیم بگوییم شاخه های درخت گسترده را از روی شاخه های موکلول DNA .

کد گذاری متناوب مسله کوچکترین درخت گسترده باید خالص شود و متوالی باشد از باند شامل کوتاه ترین طول از DNA در electrophoresis.

نتایج:

ایجا ما پیشنهاد دادایم روشی را برای محاسبات DNA شبیه قرار دادادلمان در حل مسله مینیم درخت گسترده.

محاسبات مولکو لی DNA نه تنها اطلاعات شهرها را بلکه همچنین اطلاعات فاصله میان شهر ها را کد گذاری می کند.

خالص سازی و توالی باند شامل کوچکترین طول DNA در electrophoresis می تواند پیداکند مسله کوچکترین درخت گسترده را.

                                        والسلام