MDABC: Motif Discovery Using Artificial Bee Colony Algorithm

MDABC: Motif Discovery Using Artificial Bee Colony Algorithm

Vikas Singh (ABV-Indian Institute of Information Technology and Management Gwalior, Gwalior, India), Deepak Singh (Raipur Institute of Technology, Raipur, India), Ritu Tiwari (Department of Information and Communication Technology, ABV-Indian Institute of Information Technology and Management Gwalior, Gwalior, India) and Anupam Shukla (Department of Information and Communication Technology, ABV-Indian Institute of Information Technology and Management Gwalior, Gwalior, India)
Copyright: © 2012 |Pages: 18
DOI: 10.4018/jitr.2012100103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Motif discovery is one of the most popular problems in molecular biology. There are many solutions provided by researchers. In this paper we have adopted the features of the Artificial beecolony algorithm (ABC) and designed a sequential algorithm to solve motif problem and named it MDABC. Artificial bee colony algorithm is a population based heuristic search technique used for optimization problem. We have performed experiments with the nucleotide sequences of homo sapiens (human) and mouse viz. CDRT4, MACF1, Zfa, TNFRSF19 and TICAM2. The ABC algorithm applied to the CDRT4, MACF1, Zfa, TNFRSF19 and TICAM2 DNA sequence for determining the motif of length 10, 20 and 30 using the maximum number of cycle (MCN) or the maximum number of generation is equal to 250, 500 and 1000. Our result shows a promising superior performance of the algorithm. As we will see, our results surpass the results obtained by other approaches proposed in the literature.
Article Preview

Introduction

The current challenge in the field of biology is the enormous amount of existing data. This data is complex and unformatted. Also this data is doubled in every two years. The bioinformatics is the interdisciplinary research area of biology & computer science. It uses the computer science methods, models and sophisticated algorithms to solve the biological problems that are related to huge data analysis, gene annotation, pattern reorganization and many more.

The one of the most common problem in biology is motif discovery. In motif discovery, we have to analyze the DNA sequence and find the transcription binding site. Motifs are usually short sequence of nucleotides and it is hard to discover. Motif discovery is a NP Complete problem because we cannot expect the pattern to be exact matching copies owing to biological mutations this is due to large amount of statistical noise (one regulatory region contains from several hundred to several thousand nucleotides) and it is also not known that whether motif is present in a sequence or not. There are different types of motifs in the literature namely: Sequential Motifs, Gapped motifs, Structured Motifs, Planted Motifs and Network Motifs. A number of methods, algorithms and tools have been developed in the recent years to solve these problems. The complete survey of DNA motif finding algorithms, methods and different approaches are presented in (Modan, Das, & Dai, 2007). All these methods suffered from the problem of local optima. Many evolutionary algorithms eliminate the effect of local optima; one of them is Genetic algorithm which is widely used algorithm for motif discovery problem. Che et al. (2005) developed an approach that can be used to predict binding site motifs using a genetic algorithm. Congdon et al. (2005) proposed a GAMI, a Genetic Algorithms approach to Motif Inference. Kaya (2007) proposed an efficient method using multi-objective genetic algorithm (MOGAMOD) to discover optimal motifs in sequential data. Though GA reduces the local optima effect but it has expensive operators which takes time for computation. Motif discovery problem is also solved by Particle swarm optimization one of the optimization algorithm. Hardin and Rouchka (2005) proposed a hybrid motif discovery approach based upon a combination of particle swarm optimization (PSO) and the expectation-maximization (EM) algorithm. They used PSO to generate a seed for the EM algorithm. This method still suffered with local optima. Zhou et al. (2005) proposed a novel algorithm IPSO-GA by integrating an improved particle swarm optimization with genetic algorithm to search sequence motifs from co expressed genes regulated by the NF-kb transcription factor. Reddy et al. (2010) have adopted the features of the PSO to solve the Planted Motif Finding Problem and have designed a sequential algorithm. Lei, C. and Ruan, J. (2009) used a word dissimilarity graph to remap the neighborhood structure of the solution space of DNA motifs, and propose a modification of the naive PSO algorithm to accommodate discrete variables.

In this paper we propose an alternative heuristic never used in this problem. We apply Artificial Bee Colony Optimization (ABC) algorithm to discover quality motifs. Artificial Bee Colony is a new optimization technique comes under swarm intelligence and very effective to solve optimization problems. ABC is inspired by the working principles of natural bees. ABC algorithm uses both local and global search to find out the solution or global optimum. Many problems have been solved using ABC algorithm. The Artificial Bee Colony can solve Constrained Optimization Problem. Engineering design, structural optimization, economics, VLSI design, allocation and location problems are just a few of the scientific fields in which Constrained Optimization problems are frequently met (Karaboga & Basturk, 2007; Karaboga & Basturk, 2007). This novel algorithm and the meaning of these objectives will be described in the sections concerned. To demonstrate the effectiveness and efficiency of our methodology we performed experiment on five real data sets of DNA sequences.

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