مقدمه :

محاسبات مبتنی بر DNA که با عناوین محاسبه مولکولی و یا برنامه نویسی مولکولی هم شناخته می شود در سال 1994 توسط لئونارد ادلمن مطرح گردید . وی که استاد ریاضی و کامپیو تر دانشگاه کالیفرنیا بود برای نخستین بار نشان داد که می توان از مولکول های DNA در ازمایشگاه های بیو لوژیک ، برای انجام محاسبات حتی بدون به کار گیری ماشین های کنونی ، بهره گرفت .ادلمن در نخستین مقاله خود نشان داد که رشته های DNA می توانند برای حل مسئله NP-complet مسیر هامیلتونی به کار گرفته شوند . در علوم کامپیوتر ، مسائل به دو دسته p و np تقسیم می شوند که مسائل P مسائلی هستند که در زمان چند جمله ای قابل حل و مسائل NP مسائلی هستند که درستی جواب ان ها در زمان چند جمله ای قابل تست است . در کلاس NP دسته های NP-complet و NP- hard وجود دارند که در زمان چند جمله ای قابل حل نیستند و یکی از شاخه های تحقیقاتی در علوم کامپیوتر ، بررسی چنین مسائلی لا ابزار های جدید است . یکی از این ابزار های جدید محاسباتی مولکولی می باشد که در ان با استفاده از رشته های DNA و عملیات متداول روی انها ، اقدام به حل مسائل می شود .لیپتون نیز در سال 1995 نشان داد نتایج ازمایشادلمن می تواند برای حل مسئله صدق پذیری ( SAT) به کار گرفته شود . همچنین در طولاین مدت چرلز بنت تیز کار هایی در زمینه محاسبات مبتنی بر DNA انجام داد.انجام محاسبات DNA ای به خاطر قابلیت پردازش موازی ان بسیار حائز اهمیت می باشد . با قرار دادن تعداد کافی رشته DNA برای حل مسئله ، به علت انجام همزمان عملیات روی تمام رشته ها می توان در زمانی با تابع پیجیدگی چند جمله ای مسئله را حل نمود و اساسا از ان جایی که سلول های بدن انسان و کامپیوتر در دو امر پردازش و ذخیره سازی اطلاعات شباهت های بسیار زیادی به هم دارند لذا همین شباهت موجب شکل گیری ایده ای انقلابی در زمینه ساخت کامپیوتر هایی موسوم به کامپیوتر های مولکولی گردید .

  فهرست مطالب

فصل اول : مفاهیم

1-1: تعریف                                                                                                   5

1-1-1: محاسباتی مبتنی بر DNA                       ا                                            5

1-1-2: ایده به کار گیری محاسبات در سطح مولکولی                                       5

1-2: اساس پردازشی                                                                                       5

1-3 : مدل بندی                                                                                              6

1-4: ساختار ظاهری                                                                                        6

1-5 : انرژی مولکول های DNA                                                  ا                    7

1-5-1: چگونه DNA انرژی را ذخیره می کند ؟                                               8

1-5-2 : چگونه کامپیوتر سوخت مورد نیاز خود را از ورودی دریافت می کند ؟     8

1-6: اجزای تشکیل دهنده یک کامپیوتر DNA          ا                                        9

1-7: دلیل به کار گیری محاسباتی مبتنی بر مولکول                                             9

محاسبات مبتنی بر DNA1

فصل دوم : ویژگی های محاسباتی مبتنی بر DNA

2-1: مبانی محاسباتی DNA                                                                       ا    13

2-2: خصوصیات DNA                                                                                 14

2-3: DNA computing and bio computing                     ا                    14

2-4: یکتایی DNA computing               ا                                                   15

2-5: محرکی برای محاسبات مبتنی بر DNA                                                    16

2-6: طبیعت DNA COMPUTING       ا                                                       16

2-6-1: جنبه های عمومی کار                                                                         16

2-6-2: ذخیره اطلاعات و قابلیت های پردازشی                                                 17

2-6-3: مقایسه کارایی                                                                                    18

2-6-4: حوزه های کاری در محاسبات مبتنی بر DNA                        ا               20

2-6-5: تئوری پیاده سازی و ماشین تورینگ                                                      21

2-7: کاربرد های محاسباتی مبتنی بر DNA                                            ا          23

2-8: مقایسه کامپیوتر های مبتنی بر DNA و کامپیوتر های مبتنی بر الکترو نیک    23

2-8-1: شباهت ها                                                                                          24

2-8-2: تفاوت ها                                                                                           25

2-9: مزیت به کار گیری کامپیوتر های مبتنی بر DNA                              ا        26

2-10 : محدودیت های موجود در به کار گیری کامپیوتر های مبتنی بر DNA     ا 27

محاسبات مبتنی بر DNA2 محاسبات مبتنی بر DNA2

فصل سوم : عملگر های DNA

3-1 : WATSON- CRICK                                                                       ا    30

