Implementation of the Timetable Problem Using Self-assembly of DNA Tiles

  • Zhen Cheng College of Computer Science and Technology Zhejiang University of Technology 288 Liuhe Road, Hangzhou, P.R. China
  • Zhihua Chen Department of Control Science and Engineering Huazhong University of Science and Technology 1037 Luoyu Road, Wuhan, P.R.China
  • Yufang Huang Department of Control Science and Engineering Huazhong University of Science and Technology 1037 Luoyu Road, Wuhan, P.R.China
  • Xuncai Zhang Department of Control Science and Engineering Huazhong University of Science and Technology 1037 Luoyu Road, Wuhan, P.R.China
  • Jin Xu School of Electronics Engineering and Computer Science Peking University No.5 Yiheyuan Road Haidian District, Beijing, P.R.China

Abstract

DNA self-assembly is a promising paradigm for nanotechnology. Recently, many researches demonstrate that computation by self-assembly of DNA tiles may be scalable. In this paper, we show how the tile self-assembly process can be used for implementing the timetable problem. First the timetable problem can be converted into the graph edge coloring problem with some constraints, then we give the tile self-assembly model by constructing three small systems including nondeterministic assigning system, copy system and detection system to perform the graph edge coloring problem, thus the algorithm is proposed which can be successfully solved the timetable problem with the computation time complexity ofΘ(mn), parallely and at very low cost.

References

[1] L.M. Adleman, Molecular computation of solutions to combinatorial problems, Science, vol. 266, pp. 1021-1024, 1994.
http://dx.doi.org/10.1126/science.7973651

[2] L.Q. Pan, J. Xu, Y.C. Liu, A Surface-Based DNA Algorithm for the Minimal Vertex Problem, Progress in Natural Science, vol. 13, pp. 81-84, 2003.
http://dx.doi.org/10.1360/03jz9014

[3] L.Q. Pan, G.W. Liu, J. Xu, Solid phase based DNA solution of the coloring problem, Progress in Natural Science, vol. 14, pp. 104-107, 2004.
http://dx.doi.org/10.1080/10020070412331343781

[4] A. Carbone, N.C. Seeman, Molecular Tiling and DNA Self-assembly, Springer-Verlag Berlin Heidelberg, LNCS 2950, pp. 61-83, 2004.

[5] N.C. Seeman, DNA nanotechnology: novel DNA constructions, Annu. Rev. Biophy. Biomol. Struct., vol. 27, pp. 225-248, 1998.
http://dx.doi.org/10.1146/annurev.biophys.27.1.225

[6] C. Mao,W. Sun, N.C. Seeman, Designed two dimensional DNA Holliday junction arrays visualized by atomic force microscopy, J. Am. Chem. Soc., vol. 121, pp. 5437-5443, 1999.
http://dx.doi.org/10.1021/ja9900398

[7] E. Winfree, On the computational power of DNA annealing and ligation, DNA Based Computers, pp. 199-221, 1996.

[8] T. Eng. Linear self-assembly with hairpins generates the equivalent of linear context-free grammars. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penn.,1997.

[9] R. Barish, P. Rothemund, E. Winfree, Two computational primitives for algorithmic self-assembly: Copying and counting, Nano Letters, vol. 12, pp. 2586-2592, 2005.
http://dx.doi.org/10.1021/nl052038l

[10] Pablo Moisset de Espane′s, Ashish Goel, Toward minimum size self-assembled counters, Springer Science Business Media B.V., 2008.

[11] P. Rothemund, N. Papadakis, E. Winfree, Algorithmic self-assembly of DNA Sierpinski triangles, PLoS Biology, vol. 12, pp. 2041-2053, 2004.
http://dx.doi.org/10.1371/journal.pbio.0020424

[12] M. Cook, P. Rothemund, E. Winfree, Self assembled circuit patterns, DNA, pp. 91-107, 2004.
http://dx.doi.org/10.1007/978-3-540-24628-2_11

