Shyi-Ming Chen*, Chung-Hui Lin, and Shi-Jay Chen

Department of Computer Science and Information Engineering National Taiwan University of Science and Technology Taipei 106, Taiwan, R. O. C.


 

Download Citation: |
Download PDF


ABSTRACT


Multiple DNA sequence alignment is one of the important research topics of bioinformatics. Because of the huge length of DNA sequences of advanced organisms, some researchers used divide-and-conquer techniques to cut the sequences for decreasing the space complexity for sequence alignment. Because the cutting points of sequences of the existing methods are fixed at the middle or the near-middle points, the performance of sequence alignment of the existing methods is not good enough. In this paper, we present a new method for multiple DNA sequence alignment using genetic algorithms and divide-and-conquer techniques to choose optimal cut points of multiple DNA sequences. The experimental results show that the proposed method is better than the existing method for dealing with multiple DNA sequence alignment.


Keywords: DNA sequences; sequence alignment; multiple sequence alignment; divide-and-conquer techniques; genetic algorithms.


Share this article with your colleagues

 


REFERENCES


  1. [1] Chellapilla, K. and Fogel, G. B. 1999. Multiple sequence alignment using evolutionary programming. Proceedings of the 1999 Congress on Evolutionary Computation, Washington C.: 445-452.

  2. [2] Gen, M. and Cheng, R. 1997. “Genetic Algorithms and Engineering Design”. John Wiley & Sons, New York, S.A.

  3. [3] Gusfield, D. 1977. “Algorithms on Strings, Trees, and Sequences”. Cambridge University Press, New York, S.A.

  4. [4] Hirschberg, D. S. 1977. Algorithms for the longest common subsequence problem. Journal of the ACM, 24: 664-675.

  5. [5] Holland, J. H. 1975. “Adaptation in Natural and Artificial Systems”. MIT Press, Ann Arbor, S.A.

  6. [6] Isokawa, M., Wayama, M., and Shimizu, T. 1996. Multiple sequence alignment using a genetic algorithm. Proceedings of the Seventh Workshop on Genome Informatics, 7: 176-177.

  7. [7] Krane, D. E. and Raymer, M. L. 2001. “Fundamental Concepts of Bioinformatics”. Benjamin Cummings, New York, S.A.

  8. [8] 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.

  9. [9] Lin, C. M. 2000. Using genetic algorithms to solve multiple sequence alignments. Proceedings of the 2000 Genetic and Evolutionary Computation Conference, Las Vegas, Nevada: 883-890.

  10. [10] Man, K. F., Tang, K. S., and Kwong, S. 1996. Genetic algorithms: concepts and applications. IEEE Transactions on Industrial Electronics, 43: 519-534.

  11. [11] Michalewicz, Z. 1992. “Genetic Algorithms + Data Structure = Evolution Programs”. Springer, Berlin, Germany.

  12. [12] Needleman, S. B. and Wunsch, C. D. 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48: 443-453.

  13. [13] Notredame, C. and Higgins, D. G. 1996. SAGA: Sequence alignment by genetic algorithm. Nucleic Acids Research, 24: 1515-1524.

  14. [14] Pevzner, P. A. 2000. “Computational Molecular Biology: An Algorithmic Approach”. MIT Press, Massachusetts, S.A.

  15. [15] Setubal, J. and Meidanis, J. 1997. “Introduction to Computational Molecular Biology”. PWS Publishing Company, Boston, S.A.

  16. [16] Stoye, J. 1998. Multiple sequence alignment with the divide-and-conquer method. Gene, 211: 45-56.

  17. [17] Stoye, J., Perrey, S.W., and Dress, A. W. M. 1997. “Winter Seminar on Molecular Biology and Biophysical Chemistry of the Cell”. Klosters, Switzerland.

  18. [18] Thompson, J. D., Higgins, D. G., and Gibson, T. J. 1994. CLUSTAL W: Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice. Nucleic Acids Research, 22: 4673-4680.

  19. [19] Tönges, U., Perrey, S. W., Stoye, J., and Dress, A. W. M. 1996. A general method for fast multiple sequence alignments. Gene, 172: 33-41.

  20. [20] Waterman, M. S. 1984. General methods of sequence comparison. Bulletin of Mathematical Biology, 46: 473-500.

  21. [21] Zhang, C. and Wong, A. K. C. 1997. A genetic algorithm for multiple molecular sequence alignment. Computer Applications in the Biosciences, 13: 565-581.

  22. [22] Zhang, C. and Wong, A. K. C. 1997. Toward efficient multiple molecular sequence alignment: A system of genetic algorithm and dynamic programming. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 27: 918-932.

  23. [23] JCreator Version 2.5. 2000. Xinox Software. (http://www.jcreator.com/)


ARTICLE INFORMATION




Accepted: 2005-05-04
Publication Date: 2005-10-03


Cite this article:

Chen, S.-M., Lin, C.-H., Chen, S.-J., 2005. Multiple DNA sequence alignment based on genetic algorithms and Divide-and-Conquer techniques. International Journal of Applied Science and Engineering, 3, 89–100. https://doi.org/10.6703/IJASE.2005.3(2).89