Multiple Sequence Alignment is one of the most useful tools in bioinformatics. It is widely used to identify conservation of protein domains, RNA secondary structure and classification of biological sequences. However, it is recognized as one of the most challenging tasks in bioinformatics. Evolutionary algorithms are providing competitive solutions for engineering optimization. Genetic algorithms are relatively new optimization technique that can be applied to various problems, including those that are NP-hard. We implemented conventional Genetic Algorithm on this problem using a research on Evolutionary Computation System (ECM) using MAT lab. To date, the Genetic Algorithm successfully prevented premature and brought in improvement in Multiple Sequence Alignment for short sequences. However, for the dataset with long sequences, there is no significant improvement. The proposed project work provides evolutionary optimization for MSA with long sequences.

 

Published In : IJCSN Journal Volume 3, Issue 4

Date of Publication : 01 August 2014

Pages : 195 - 199

Figures : 08

Tables : --

Publication Link : An Evolutionary Optimization for Multiple Sequence Alignment

 

 

 

K.Lohita Lakshmi : is a M.Tech scholar at VVIT(Vasireddy Venkatadri Institute of Technology),Nambur. She got her Master of Computer Applications Degree from Venkateswara University and she got her M.Tech from Nagarjuna University. She is very much interested in Data Mining, Bioinformatics and Computer networks.

P.Rajesh : received the M.Tech degree in computer science and engineering (CSE) from Jawaharlal Nehru Technological University Hyderabad in 2009. He is currently pursuing Ph. D degree in the department of computer science and engineering from Jawaharlal Nehru Technological University Hyderabad and working as an assistant professor in CSE department at Vasireddy Venkatadri Institute of technology, Guntur, Andhra Pradesh. His research interests are in the area of Data mining, Information security, Privacy preserving data publishing and sharing.

 

 

 

 

 

 

 

Multiple Sequence Alignment

Genetic Algorithms

optimization

Here we have presented a detailed implementation of multiple sequence alignment using Evolutionary Algorithm. Also in current work we allow the input sequences of various length .The variable length input sequences are pragmatic to real world. Biological sequences generated by multiple alignments provides valuable source of information for investigating properties, characteristics of the future generated sequences. The proposed algorithm provides an evolutionary optimization for Multiple Sequence Alignment with long sequences.

 

 

 

 

 

 

 

 

 

[1] D. B. Fogel. An introduction to simulated evolutionary optimization. IEEE Transactions on Neural Networks, 5:3{14, 1994.

[2] K. Chellapilla and G. B. Fogel. Multiple sequence alignment using evolutionary programming. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC'99), pages 445{452, 1999.

[3] Yang Chen, Jinglu Hu, Kotaro Hirasawa, and Songnian Yu. GARS:an improved genetic algorithm with reserve selection for global optimization. In Proceedings of Genetic and Evolutionary Computation Conference (GECCO'07), pages 1173{1178, 2007.

[4] L. Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.

[5] Wang L and Jiang T. On the complexity of multiple sequence alignment. Comput Biol, 4:337{48, 1994.

[6] Gibson TJ Thompson JD, Higgins DG. Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-speci_c gap penalties and weight matrix choice. Nucleic Acids Res, 22:4673{4680, 1994.

[7] Altschul SF, Gish W, Miller W, Myers EW, and Lipman DJ. Basic local alignment search tool. J Mol Biol, 215:403{410, 1990.

[8] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. Fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary, 6:182{197, 2002.

[9] Andreas W., Indra M., and Gerhard S. An enhanced rna alignment benchmark for sequence alignment programs. Algorithms Mol Biol, 2:19, 2006.