A Molecular Solution to the Three-Partition Problem

A Molecular Solution to the Three-Partition Problem

Maryam S. Nuser (Computer Information Systems Department, Yarmouk University, Irbid, Jordan)
Copyright: © 2012 |Pages: 16
DOI: 10.4018/jitr.2012100102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Given a set of numbers, the three-partition problem is to divide them into disjoint triplets that all have the same sum. The problem is NP-complete. This paper presents an algorithm to solve this problem using the biomolecular computing approach. The algorithm uses a distinctive encoding technique that depends on the numbers values which omits the need to an adder to find the sum. The algorithm is explained and an analysis of its complexity in terms of time, the number of strands, number of tubes, and the longest library strand used is presented. A simulation of the algorithm is implemented and tested. This algorithm further proves the ability of molecular computing in solving hard problems.
Article Preview

Introduction

DNA, or deoxyribonucleic acid, is the material that carries information across generations. Rather than storing information in binary form as in digital computers, the information in DNA is stored as a code made up of four chemical bases: adenine (A), guanine (G), cytosine (C), and thymine (T). DNA bases pair up with each other to form units that are called base pairs such that A binds with T and C binds with G. This is known as Watson-Crick complementarity.

Each DNA base (deoxyribonucleotide) consists of three components: a sugar, a phosphate group, and a nitrogenous base. A DNA strand has two different ends that determine its polarity: the 3’ end, and the 5’ end.

A DNA sequence (strand) of length n consists of n consecutive letters from the set {A, G, C, T}, which is similar in computer science to a string consisting of a combination of four different symbols A G C T.

Thousands of biological databases that store DNA sequences exist and some of the well known databases are the Genbank that has a collection of all publicly available DNA sequences (http://www.ncbi.nlm.nih.gov/RefSeq/). Biological databases should provide biologists with central and uniform access to their data. Several methods exist to deal with providing users with accurate data efficiently regardless of the heterogeneity of database (Singh, 2003; Wang et. al., 2009). The specificities of nanotechnology data and applications suggest implementing an ad-hoc tool that allows updating information frequently, so that not only the latest versions of the documents are always available, but also the raw experimental data are shared in a protected environment (Giacomini et al., 2009). These huge data are critical for both biologists, to understand how natural systems work, and other scientists to use these data to solve other computational problems.

Molecular computing, also known as DNA computing or natural computing, is a new approach to parallel computation where computing takes place in test tubes; it uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computers. Using this approach, several NP-complete problems were solved with a polynomial number of steps (Adleman, 1994; Brun, 2008; Chang et al., 2004; Chang, 2007). The theory behind the solution is based on representing problem instances with DNA sequences. Now, you can order DNA sequences and receive them within few days. After receiving these sequences, several molecular operations are applied in a specific order on these sequences. The resulting DNA sequences (if any) usually specify the problem’s correct solution.

DNA computing has been applied to different problems that range from very simple computations such as adding two numbers (Wasiewicz et al., 2000; Gupta et al., 1997) to very complex problems such as intractable problems (Tanaka et al., 2005). Although simple computations took much more time using DNAC than silicon-based computers, they showed the ability of DNA computers to mimic traditional computers.

Moreover, various fields of study used DNA computation. This includes computer science (Kim et al., 2008), mathematics (Shi & Chu, 2010), Engineering (Nuser, 2010) … and others. The main benefit of using DNAC in these fields is that always all possible solutions are created and processed simultaneously offering a huge parallelism that solves problems efficiently.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2017)
Volume 9: 4 Issues (2016)
Volume 8: 4 Issues (2015)
Volume 7: 4 Issues (2014)
Volume 6: 4 Issues (2013)
Volume 5: 4 Issues (2012)
Volume 4: 4 Issues (2011)
Volume 3: 4 Issues (2010)
Volume 2: 4 Issues (2009)
Volume 1: 4 Issues (2008)
View Complete Journal Contents Listing