توصيفگر ها :
كدهاي DNA , ذخيره سازي اطلاعات DNA- مبنا , كدهاي تصحيح كننده خطا , تكثير متوالي , تكثير پاليندروميك , محاسبات DNA , كدهاي وارون پذير
چكيده فارسي :
DNA به علت چگالي بالا در ذخيره اطلاعات، ماندگاري طولاني و توان بالاي واكنش‌هاي موازي مورد توجه محققان براي كاربرد در زمينه‌هاي مختلف قرار گرفته است. ذخيره‌سازي اطلاعات -DNAمبنا و محاسبات DNA دو رده مهم از كاربردهاي DNA هستند. براي كنترل خطا در ذخيره‌سازي اطلاعات -DNAمبنا و جلوگيري از بروز خطا در محاسبات DNA از نظريه كدگذاري استفاده مي‌شود.
فرآيند ذخيره‌سازي اطلاعات در DNA به اين‌صورت است كه اطلاعات كدگذاري شده توسط فرآيند سنتز به رشته‌هاي DNA تبديل مي‌شوند. رشته‌هاي سنتز شده را مي‌توان در يك شرايط مناسب نگهداري كرد يا به‌وسيله ابزارهاي زيست‌فناوري به يك موجود زنده تزريق كرد. خطاهاي تكثير متوالي و تكثير پاليندروميك دو رده از خطاهايي هستند كه ممكن است در ذخيره‌سازي اطلاعات در DNA يك موجود زنده رخ دهند. در اين رساله براي چهار رده از خطاهايي كد ساخته مي‌شود كه تاكنون كدي براي آن‌ها ساخته نشده است. اين رده‌ها عبارتند از:
1- خطاهاي تكثير متوالي به‌طول حداكثر k كه 3< k<10 ،
2- خطاهاي تكثير پاليندروميك به‌طول ثابت k،
3- تركيبي از خطاهاي تكثير پاليندروميك و تكثير متوالي به‌طول ثابت k،
4- تركيبي از خطاهاي تكثير متوالي و تكثير پاليندروميك به‌طول حداكثر k كه k=2,3.
حل مساله -<=kدرهم‌تنيدگي براي ساخت كد جهت تصحيح خطاهاي تكثير متوالي به‌طول حداكثر k با اندازه بيشتر ضروري است. در اين رساله اين مساله براي رده‌اي از كلمات در حالت k=4,5 حل مي‌شود.
حجم بالاي واكنش‌هاي موازي بين رشته‌هاي DNA و توان ذخيره نمونه‌هاي مساله در رشته‌هاي DNA باعث شكل گرفتن روشي محاسباتي با استفاده از رشته‌هاي DNA شده است. يكي از روش‌هاي جلوگيري از بروز خطا در اين فرآيند، طراحي كد براي رشته‌هاي DNA است. كدهاي خطي وارون‌پذير يك رده مهم از كدهايي است كه در فرآيند طراحي كد مورد استفاده قرار مي‌گيرند. در اين رساله معيارهايي براي وارون‌پذيري و مزدوج-وارون‌پذيري كدهاي شبه‌دوري ارائه مي‌شود. سپس شرايطي براي خود-دوگان بودن و دوگان تكميلي داشتن كدهاي شبه‌دوري وارون‌پذير بيان مي‌شود. در انتها از كدهاي شبه‌دوري وارون‌پذير جهت ساخت كدهاي DNA با تعداد كدكلمه بيشتر استفاده مي‌شود.
چكيده انگليسي :
DNA has been shown to have a storage density in magnitude of petabyte per gram. In addition, it can withstand a board range of temperatures (-800^o to +800^o}) and can exist for a long time. DNA strands can hybridize quickly. These properties of DNA along with recent progress in synthetic biology, attract a lot of attentions for DNA applications. In this thesis, we construct codes for two branches of DNA applications; DNA based data storage and DNA computing.
Tandem duplication (TD), palindromic duplication (PD), end duplication and interspersed duplication errors can occur when DNA of a living organism is used to store data. In this thesis, codes are obtained to correct the following four classes of errors
1- TD errors of length at most s, 3< s<10,
2- PD errors of length k,
3- a combination of PD and TD errors of length k, and
4- a combination of PD and TD errors of length at most k where k=2,3.
Determining <=k-confusability plays a key role in constructing optimal <= k-TD codes.
Chee et al. provided an algorithm for checking <=3-confusability,
but determining <= k-confusability for k>3 remains an open problem.
This problem is solved here for a class of words for k=4,5 which leads to an approach for checking <= k-confusability in general.
DNA computing is an area of natural computing, which uses DNA strings and biochemical processes to solve hard problems. Since these processes are not complete, it is possible that some errors occur. For preventing errors in DNA computing, researchers considered designing DNA codes. A code with DNA alphabet, {A, T, C, G}, is called a DNA code. For designing these codes some constraints are considered. One of the important tools for designing codes is the usage of reversible codes over the Galois field with four elements. Optimal reversible codes are desirable for these targets. Quasi-cyclic (QC) codes are important class of codes, containing many optimal codes. In this thesis, reversible quasi-cyclic codes are used for code construction.
