Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem
DNA computing often makes use of hybridization, whether for vastly generating the initial candidate answers or amplification by using polymerase chain reaction (PCR). The main idea behind DNA computing approaches for solving weighted graph problems is that if the degree of hybridization can be contr...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Book Section |
| Published: |
Springer
2006
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/7188/ |
| _version_ | 1848891419502051328 |
|---|---|
| author | Ibrahim, Zuwairie Tsuboi, Yusei Ono, Osamu Khalid, Marzuki |
| author2 | Ijspeert, A. J. |
| author_facet | Ijspeert, A. J. Ibrahim, Zuwairie Tsuboi, Yusei Ono, Osamu Khalid, Marzuki |
| author_sort | Ibrahim, Zuwairie |
| building | UTeM Institutional Repository |
| collection | Online Access |
| description | DNA computing often makes use of hybridization, whether for vastly generating the initial candidate answers or amplification by using polymerase chain reaction (PCR). The main idea behind DNA computing approaches for solving weighted graph problems is that if the degree of hybridization can be controlled, then it is able to generate more double stranded DNAs (dsDNAs), which represent the answer of the problem during in vitro computation. Previously, length, concentration, and melting temperature, have been exploited for encoding of weights of a weighted graph problem. In this paper, we present a hybrid approach, which is called concentration-controlled direct-proportional length-based DNA computing (CCDPLB-DNAC), that combines two characteristics: length and concentration, for encoding and at the same time, effectively control the degree of hybridization of DNA. The encoding by length is realized whereby the cost of each path is encoded by the length of the oligonucleotides (oligos) in a proportional way. On the other hand, the hybridization control by concentration is done by varying the amount of oligos, as the input of computation, before the computation begins. The advantage is such that, after an initial pool generation and amplification, polyacrylamide gel electrophoresis (PAGE) can be performed to separate the survived dsDNAs according to their length, which directly decodes the results. The proposed approach shows significant improvement in term of materials used and scalability. The experimental results show the effectiveness of the proposed CCDPLB-DNAC for solving weighted graph problems, such as the shortest path problem. |
| first_indexed | 2025-11-15T20:57:40Z |
| format | Book Section |
| id | utm-7188 |
| institution | Universiti Teknologi Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T20:57:40Z |
| publishDate | 2006 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | utm-71882017-07-25T06:20:11Z http://eprints.utm.my/7188/ Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem Ibrahim, Zuwairie Tsuboi, Yusei Ono, Osamu Khalid, Marzuki QA75 Electronic computers. Computer science DNA computing often makes use of hybridization, whether for vastly generating the initial candidate answers or amplification by using polymerase chain reaction (PCR). The main idea behind DNA computing approaches for solving weighted graph problems is that if the degree of hybridization can be controlled, then it is able to generate more double stranded DNAs (dsDNAs), which represent the answer of the problem during in vitro computation. Previously, length, concentration, and melting temperature, have been exploited for encoding of weights of a weighted graph problem. In this paper, we present a hybrid approach, which is called concentration-controlled direct-proportional length-based DNA computing (CCDPLB-DNAC), that combines two characteristics: length and concentration, for encoding and at the same time, effectively control the degree of hybridization of DNA. The encoding by length is realized whereby the cost of each path is encoded by the length of the oligonucleotides (oligos) in a proportional way. On the other hand, the hybridization control by concentration is done by varying the amount of oligos, as the input of computation, before the computation begins. The advantage is such that, after an initial pool generation and amplification, polyacrylamide gel electrophoresis (PAGE) can be performed to separate the survived dsDNAs according to their length, which directly decodes the results. The proposed approach shows significant improvement in term of materials used and scalability. The experimental results show the effectiveness of the proposed CCDPLB-DNAC for solving weighted graph problems, such as the shortest path problem. Springer Ijspeert, A. J. 2006 Book Section PeerReviewed Ibrahim, Zuwairie and Tsuboi, Yusei and Ono, Osamu and Khalid, Marzuki (2006) Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem. In: Biologically Inspired Approaches to Advanced Information Technology. Lecture notes in computer science, 3853 . Springer , Verlag Berlin Heidelberg, pp. 206-221. ISBN 978-3-540-31253-6 https://link.springer.com/chapter/10.1007%2F11613022_18 10.1007/11613022 |
| spellingShingle | QA75 Electronic computers. Computer science Ibrahim, Zuwairie Tsuboi, Yusei Ono, Osamu Khalid, Marzuki Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem |
| title | Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem |
| title_full | Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem |
| title_fullStr | Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem |
| title_full_unstemmed | Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem |
| title_short | Hybrid concentration-controlled direct-proportional length-based DNA computing for numerical optimization of the shortest path problem |
| title_sort | hybrid concentration-controlled direct-proportional length-based dna computing for numerical optimization of the shortest path problem |
| topic | QA75 Electronic computers. Computer science |
| url | http://eprints.utm.my/7188/ http://eprints.utm.my/7188/ http://eprints.utm.my/7188/ |