Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Phylogenetic Trees03:21

Phylogenetic Trees

41.7K
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.
41.7K
Evolutionary Relationships through Genome Comparisons02:54

Evolutionary Relationships through Genome Comparisons

5.8K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
5.8K
Maxam-Gilbert Sequencing01:05

Maxam-Gilbert Sequencing

10.5K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
10.5K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Correction to: Documenting lemming population change in the Arctic: Can we detect trends?

Ambio·2019
Same author

Documenting lemming population change in the Arctic: Can we detect trends?

Ambio·2019
Same author

Climate Warming as a Possible Trigger of Keystone Mussel Population Decline in Oligotrophic Rivers at the Continental Scale.

Scientific reports·2018
Same author

Faltering lemming cycles reduce productivity and population size of a migratory Arctic goose species.

The Journal of animal ecology·2013

Related Experiment Video

Updated: May 2, 2026

A Virtual Machine Platform for Non-Computer Professionals for Using Deep Learning to Classify Biological Sequences of Metagenomic Data
09:34

A Virtual Machine Platform for Non-Computer Professionals for Using Deep Learning to Classify Biological Sequences of Metagenomic Data

Published on: September 25, 2021

3.2K

DNA-algorithm for timetable problem.

Igor Yu Popov1, Anastasiya V Vorobyova1, Irina V Blinova1

  • 1St. Petersburg National Research University of Information Technologies, Mechanics and Optics, 49 Kronverkskiy, St. Petersburg, 197101, Russia.

International Journal of Bioinformatics Research and Applications
|March 5, 2014
PubMed
Summary

DNA computing offers a novel approach to solving complex NP-complete problems, like the timetable problem. This DNA algorithm significantly reduces computational complexity from exponential to polynomial time.

Keywords:
DNA algorithmNP–complete problemsbioinformaticsfilteringmolecular computingnucleotide chainstimetablestimetabling

More Related Videos

Designing a Bio-responsive Robot from DNA Origami
13:32

Designing a Bio-responsive Robot from DNA Origami

Published on: July 8, 2013

21.7K
Design and Synthesis of a Reconfigurable DNA Accordion Rack
07:44

Design and Synthesis of a Reconfigurable DNA Accordion Rack

Published on: August 15, 2018

6.7K

Related Experiment Videos

Last Updated: May 2, 2026

A Virtual Machine Platform for Non-Computer Professionals for Using Deep Learning to Classify Biological Sequences of Metagenomic Data
09:34

A Virtual Machine Platform for Non-Computer Professionals for Using Deep Learning to Classify Biological Sequences of Metagenomic Data

Published on: September 25, 2021

3.2K
Designing a Bio-responsive Robot from DNA Origami
13:32

Designing a Bio-responsive Robot from DNA Origami

Published on: July 8, 2013

21.7K
Design and Synthesis of a Reconfigurable DNA Accordion Rack
07:44

Design and Synthesis of a Reconfigurable DNA Accordion Rack

Published on: August 15, 2018

6.7K

Area of Science:

  • Biomolecular Computing
  • Computational Complexity Theory
  • Algorithm Design

Background:

  • NP-complete problems, such as the timetable problem, pose significant computational challenges for traditional algorithms.
  • DNA computing leverages the unique properties of DNA molecules for parallel processing and massive data storage.
  • Existing methods for solving the timetable problem often struggle with scalability and efficiency.

Purpose of the Study:

  • To explore the application of DNA computing for solving NP-complete problems.
  • To develop a DNA-based algorithm for efficiently solving the timetable problem.
  • To analyze the computational complexity and feasibility of the proposed DNA algorithm.

Main Methods:

  • Representing classes, teachers, and hours as nucleotide chains.
  • Constructing a multi-set of all possible timetables using DNA molecules.
  • Implementing a filtering algorithm to eliminate timetables that violate given constraints.
  • Analyzing the efficiency and correctness of the DNA-based timetable algorithm.

Main Results:

  • Demonstrated that DNA properties can reduce the operational complexity of NP-complete problems from exponential to polynomial.
  • Successfully designed and analyzed a DNA algorithm for the timetable problem.
  • The proposed filtering procedure effectively identifies and excludes invalid timetables.
  • An example case study validated the algorithm's practical applicability.

Conclusions:

  • DNA computing presents a viable and efficient alternative for tackling NP-complete problems.
  • The developed DNA algorithm offers a significant improvement in solving the timetable problem.
  • Further research into DNA-based algorithms could revolutionize computational problem-solving.