بخشی از مقاله
چکیده
امروزه محاسبات مولکولی به خاطر تواناییهای بالایی که در حل مسائل غیر چندجمله ای - زمانی دارد، بسیار مورد توجه قرار گرفته است. دسته خاصی از مسائل کوله پشتی، مسائل کوله پشتی محدود نامیده می شوند که یکی از مسائل محاسباتی سخت است و در این مقاله با استفاده از ویژگی های محاسبات DN A مانند قابلیت محاسبات موازی بالا و قدرت ذخیره سازی انبوه اطلاعات ، به حل مسئله کوله پشتی محدود براساس محاسبات DNA می پردازیم.
١ مقدمه
در انتهای دهه ٠۵ یک فیزیکدان به نام ر یچارد فینمن برای نخستین بار ایده استفاده از سلولهای زنده و مجموعه های پیچیده مولکولی را مطرح کرد. اولین مقاله در این موضوع در نوامبر ۴١٩٩ توسط لئونارد آدلمان ارائه شد که در آن یک روش برای حل مسئله مسیر هامیلتونی ارائه و به طور آزمایشگاهی پیاده سازی شد و به دلیل ویژگی های مهم محاسباتی DNA، حوزه تحقیقاتی جدیدی را پیش رو قرار داده است. در این محاسبات ابتدا با رشته های DNA کد می شود سپس الگوریتمی برای پیدا کردن جواب ارائه می شود. در این مقاله به حل مسئله کوله پشتی محدود بااستفاده از الگوریتم های DNA می پردازیم.
٢ مبانیDNA و عملگرها
مولکول DNA تک رشته ای از چند نوکلئوتید و هر نوکلئوتید از سه بخش اصلی فسفات، قند و یکی از چهار باز آلی آدنین A، تیمین T، گوانین G و سیتوزین C تشکیل شده است. DNA دو رشته ای متشکل از دو تک رشته می باشد که مکمل یکدیگر هستند، بدین صورت که باز G از یک رشته با باز c از رشته دیگرو باز A با باز T از رشته دیگر بهم متصل می شوند. مکمل هر رشته را مکمل واتسون-کریک می نامند.
