مسئلۀ گراف همیلتنى در یک قاشق آب‌نمک!

در سدۀ 18 میلادى، ویلیام همیلتون [1]، ریاضی‌دان و ستاره‌شناس ایرلندى، مسئله‌اى مطرح کرد که در آن باید براى گره‌هاى یک گراف، مسیرى را پیدا کرد که از گره آغازین گراف شروع شود و در گره پایانى آن خاتمه یابد؛ به شرط آنکه از تمام گره‌هاى گراف، یک و تنها یک بار عبور کند. از مسیرهاى همیلتنى براى حل بسیارى از مسائل دنیاى واقعى استفاده مى‌شود. این گراف‌ها در نظریۀ بازى‌ها، گرافیک و بینایى کامپیوتر و رباتیک کاربرد ویژه‌اى دارند.

مسئلۀ فروشندۀ دوره‌گرد یکى از مشهورترین انواع این مسائل است. در این مسئله تعدادى شهر و هزینۀ رفتن مستقیم از هر یک به دیگرى داده شده است و کم‌هزینه‌ترین مسیرى که از یک شهر شروع شود و از تمامى شهرها دقیقاً یک بار عبور کند و به شهر شروع بازگردد، مطلوب است. این مسئله جزو مسائل سخت NP [2]، محسوب می‌شود.

در سال 1994 ، لئونارد آدِلمَن [3]، دانشمند علوم کامپیوتر، با ساخت رشته‌هاى دى‌ان‌اى در آزمایشگاه و قرار دادن آن‌ها در لولۀ آزمایش حاوى آب‌نمک، تلاش کرد مسئلۀ فروشنده دوره‌گرد مدار همیلتنى را حل کند. این آزمایش انقلابى در دنیاى تکنولوژى ایجاد کرد که منجر به ظهور مفهوم دى‌ان‌اى رایانه‌ها شد!

رایانش دى‌ان‌اى مفهومى را معرفى مى‌کند که در آن به جاى تراشه‌هاى سیلیکونى، مولکول‌هاى دى‌ان‌اى محلى براى ذخیره‌سازى داده‌ها و اجراى محاسبات منطقى و ریاضى هستند. در این رایانه‌ها مجموعه‌اى از رشته‌هاى دى‌ان‌اى، به طور مشخصى با یکدیگر ترکیب مى‌شوند تا پاسخ برخى از مسئله‌ها را پیدا کنند. موضوع رایانش دى‌ان‌اى بحثى بسیار پیچیده است و در این مقاله تا حد امکان تلاش مى‌کنیم به ساده‌ترین بیان ممکن به آن بپردازیم.

قبل از اینکه با داستان آدلمن و چگونگى سازوکار این رایانه‌ها آشنا شویم، بد نیست کمى راجع به ساختار دى‌ان‌اى بدانیم.

ساختمان دى‌ان‌اى

دى‌ان‌اى یک ساختار دو رشته‌اى متشکل از 4 نوکلئوتید (گونه‌اى از مولکول‌هاى ترکیبات آلى) است. این نوکلئوتیدها آدنین (A)، تیمین (T)، ستوزین (C) و گوانین (G) نامیده می‌شود. این 4 نوکلئوتید با تشکیل پیوند، به شکل دو دنبالۀ خطى، ساختمان دى‌ان‌اى را مى‌سازند. البته براى تشکیل مارپیچ‌هاى دوگانۀ دى‌ان‌اى، G فقط با C و T فقط با A، تشکیل پیوند مى‌دهند. بنابراین، هر رشتۀ دى‌ان‌اى یک مکمل مشخص دارد که به ازاى هر نوکلئوتید متناظر جفت‌شونده آن نوکلئوتید وجود دارد.

اگر در مجموعۀ جوابى که کار مى‌کنیم رشتۀ مکمل یک رشته موجود باشد، این دو رشته با هم جفت مى‌شوند و ساختمان مارپیچ دى‌ان‌اى را مى‌سازند. به طور مثال نوکلئوتید A از یک رشتۀ دى‌ان‌اى با نوکلئوتید مکمل آن یعنی T در رشته‌اى دیگر مى‌تواند تشکیل پیوند دهد اما با نوکلئوتیدهای C و G جفت نمی‌شوند. حالا اگر مکمل تمام نوکلئوتیدهاى یک رشته در رشتۀ دیگر یافت شوند، آن دو رشته با هم جفت مى‌شوند و ساختمان مارپیچ به وجود مى‌آید.

راه حل آدلمن براى مسئلۀ مسیر همیلتنى با کمک دى‌ان‌اى رایانه