[13] C. Mao, T.H. LaBean, J.H. Reif, Logical computation using algorithmic self-assembly of DNA triple-crossover molecules, Nature, vol. 407, pp. 493-496, 2000.
http://dx.doi.org/10.1038/35035038

[14] Y. Brun, Arithmetic computation in the tile assembly model: Addition and multiplication, Theoretical Computer Science, vol. 378, pp. 17-31, 2006.
http://dx.doi.org/10.1016/j.tcs.2006.10.025

[15] G.L. Michail, T.H. LaBean, 2D DNA self-assembly for satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. vol. 44, pp. 139-152, 1999.

[16] Y. Brun, Nondeterministic polynomial time factoring in the tile assembly model, Theoretical Computer Science, vol. 395, pp. 3-23, 2008.
http://dx.doi.org/10.1016/j.tcs.2007.07.051

[17] Y. Brun, Solving NP-complete problems in the tile assembly model, Theoretical Computer Science, vol. 395, pp. 31-36, 2008.
http://dx.doi.org/10.1016/j.tcs.2007.07.052

[18] A. Gehani, T.H. LaBean, J.H. Reif, In DNA Based Computers: Proceedings of a DIMACS Workshop, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999.

[19] D. Werra, An introduction to timetabling. European Journal of Operations Research, vol. 19, pp.151-162, 1985.
http://dx.doi.org/10.1016/0377-2217(85)90167-5

[20] D. Abramson, Constructing school timetables using simulated annealing: Sequential and parallel algorithms. Management Science, vol. 37, pp. 98-113, 1991.
http://dx.doi.org/10.1287/mnsc.37.1.98

[21] A. Colorni, M. Dorigo, V. Maniezzo, Genetic algorithms and highly constrained problems: the time-table case. In: H.P.Schwefel and R.Manner(eds). Parallel Problem Solving from Nature. Proceedings of 1st Workshop, PPSN 1, LNCS 496, Dortmund, Germany, 1-3 October. Springer-Verlag, pp. 55-59, 1991.
http://dx.doi.org/10.1007/bfb0029731

[22] L. Gaspero, A. Schaerf, Tabu search techniques for examination timetabling. In Proceedings of the 3rd International Conference on Practice and Theory of Automated Timetabling (PATAT 2000), Springer-Verlag, LNCS 2079, pp. 104-117, 2001.
http://dx.doi.org/10.1007/3-540-44629-x_7

[23] H. Wang, Proving theorems by pattern recognition, I. Bell System Technical Journal, vol. 40, pp. 1-42, 1961.
http://dx.doi.org/10.1002/j.1538-7305.1961.tb03975.x

[24] E. Winfree, Algorithmic self-assembly of DNA, Ph.D.Thesis, Caltech, Pasadena, CA, June 1998.

[25] P. Rothemund, E. Winfree, The program-size complexity of self-assembled squares, ACM Symposium on Theory of Computing (STOC), pp. 459-468, 2001.

[26] Mihaela Oprea. MAS_UPUCT: A Multi-Agent System for University Course Timetable Scheduling. International Journal of Computers, Communications & Control, Vol. II, pp. 94-102, 2007.

[27] Zhipeng L., Jin-Kao Hao. Adaptive Tabu search for course timetabling. European Journal of Operational Research, doi:10.1016/j.ejor.2008.12.007, 2009.
http://dx.doi.org/10.1016/j.ejor.2008.12.007

[28] A.R. Mushi, Mathematical programming for mulations for the examinations timetable problem: the case of the university of DAR ES SALAAM. African Journal of Science and Technology (AJST) Science and Engineering Series, Vol. 5, pp. 34-40, 2004.
Published
2010-11-01
How to Cite
CHENG, Zhen et al. Implementation of the Timetable Problem Using Self-assembly of DNA Tiles. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 5, n. 4, p. 490-505, nov. 2010. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2507>. Date accessed: 06 aug. 2020. doi: https://doi.org/10.15837/ijccc.2010.4.2507.

Keywords

timetable, self-assembly, graph edge coloring, DNA tiles