CFP last date
20 December 2024
Reseach Article

DNA Multiple Sequence Alignment by a Hidden Markov Model and Fuzzy Levenshtein Distance based Genetic Algorithm

by Tamal Chakrabarti, Sourav Saha, Devadatta Sinha
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 73 - Number 16
Year of Publication: 2013
Authors: Tamal Chakrabarti, Sourav Saha, Devadatta Sinha
10.5120/12826-0206

Tamal Chakrabarti, Sourav Saha, Devadatta Sinha . DNA Multiple Sequence Alignment by a Hidden Markov Model and Fuzzy Levenshtein Distance based Genetic Algorithm. International Journal of Computer Applications. 73, 16 ( July 2013), 26-30. DOI=10.5120/12826-0206

@article{ 10.5120/12826-0206,
author = { Tamal Chakrabarti, Sourav Saha, Devadatta Sinha },
title = { DNA Multiple Sequence Alignment by a Hidden Markov Model and Fuzzy Levenshtein Distance based Genetic Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { July 2013 },
volume = { 73 },
number = { 16 },
month = { July },
year = { 2013 },
issn = { 0975-8887 },
pages = { 26-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume73/number16/12826-0206/ },
doi = { 10.5120/12826-0206 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:40:16.911336+05:30
%A Tamal Chakrabarti
%A Sourav Saha
%A Devadatta Sinha
%T DNA Multiple Sequence Alignment by a Hidden Markov Model and Fuzzy Levenshtein Distance based Genetic Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 73
%N 16
%P 26-30
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In the last decade, biologists have experienced a fundamental shift away from the traditional empirical research to large-scale, computer-based research. Today bio-informatics is a systematic and predictive discipline which encompasses genomics, informatics, automation, and miniaturization. This fusion of biology and information science is expected to continue and expand for the foreseeable future. DNA Sequence alignment is a commonly observed problem in bio-informatics for establishing similarity and evolutionary relationship between DNA sequences. This paper has presented a DNA multiple sequence alignment technique by a genetic algorithm based on Hidden Markov Model and Fuzzy Levenshtein Distance.

References
  1. Baum, L. and Petrie, T. (1966). Statistical inference for probabilistic functions of finite state Markov chains. The Annals of Mathematical Statistics, 37(6):1554-1563.
  2. Braun, J. V. and Muller, H. -G. (1998). Statistical methods for dna sequence segmentation. Statistical Science, 13(2):142-162.
  3. Chih-Chin Lai; Chih-Hung Wu; Cheng-Chen Ho; "Using Genetic Algorithm to Solve Multiple Sequence Alignment Problem ", International Journal of Software Engineering and Knowledge Engineering Vol. 19, No. 6 (2009)
  4. Churchill, G. (1989). Stochastic models for heterogeneous dna sequences. Bulletin of Mathematical Biology, 51:79-94. 10. 1007/BF02458837.
  5. Churchill, G. (1992). Hidden markov chains and the analysis of genome structure. Computers and Chemistry, 16(2):107-115.
  6. Dong, S. and Searls, D. B. (1994) Genomics 23, 540–551.
  7. Dubin, R. E. S. , Krogh, A. , and Mitchison, G. (1998). Biological Sequence Analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press, Cambridge.
  8. Eddy, S. R. (1995); Multiple alignment using hidden Markov models. In Rawlings, C. , Clark, D. , Altman, R. , Hunter, L. , Lengauer, T. , and Wodak, S. (Eds. ), Proc. of Third Int. Conf. on Intelligent Systems for Molecular Biology volume 3 pp. 114–120 Menlo Park, CA. AAAI Press.
  9. Guang-Zheng Zhang; De-Shuang Huang; "Aligning multiple protein sequence by an improved genetic algorithm," Neural Networks, 2004. Proceedings. 2004 IEEE International Joint Conference on , vol. 2, no. , pp. 1179- 1183 vol. 2, 25-29 July 2004.
  10. Hjelmqvist, Sten (26 Mar 2012), Fast, memory efficient Levenshtein algorithm (http://www. codeproject. com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm)
  11. HMMER 3. 1 (February 2013); http://hmmer. org/
  12. Hung Dinh Nguyen; Yoshihara, I. ; Yamamori, K. ; Yasunaga, M. ; "A parallel hybrid genetic algorithm for multiple protein sequence alignment," Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on , vol. 1, no. , pp. 309-314, 12-17 May 2002
  13. Lin, C. H. , Chen, S. J. , and Chen, S. M. 2003. A new method for multiple DNA sequence alignment based on genetic algorithms. Proceedings of the 2003 Joint Conference of AI, Fuzzy System, and Grey System, Taipei, Taiwan, Republic of China.
  14. Mount David W. , Bioinformatics – Sequence and Genome Analysis, Cold Spring Harbor Laboratory Press, 2001.
  15. Notredame, Higgins, Heringa, T-Coffee: A novel method for multiple sequence alignments, Journal of Molecular Biology, 302 (205-217) 2000
  16. Omar, M. F. ; Salam, R. A. ; Rashid, N. A. ; Abdullah, R. ; "Multiple sequence alignment using genetic algorithm and simulated annealing," Information and Communication Technologies: From Theory to Applications, 2004. Proceedings, vol. , no. , pp. 455- 456, 19-23 April 2004.
  17. Ping-Teng Chang; Lung-Ting Hung; Kuo-Ping Lin; Chih-Sheng Lin; Kuo-Chen Hung; , "Protein Sequence Alignment Based on Fuzzy Arithmetic and Genetic Algorithm," Fuzzy Systems, 2006 IEEE International Conference on , vol. , no. , pp. 1362-1367, 0-0 0.
  18. Sellers, Peter H. (1980). "The Theory and Computation of Evolutionary Distances: Pattern Recognition". Journal of Algorithms 1 (4): 359–73. doi:10. 1016/0196-6774(80)90016-4
  19. Shyi-Ming Chen, Chung-Hui Lin, and Shi-Jay Chen, Multiple DNA Sequence Alignment Based on Genetic Algorithms and Divide-and-Conquer Techniques, International Journal of Applied Science and Engineering 2005. 3, 2: 89-100
  20. Smith-Keary. P. Molecular Genetics. Macmillan Education Ltd, London, 1991
Index Terms

Computer Science
Information Sciences

Keywords

Genetic Algorithm Hidden Markov Model Fuzzy Levenshtein Distance