3-2: synthesis                                                                            ا              30

3-3: melting and annealing                                              ا                   31

3-4: ligases and nucleases                                                ا                  31

3-5: gel electrophorsis                                                          ا               32

3-6: پلمریس و واکنش زنجیری پلیمریس PRC                                          ا     33

3-7: تفکیک هیبریداسیون                                                                               36

3-8 : استخراج                                                                                                36

3-9: اتصال                                                                                                    36

3-10 : اشکار سازی                                                                                       37

3-11 : انزیم های بازدارنده                                                                              37

محاسبات مبتنی بر DNA3

فصل چهارم : ازمایش ادلمن

4-1: مساله مسیرهمیلتون ( HPP )                                                          ا           40

4-2: راه حل ادلمن برای مساله مسیر همیلتونی                                                     41

4-3: عملگر های مدل ادلمن – لیپتون                                                               43

4-3-1: استخراج{ SEPARATE(P.S) }                             ا                           43

4-3-2: جداسازی بر حسب طول {SEPARATE(P.L) }                            ا      43

4-3-3: { merg( p1. P2) }                                                           ا             44

4-3-4: {anneal(p) }                                                                          ا       44

4-3-5: { detect(p) }                                                                          ا     44

4-3-6: { append (p,z) }                                                                       ا  44

4-3-7: { discard(p) }                                                                           ا    44

4-3-8: { read(p) }                                                                               ا    44

4-4: بررسی یک مثال                                                                                     45

فصل پنجم : حل مسئله کوتاهترین مسیر

5-1: مساله کوتاهترین مسیر                                                                              54

5-2: تعریف مساله کوتاهترین مسیر                                                                   54

5-3: کد گذاری اعدا حقیقی در محاسبات مولکولی                                            54

5-4: الگوریتم DNA                                                        ا                             55

5-4-1: گام 1 – کد نمودن مساله توسط رشته های DNA                           ا       56

5-4-2: گام 2- تولید مسیر های تصادفی                                                          56

5-4-3: گام 3- گسترش مسیر های DNA توسط پلیمریس ( PCR )                  ا56

5-4-4: گام 4 – حذف ند های تکراری                                                           56

5-4-5: گام 5 : ترتیب رشته های DNA                                                       ا   57

5-5 : بررسی روند الگوریتم در قالب مثال                                                         57

5-6: پیچیدگی الگوریتم DNA                                                            ا           72

5-7: الگوریتم کامپیوتری                                                                                 74

5-8: پیچیدگی شبیه سازی کامپیوتری                                                               75

فصل ششم : نتیجه گیری            ا

6-1: مروری بر مطالب                                                                                     79

6-2: محدودیت های راه حل                                                                           79

6-3: فرصت های اتی و پیشنهادات                                                                    79

منابع وماخذ                                                                                                    81

فهرست منابع فارسی                                                                                         81

فهرست منابع لاتین                                                                                          82

چکیده ا نگلیسی                                                                                             84

فهرست جدول ها

جدول 1-4: چگونگی کد نمودن رئوس گراف                                                    46

جدول 4-2: چگونگی کد نمودن یال های گراف                                                 48

جدوا 5-1: کد کردن رئوس گراف 1 در SSP                                          ا        58

جدول 5-2: کدکردن یال های گراف 1 در SSP                                        ا       59

جدول 5-3: کد کردن رئوس گراف 2در SSP                                           ا       69

جدول 5-4: کد کردن یال های گراف 2 در SSP                                          ا     69

فهرست شکل ها

شکل 2-1: مولکول DNA دو رشته ای                                                  13

شکل 3-1: جفت شدن دو رشته مکمل                                                     30

شکل 3-2: اتصال و انفصال DNA                                                          ا32

شکل 3-3: فرایند الکتروفورسیس ژل                                                        33

شکل 3-4: فتو گراف عملکرد الکتروفورسیس ژل                                      33

شکل 3-5 : فرایند PCR                                                                  ا      35

شکل 3-6: عما الحاق توسط پلیمریس                                                      35

شکل3-7 : قطع رشته دو تایی DNA بوسیله sau3AI                        ا       37

شکل 4-1: گراف جهت دار باند مبدا 0وند مقصد 6                                41

شکل 4-2: گراف نمونه                                                                          45

شکل 4-3: نحوه نامگذاری                                                                      47

شکل 5-1: اولین گراف نمونه برای حل مسئله کوتاهترین مسیر                   58

شکل 5-2 : دومین گراف نمونه برای حل مساله کوتاهترین مسیر                  68

شکل 5-3 : گراف ازمون                                                                                    76

انرژی مولکول های DNA :