آدلمن گرافى همیلتنى را مورد بررسى قرار داد که متشکل از 7 گره و 14 یال جهت‌دار بود. یعنى میان هر دو گره یک مسیر مستقیم براى رفت و یک مسیر مستقیم براى برگشت وجود دارد. آدلمن براى نمایش نام شهرها (گره‌هاى گراف) از دنباله‌اى 8 تایى متشکل از نوکلئوتیدهایى تصادفى که در شرایط آزمایشگاهى با روش نوترکیبى ژنتیک بر رشته‌هاى دى‌ان‌اى قرار گرفتند، استفاده کرد. براى مثال براى شهر (گره) A دنبالۀ ACTTGCAG، شهر (گره) B دنبالۀ TCGGACTG و شهر (گره) C، دنبالۀ GGCTATGT را تعریف کرد که نیمۀ اول دنباله، به عنوان بخش اول نام شهر و نیمۀ دوم دنباله، بخش دوم نام شهر معرفى شد. به طور مثال براى شهر A، بخش ACTT نیمۀ اول نام شهر A و GCAG نیمۀ دوم نام شهر A است. اهمیت تقسیم نام شهر به دو نیمه را در ادامه خواهید دید. با ترکیب نیمۀ دوم شهر مبدأ با نیمۀ اول شهر مقصد نیز، مسیر میان آن دو شهر (یال) مشخص مى‌شود. به طور مثال، مسیر میان دو شهر A و B که در آن A مبدأ و B مقصد است (یال AB)، به صورت GCAGTCGG (بخش GCAG نیمۀ دوم شهر (گره) مبدأ A و TCGG نیمۀ اول شهر مقصد یعنى گره B است) و مسیر (یال) BC به صورت ACTGGGCT است. آدلمن رشتۀ مکمل نام شهرها را نیز در شرایط آزمایشگاهى تولید کرد.

او 10 به توان 14 مولکول از رشته‌هاى متفاوت را در یک لولۀ آزمایش قرار داد. براى نزدیک کردن شرایط لولۀ آزمایش به سلول موجود زنده مقدارى آب نمک به لوله افزود (نمک سدیم یکى از عناصر اصلى مایع اطراف سلول‌ها است.) آدلمن 1 ثانیه بعد، در محلولى با حجم کمتر از یک‌پانزدهم قاشق چاى‌خورى، جواب مسئله را داشت!

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

آدلمن چگونه به جواب رسید؟

با توجه به شیوه کد کردن، مثلاً مسیر (یال) میان شهر A و B (رشته GCAGTCGG ) و مکمل شهر(گره) B (رشته AGCCTGAC) ممکن است به طور اتفاقی باهم روبرو شوند. بر اساس طراحی کدها، رشتۀ اول (یال AB) به TCGG ختم و رشتۀ دوم (مکمل شهر B) با AGCC آغاز می­‌شود؛ از آنجا که نوکلئوتیدهای این دو بخش مکمل یکدیگرند، به هم خواهند چسبید. (و رشتۀ طولانی‌تر GCAGTCGG AGCCTGAC تشکیل خواهد شد.) اگر نتیجۀ حاصل با رشتۀ حاوی مسیر BC (ACTGGGCT) رودررو شود، این رشته نیز، به مجموعۀ رشتۀ حاصل از اتصال قبل، خواهد چسبید؛ چون انتهای رشتۀ حاصل از اتصال قبل یعنی TGAC مکمل شروع رشتۀ BC (ACTG) می‌باشد. به همین ترتیب، طول ترکیبات با چسبیدن مسیرها به هم با استفاده از مکمل نام شهر­ها افزایش می‌یابد. در نهایت لولۀ آزمایش سرشار از رشته‌­هایی خواهد بود، که کدشدۀ مسیر­های تصادفی میان شهر­های مختلف هستند. از آنجا که تعداد مولکول­‌های اولیه بسیار زیاد بود و تعداد شهر­ها نیز بسیار کم است، می­‌توان گفت که تمام مسیر­های ممکن میان شهرها (گره‌­ها) ساخته شده و با یک اطمینان تقریبی حداقل یکی از این مسیرها، همان مسیر همیلتنی موردنظر است.

متأسفانه همان طور که آدلمن مسیر همیلتنى را در لولۀ آزمایش داشت، ده‌ها تریلیون مسیر دیگر نیز در لولۀ آزمایش وجود داشتند که همیلتنى نبودند و آدلمن باید آن‌ها را جداسازى مى کرد. غربالگرى رشته‌هاى دى‌ان‌اى از یکدیگر نیز، طى فرآیندهایى جالب با به کارگیرى خواص زیستى شیمیایى رشته‌هاى دى‌ان‌اى رخ داد، که بحث پیرامون آن از حوصلۀ مطلب خارج است.[4]

در نهایت آدلمن موفق به جداسازى رشتۀ دى‌ان‌اى حاوى مسیر همیلتنى، از رشته‌هاى نامرتبط شد و این آزمایش موفق، سرآغازى براى پژوهش در زمینۀ رایانش دى‌ان‌اى شد.

در ادامه به بحث راجع به مفهوم کلى رایانش دى‌ان‌اى، که با آزمایش آدلمن شکل گرفت، مزایاى استفاده از این نوع رایانه‌ها و پیشرفت‌ها و چالش‌هاى آن مى‌پردازیم.

رایانش دی‌­­ان‌­ای

