Implementation of the Timetable Problem Using Self-assembly of DNA Tiles
Keywords:
timetable, self-assembly, graph edge coloring, DNA tilesAbstract
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
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
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
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
A. Carbone, N.C. Seeman, Molecular Tiling and DNA Self-assembly, Springer-Verlag Berlin Heidelberg, LNCS 2950, pp. 61-83, 2004.
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
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
E. Winfree, On the computational power of DNA annealing and ligation, DNA Based Computers, pp. 199-221, 1996.
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.
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
Pablo Moisset de Espane′s, Ashish Goel, Toward minimum size self-assembled counters, Springer Science Business Media B.V., 2008.
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
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
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
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
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.
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
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
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.
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
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
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
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
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
E. Winfree, Algorithmic self-assembly of DNA, Ph.D.Thesis, Caltech, Pasadena, CA, June 1998.
P. Rothemund, E. Winfree, The program-size complexity of self-assembled squares, ACM Symposium on Theory of Computing (STOC), pp. 459-468, 2001.
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.
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
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
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
