Solving the 0/1 Knapsack Problem by a Biomolecular DNA Computer
| Autor: | M. Rezaei, Hassan Taghipour, Heydar Ali Esmaili |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Alternative methods
Mathematical problem Theoretical computer science Article Subject Computer science Biomedical Engineering Parallel algorithm Biochemistry Genetics and Molecular Biology (miscellaneous) Computer Science Applications law.invention Parallel processing (DSP implementation) lcsh:Biology (General) DNA computing law Knapsack problem Massively parallel Time complexity lcsh:QH301-705.5 lcsh:Statistics lcsh:HA1-4737 Research Article |
| Zdroj: | Advances in Bioinformatics, Vol 2013 (2013) Advances in Bioinformatics |
| ISSN: | 1687-8035 1687-8027 |
| Popis: | Solving some mathematical problems such as NP-complete problems by conventional silicon-based computers is problematic and takes so long time. DNA computing is an alternative method of computing which uses DNA molecules for computing purposes. DNA computers have massive degrees of parallel processing capability. The massive parallel processing characteristic of DNA computers is of particular interest in solving NP-complete and hard combinatorial problems. NP-complete problems such as knapsack problem and other hard combinatorial problems can be easily solved by DNA computers in a very short period of time comparing to conventional silicon-based computers. Sticker-based DNA computing is one of the methods of DNA computing. In this paper, the sticker based DNA computing was used for solving the 0/1 knapsack problem. At first, a biomolecular solution space was constructed by using appropriate DNA memory complexes. Then, by the application of a sticker-based parallel algorithm using biological operations, knapsack problem was resolved in polynomial time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text