چه به وسیله باتری و پهبه وسیله برق ، همواره نیاز به انرزی برای انجام اعمال محاسباتی می گردد. در این بخش قصد داریم مولکول های DNA را از نظر انرژی مورد بررسی قرار دهیم .بدیهی است که کامپیوتر ها از طریق برق ویا باتری انرژی خود را تامین می تمایند اما در مورد یک کامپیوتر مولکولی قصد داریم روند تامین انرژی را برای ان تحت بررسی قرار دهیم .پروفسور EUde Shapiro از انستیتوی Weizmann تبلیغات جهانی خود را برای ساخت یک ماشین محاسباتی ، که از انزیم ها و مولکول های DNA تشکیل شده باشد اغاز نمود .هدف تیم وی ، ساخت یک وسیله منحصر به فرد از نظر صرفه جویی در مصرف انرژی بود . که در ان مولکول DNA بتواند سوخت مورد نیاز کامپیوتر را تامین نماید .در بخش های بعدی مطرح خواهد شد که چگونه یک مولکول DNA اطلاعات را در قالب کد های ژنیتیکی ذخیره می کند و طبیعت از DNA به عنوان یک انباره ذخیره اطلاعاتی بهره می گیرد .ازمایشات نشان میدهد که برای نخستین بار می توان از مولکول های DNA به عنوان ورودی و در عین حال ازانرژی ذخیره شده در همان مولکول به عنوان سوخت استفاده کرد . یک چنین ترکیبی از نظر علمی ، با کامپیوتر های الکترونیکی کتداول غیر ممکن است اما در سیستم های مبتنی بر DNA ، داده های مولکولی از طریق خود انگیزه اننده ازاد کننده انرژی پردازش می شوند .این کامپیوتر ها پیوند بین مولکول های DNA را شکسته و انرژی ای را که در این پیوند به صورت گرما ذخیره شده است ازاد می کنند . این فرایند انرژی کافی برای ادامه محاسبات را بدون نیاز به منبع خارجی انرژی فراهم خواهد نمود .این کامپیوتر ها به انرژی بسیار کمی نیاز دارند .( همانطور که گفته شد به وسیله مولکول های DNA ورودی ، این انرژی تامین خواهد شد ) و در مجموع کمتر از 25 میلیو نیم وات گرما ازاد میکند . اما در مقابل کامپیوتر های الکترونیکی نیاز به مقدار زیادی انرژی دارند و هنگام محاسبات مقدار زیادی گرما تولید می کنند . عملخنکنگه داشتن سازه های کامپیوتری مسئله مهمیدر مهندسی کامپیوتر محسوب می گردد. این موضوع بسیاری از محققان را به سمت خود جلب می کند تا محدودیت های درونی کامپیوتر را از لحاظ مصرف انرژی و تولید گرما ی هدر رفته بررسی کنند .

چگونه DNA انرژی ذخیره می کند ؟

بحث در مورد ذخیره انرژی اساسا یک موضوع چالش برانگیز است . سنگی را در نظر بگیرید که از سطح زمین بالا می رود ، این سنگ انرژی پتانسیل به دست می اورد و هنگامی که می افتد ممکن است هر چیزی را که به ان برخورد میکند بشکند یا ضربه مهلکی به زمین وارد اورد . لذا تصورات ما در مورد وجود انرژی پتانسیل یا همان انرژی ذخیره شده به صورت یک خاصیت نسبی مطرح است .با همین استدلال ، یک پلیمر DNA مقدار چشمگیری انرزی ذخیره می کند . مولکول های DNA به یک باره از هم جدا نمی شوند ، ( در بخش ها یعدی تشریح خواهد شد که ساختار یک مولکول DNA به چه صورت است )اما هنگامی که این پیوند شکسته شود انرزی موجود در ولکول ازاد خواهد شد و انرژی ازاد شده از شکستن مولکول های DNA می تواند برای انجام اعمال محاسباتی مورد استفاده قرار گیرد .

اجزای تشکیل دهنده یک کامپیوتر DNA :

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

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

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

محدودیت های موجود در به کارگیری کامپیوتر های مبتنی بر DNA :

در این بخش به برخی محدودیت ها ی مهم سیستم های مبتنی بر DNA اشاره خواهد شد :

  1. برای تولید مجموعه جواب ، حتی در یک مسئله نسبتا ساده نیز ممکن است به مقادیر زیادی رشته DNA نیاز داشته باشیم .
  2. در برخی از مسائل تجربی و غیر قطعی شامل تغییر نرخ خطا ، تکنیک های رمز گذاری بهینه و غیره ، برای هر جواب میلیون ها مسیر نادرست تشکیل می گردد که ارزشی ندارد و باید از مجموعه جواب حذف گردد.
  3. برای اجرای برخی عملیات ، حذف کردن رشته های نادرست از مجموعه جواب به حضور انسان نیاز خواهیم داشت و این امر خود یکی از محدودیت های اساسی در محاسبات مبتنی بر DNA به شمار می رود .

مقطع کارشناسی ارشد

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


فایل pdf غیر قابل ویرایش

قیمت25000تومان

قیمت45000تومان