در رایانه‌هایى که از رایانش دى‌ان‌اى استفاده مى‌کنند، به جاى استفاده از سیگنال الکتریکى براى نمایش یک بیت اطلاعات، از خواص شیمیایى مولکول‌هاى دى‌ان‌اى استفاده مى‌شود. در واقع الفباى 4 کاراکترى نوکلئوتیدها، جایگرین الفباى باینرى شده است. دى‌ان‌اى رایانه از نوکلئوتیدهاى آدنین (A)، سیتوزین (C)، تیمین (T) و گوانین (G) به جاى صفر و یک متداول در الفباى باینرى استفاده مى‌کند. ورودى الگوریتم، یک یا چند رشته مولکول دى‌ان‌اى است و رایانش در فضاى یک لولۀ آزمایش یا اسلاید شیشه‌اى صورت مى‌پذیرد. این رایانش در واقع آزمایشى بر روى مولکول‌هاى دى‌ان‌اى است؛ آزمایش‌هایى از قبیل مرتب‌سازى رشته‌ها بر اساس طول آن‌ها یا برش‌ بخشى از رشته‌ها که حاوى ترکیب یا پیوند خاصى از نوکلئوتیدها هستند. با اعمال این تغییرات رشتۀ نهایى در واقع به عنوان رشتۀ خروجى معرفى مى‌شود. براى مثال در آزمایش آدلمن، این تغییرات، همان اتصال رشته‌هاى مکمل به یکدیگر براى تشکیل مسیرهاى مختلف و جداسازى رشته‌ها از رشته‌هاى نامربوط بود. خروجى برنامه هم رشتۀ حاوى مسیر همیلتنى بود.

چرا دى‌ان‌اى رایانه؟

مهم‌ترین دلیل براى انتخاب دى‌ان‌اى رایانه‌ها، ظرفیت بسیار بالایى است که این رایانه‌ها در مقایسه با رایانه‌هاى سیلیکونى براى ذخیرۀ اطلاعات دارند. ذخیرۀ این حجم بالاى اطلاعات در فضایى کم، به معنى چگالى فوق‌العاده بالاى این رایانه‌هاست. یک بیت در دى‌ان‌اى به اندازۀ یک نانومتر مکعب فضا اشغال مى‌کند در حالى که در حافظه‌هاى سخت افزارى موجود، یک بیت را مى‌توان در 10 به توان 12 نانومتر مکعب ذخیره کرد.

از دلایل دیگر مى‌توان به دردسترس بودن همیشگى منابع دى‌ان‌اى اشاره کرد. به عبارتى تا زمانى که موجود زنده در جهان وجود دارد مى توان رایانه ساخت!

این عرضۀ وسیع دى‌ان‌اى قیمت آن را بسیار ارزان کرده است.

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

یکى از مزایاى جالب دى‌ان‌اى رایانه‌ها قابلیت اجراى عملیات‌هاى موازى است. یک لولۀ آزمایش مى تواند حاوى 10 تریلیون رشتۀ دى‌ان‌اى باشد؛ هر رشته یک محاسبۀ منطقى یا ریاضى را پردازش کند و در یک زمان، تنها در یک لولۀ آزمایش، 10 تریلیون محاسبه پردازش شود!

پیشرفت‌ها

على‌رغم نوپا بودن دى‌ان‌اى رایانه‌ها دستاوردهاى جالبى در این زمینه حاصل شده است. از ذخیره‌سازى اطلاعات در سلول‌هاى موجودات زنده (DNA Storage)، تا ساخت گیت‌هاى منطقى عملگر بر رشته‌های دی‌ان‌ای.

چگالى بالاى ذخیره‌سازى اطلاعات در رشته‌هاى دى‌ان‌اى و قابلیت موازى بودن فعالیت‌ها در آن‌ها، رایانش دى‌ان‌اى را تبدیل به یک زمینۀ تحقیقاتى داغ در قرن بیست‌ویکم کرده است.

در این مقاله سعى شد به طور خلاصه و ساده به مقدمات رایانش دى‌ان‌اى پرداخته شود. مسلماً بحث پیرامون این موضوع بسیار وسیع است و در این حجم نمى‌گنجد.

نویسنده مقاله: راضیه زارع

این مقاله در در شمارۀ 1 نشریه آرایه در بهار 1399، (با تغییراتی جزئی در عکس‌های به‌کاررفته) منتشر شده است.

پانویس‌ها:

[1] William Hamilton

[2] Nondeterministic Polynomial

[3] Leonard Adleman

[4] جهت مطالعه در این زمینه روش Polymerase Chain Reaction و پل الکتروفورز را جست وجو کنید.

جهت مطالعۀ بیشتر در زمینه رایانش دی‌ان‌ای مى‌توانید به منابع زیر مراجعه کنید.

Bonsor, Kevin. &quotHow DNA Computers Will Work&quot. Retrieved from computer.howstuffworks.com

Adleman, Leonard M. &quotComputing with DNA&quot, Scientific American. August, 1998.

Shouse, Ben. &quotFirst Automated DNA Computer Boots Up&quot. May, 2001.

Wang,Fei  &others. &quotImplementing digital computing with DNA-based switching circuits&quot, Nature Communications. January 2020.