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

Zhen Cheng, Zhihua Chen, Yufang Huang, Xuncai Zhang, Jin Xu

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.

Keywords


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

Full Text:

PDF

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.




DOI: https://doi.org/10.15837/ijccc.2010.4.2507



Copyright (c) 2017 Zhen Cheng, Zhihua Chen, Yufang Huang, Xuncai Zhang, Jin Xu

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2);

SCImago Journal & Country Rank

Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.