Featured Research

from universities, journals, and other organizations

DNA fix for school timetables

Date:
March 12, 2014
Source:
Inderscience
Summary:
Scientists in Russia plan to use DNA -- our genetic material -- to help them solve one of the perennial "back to school" problems faced by school administrators the world over: how to match up students, with classes and available teachers. DNA's ability to store information can be used to encode the timetabling problem and then a solution read out using enzymes, according to the scientists.

Scientists in Russia plan to use DNA -- our genetic material -- to help them solve one of the perennial "back to school" problems faced by school administrators the world over: how to match up students, with classes and available teachers. Writing in the International Journal of Bioinformatics Research and Applications, the team explains how DNA's ability to store information can be used to encode the timetabling problem and then a solution read out using enzymes.

Related Articles


Igor Popov, Anastasiya Vorobyova and Irina Blinova of the St. Petersburg National Research University of Information Technologies, Mechanics and Optics, explain how timetabling is a so-called NP-complete problem. Such problems are complex and have many possible solutions, some of which are near-perfect others not so much. The classic school timetabling problem involves accommodating a number of students in a finite number of classrooms for appropriate lessons with a limited number of teachers offering their chosen subjects. In general, school administrators at large schools offering many diverse courses will expend a large amount of energy attempting to fit all students and teachers into appropriate timetable slots during the school week. Issues come to light when a given subject is oversubscribed or when a subject offered has very few takers.

The team explains that timetabling essentially consists of a set of resources (teachers and classrooms), a set of activities (lessons, study periods, physical education), and a set of dependencies between the activities (is the Latin teacher available on Monday mornings? Are students interested in studying Latin available or are they likely to be in their Greek lesson on Monday mornings?). Time is divided into slots of the same duration and these can be hard or soft: a hard constraint indicates that the slot is forbidden for an activity (absolutely no Latin lessons last thing on a Friday as the teacher has to catch an early train back to Rome), a soft constraint indicates that the slot is not preferred (the Latin teacher is always available on Monday mornings but can take classes on Tuesday if students cannot make Monday morning). Every activity and every resource may have assigned a set of time preferences, which indicate forbidden and not preferred time slots.

All possible timetables can be encoded in a large number of synthetic strands of DNA, the team then explains. They then apply the various resources and constraints to a second strand of DNA. When this is mixed with in the test-tube with the encoded DNA strands it will match up with its complementary strand, which can then be filtered from the brew. An enzymatic DNA reading system can then identify the solution plucked from the mixture and reveal the optimal timetable.

Finding a unique, fully working solution to the timetabling problem usually involves exponential growth as student numbers, courses offered and teaching resources increase. The application of a DNA algorithm to this problem, which could also be applied to other logistics and scheduling problems, reduces this exponential problem (due to massive parallelism) to a polynomial one. "At present, the result is purely theoretical," says Popov. "Its implementation will be an interesting future problem."


Story Source:

The above story is based on materials provided by Inderscience. Note: Materials may be edited for content and length.


Journal Reference:

  1. Igor Yu. Popov, Anastasiya V. Vorobyova, Irina V. Blinova. DNA-algorithm for timetable problem. International Journal of Bioinformatics Research and Applications, 2014; 10 (2): 145 DOI: 10.1504/IJBRA.2014.059520

Cite This Page:

Inderscience. "DNA fix for school timetables." ScienceDaily. ScienceDaily, 12 March 2014. <www.sciencedaily.com/releases/2014/03/140312082400.htm>.
Inderscience. (2014, March 12). DNA fix for school timetables. ScienceDaily. Retrieved April 19, 2015 from www.sciencedaily.com/releases/2014/03/140312082400.htm
Inderscience. "DNA fix for school timetables." ScienceDaily. www.sciencedaily.com/releases/2014/03/140312082400.htm (accessed April 19, 2015).

Share This


More From ScienceDaily



More Science & Society News

Sunday, April 19, 2015

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

L.A. Water Cops Remind Residents of Water Conservation

L.A. Water Cops Remind Residents of Water Conservation

Reuters - US Online Video (Apr. 18, 2015) "Water cops" in Los Angeles remind the public about water conservation methods amid California&apos;s prolonged drought. Julie Noce reports. Video provided by Reuters
Powered by NewsLook.com
Dr. Oz Under Fire For 'Quack Treatments' Yet Again

Dr. Oz Under Fire For 'Quack Treatments' Yet Again

Newsy (Apr. 17, 2015) Ten doctors signed a letter urging Columbia University to drop Dr. Oz as vice chair of its department of surgery, saying he plugs "quack" treatments. Video provided by Newsy
Powered by NewsLook.com
WikiLeaks Refuses To Let Sony Hack Die, Posts Database

WikiLeaks Refuses To Let Sony Hack Die, Posts Database

Newsy (Apr. 17, 2015) WikiLeaks&apos; Julian Assange says the hacked emails and documents "belong in the public domain." Video provided by Newsy
Powered by NewsLook.com
Cybercrime Could Cost $400 Bln

Cybercrime Could Cost $400 Bln

Reuters - Business Video Online (Apr. 16, 2015) Representatives from around 160 countries gather at the Hague to discuss cyber space and cyber security, including the dilemmas and challenges regarding the evolution of the internet. Ciara Lee reports. Video provided by Reuters
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:

Strange & Offbeat Stories


Science & Society

Business & Industry

Education & Learning

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins