title: DNA-algorithm for timetable problem.
abstract: Using of DNA molecules for solving of NP-complete problems is discussed. Properties of DNA allow one to reduce the number of operations from exponential to polynomial. DNA-algorithm for solving of the timetable problem is suggested. The starting point is a set of classes, teachers and hours with some limitations. It is necessary to determine whether there is a timetable satisfying all limitations. The sets of classes, teachers and hours are coded by chains of nucleotides. After preparing of the input multi-set containing all possible timetables the filtering procedure should be made. It allows to exclude all illegal timetables. The filtering algorithm is suggested. An example is described. The analysis of the algorithm is made.
authors.affiliation: St. Petersburg National Research University of Information Technologies, Mechanics and Optics, 49 Kronverkskiy, St. Petersburg, 197101, Russia.
authors.forename: Igor Yu
authors.initials: IY
authors.lastname: Popov
authors.affiliation: St. Petersburg National Research University of Information Technologies, Mechanics and Optics, 49 Kronverkskiy, St. Petersburg, 197101, Russia.
authors.forename: Anastasiya V
authors.initials: AV
authors.lastname: Vorobyova
authors.affiliation: St. Petersburg National Research University of Information Technologies, Mechanics and Optics, 49 Kronverkskiy, St. Petersburg, 197101, Russia.
authors.forename: Irina V
authors.initials: IV
authors.lastname: Blinova
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D004247:DNA / Q000737:chemistry*; D006801:Humans; D017146:Models, Organizational; D009711:Nucleotides / Q000737:chemistry; D010561:Personnel Staffing and Scheduling / Q000458:organization & administration*; D012984:Software
chemical_list: D009711:Nucleotides; D004247:DNA
keywords: DNA algorithm; NP–complete problems; bioinformatics; filtering; molecular computing; nucleotide chains; timetables; timetabling