Research Article
DNA Sequence Assembly using Particle Swarm Optimization
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 28 - Issue 10 |
| Published: August 2011 |
| Authors: Ravi Shankar Verma, Vikas Singh, Sanjay Kumar |
10.5120/3425-4777
|
Ravi Shankar Verma, Vikas Singh, Sanjay Kumar . DNA Sequence Assembly using Particle Swarm Optimization. International Journal of Computer Applications. 28, 10 (August 2011), 33-38. DOI=10.5120/3425-4777
@article{ 10.5120/3425-4777,
author = { Ravi Shankar Verma,Vikas Singh,Sanjay Kumar },
title = { DNA Sequence Assembly using Particle Swarm Optimization },
journal = { International Journal of Computer Applications },
year = { 2011 },
volume = { 28 },
number = { 10 },
pages = { 33-38 },
doi = { 10.5120/3425-4777 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2011
%A Ravi Shankar Verma
%A Vikas Singh
%A Sanjay Kumar
%T DNA Sequence Assembly using Particle Swarm Optimization%T
%J International Journal of Computer Applications
%V 28
%N 10
%P 33-38
%R 10.5120/3425-4777
%I Foundation of Computer Science (FCS), NY, USA
Abstract
DNA sequence assembly problem is a very complex problem of computational biology. DNA sequence assembly is a NP hard problem there is no single solution available for this kind of problems. DNA sequence assembly refers to aligning and merging fragments of a much longer DNA sequence in order to reconstruct the original sequence. In this paper a solution is proposed for DNA sequence assembly problem using Particle Swarm Optimization (PSO) with Shortest Position Value (SPV) rule. DNA sequence assembly problem is a discrete optimization problem, so there is need of discrete optimization algorithm to solve it. In this paper continuous version of PSO is used with SPV rule to solve the DNA sequence assembly problem. SPV rule transforms continuous version of PSO to discrete version. Proposed methodology is named as DSAPSO. To check the efficiency of proposed methodology the results of DSAPSO is compared with the results of genetic algorithm (GA).
References
- Kennedy, J. and Eberhart, R. “Particle swarm optimization”, Neural Networks, 1995. Proceedings. IEEE International Conference on, Vol. 4, pp. 1942—1948, 1995.
- Shi, Y. and Eberhart, R. “A modified particle swarm optimizer”, Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence. The 1998 IEEE International Conference on, pp. 69—73, 1998.
- Eberhart, R.C. and Shi, Y. “Comparing inertia weights and constriction factors in particle swarm optimization”, Evolutionary Computation, 2000. Proceedings of the 2000 Congress on, Vol. 1, pp. 80—84, 2000.
- Burks, C. “DNA sequence assembly”, Engineering in Medicine and Biology Magazine, IEEE, Vol. 13, pp. 771—773, 1994.
- P. Green. Phrap. http://www.phrap.org/.
- G.G. Sutton, O. White, M.D. Adams, and A.R. Kerlavage. “TIGR Assembler: A new tool for assembling large shotgun sequencing projects”, Genome Science & Tech., Vol. 1, pp. 9–19, 1995.
- T. Chen and S. Skiena. “Trie-based data structures for sequence assembly”, Combinatorial Pattern Matching, pp. 206–223, 1998.
- X. Huang and A. Madan. “CAP3: A DNA sequence assembly program”, Genome Research, Vol. 9, pp. 868–877, 1999.
- E.W. Myers. “Towards simplifying and accurately formulating fragment assembly”, Journal of Computational Biology, Vol. 2, pp. 275–290, 2000.
- P.A. Pevzner. “Computational molecular biology: An algorithmic approach”, The MIT Press, Vol. 1, 2000.
- Allex, C.F. and Baldwin, S.F. and Shavlik, J.W. and Blattner, F.R. “Improving the quality of automatic DNA sequence assembly using fluorescent trace-data classifications”, Proceedings, Fourth International Conference on Intelligent Systems for Molecular Biology, pp. 3—14, 1996.
- Wilks, C. and Khuri, S. “A fast shotgun assembly heuristic”, Computational Systems Bioinformatics Conference, Workshops and Poster Abstracts, IEEE, pp. 122—123, 2005.
- Parsons, R. and Forrest, S. and Burks, C. “Genetic algorithms for DNA sequence assembly”, Proceedings of the First International Conference on Intelligent Systems for Molecular Biology (ISMB-93), pp. 310—318, 1993.
- Parsons, R.J. and Forrest, S. and Burks, C. “Genetic algorithms, operators, and DNA fragment assembly”, Machine Learning, Vol. 21, pp. 11—33, 1995.
- Parsons, R.J. and Johnson, M.E. “DNA sequence assembly and genetic algorithms--new results and puzzling insights”, Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology (ISMB-95), pp. 277—284, 1995.
- Kim, K. and Mohan, CK “Parallel hierarchical adaptive genetic algorithm for fragment assembly”, Evolutionary Computation, 2003. CEC'03. The 2003 Congress on, Vol. 1, pp. 600—607, 2003.
- Fang, S.C. and Wang, Y. and Zhong, J. “A Genetic Algorithm Approach to Solving DNA Fragment Assembly Problem”, Journal of Computational and Theoretical Nanoscience, Vol. 2, pp. 499—505, 2005.
- Kikuchi, S. and Chakraborty, G. “Heuristically tuned GA to solve genome fragment assembly problem”, Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, pp. 1491—1498, 2006.
- Luque, G. and Alba, E. “Metaheuristics for the DNA fragment assembly problem”, International Journal of Computational Intelligence Research, Vol. 1, pp. 98—108, 2005.
- Meksangsouy, P. and Chaiyaratana, N. “DNA fragment assembly using an ant colony system algorithm”, Evolutionary Computation, 2003. CEC'03. The 2003 Congress on, Vol. 3, pp. 1756—1763, 2003.
- Zhao, Y. and Ma, P. and Lan, J. and Liang, C. and Ji, G. “An Improved Ant Colony Algorithm for DNA Sequence Alignment”, 2008 International Symposium on Information Science and Engineering, pp. 683—688, 2008.
- Nucleotide, NCBI- http://www.ncbi.nlm.nih.gov/nuccore.
Index Terms
Keywords