کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
395232 | 665937 | 2010 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A molecular solution to the hitting-set problem in DNA-based supercomputing
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Assume that there exists a collection C of subsets of a finite set S, and a positive integer K ⩽ â£Sâ£, and we need to know whether there is a subset Sâ²Â â S with â£Sâ²â£Â ⩽ K such that Sâ² contains at least one element of each subset in C. In other words, Sâ² is the subset that intersects every subset in C and is called the hitting-set. In this paper, a DNA-based algorithm is proposed to solve the small hitting-set problem. A small hitting-set is a hitting-set with the smallest K value, i.e., the hitting-set with the smallest number of elements. Furthermore, another algorithm is introduced to find the number of ones from 2n combinations and minimum numbers of ones represents the small hitting-set since K is expected to be as small as possible. The complexity of the proposed DNA-based algorithm is discussed, in terms of time complexity, volume complexity, numbers of test tube used and the longest library strand in solution space. Finally, the simulated experiment is applied to verify the correctness of our proposed DNA-based algorithm, in order to solve the well-known hitting-set problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 180, Issue 6, 15 March 2010, Pages 1010-1019
Journal: Information Sciences - Volume 180, Issue 6, 15 March 2010, Pages 1010-1019
نویسندگان
Nung-Yue Shi, Chih-Ping Chu,