Email this article 
Open Access
Subscription or Fee Access
DNA Multiple Sequence Alignment by an Ant Colony Based Approach
Abstract
recent studies in Bioinformatics have experienced a fundamental swing away from the traditional research and development methodologies based on Biology’s empirical roots to large-scale, computer-based and automated tools and techniques. Today it is systematic and predictive with genomics, informatics, automation, and miniaturization all playing a role. This blending of Biology and Information Science is likely to remain and magnify for a conceivable time. DNA sequence alignment is a frequently witnessed and discussed problem in Bio-informatics, where the researcher is aligning two or more DNA sequences to find common parts in them. Since the DNA sequences are extremely long (e.g. the human genome alone has approximately three billion DNA base pairs), sequence alignment becomes a challenging problem. This paper introduces an ant colony based solution to the DNA multiple sequence alignment problem.
Keywords
References
Arthur M. Lesk. Introduction to Bioinformatics. OxfordUniversity Press, 2002.
B. Holldobler and E.O. Wilson. The Ants. Springer, 1990.
B. Monien, How to find long paths efficiently, Annals of Discrete Mathematics, Vol. 25, 239-254, 1985.
D. Karger, R. Montwani, and G. Ramkumar, On approximating the longest path in a graph, Algorithmica, Vol. 18, No. 1, 92-98, May, 1997.
de Bruijn, N. Proc. Nederl. Akad. Wetensch. 49, 758–764 (1946).
E. Ando, T. Nakata, and M. Yamashita, Approximating the Longest Path Length of a Stochastic DAG by a Normal Distribution in Linear Time, Journal of Discrete Algorithms, Vol. 7, No. 4, 420-438, December, 2009.
Eddy, S.R. 1995. Multiple alignment using hidden Markov models. ISMB 3, 114–120.
Eva K. Lee, Todd Easton, Kapil Gupta. 2006. Novel evolutionary models and applications to sequence alignment problems. Annals of Operations Research 148:1, 167.
Gotoh, O. 1999. Multiple sequence alignment: Algorithms and applications. Adv. Biophys. 36, 159–206..
Idury, R., and Waterman, M.S. 1995. A new algorithm for DNA sequence assembly. J. Comp. Biol. 2, 291–306.
Lipman, D.J., Altschul, S.F., and Kececioglu, J.D. 1989. A tool for multiple sequence alignment. Proc. Natl. Acad. Sci. USA. 86, 4412–4415.
M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics|Part B, 26(1):29-41, 1996.
Marco Dorigo, Gianni Di Caro, and Michael Sampels, editors. Ant Algorithms: Third International Workshop, ANTS 2002. Springer, 2002.
Notredame, C. 2002. Recent progresses in multiple sequence alignment: A survey. Pharmacogenomics 3, 131–144.
Pevzner, P.A., Tang, H., and Waterman, M.S. 2001. An Eulerian path approach to DNA fragment assembly. Proc. Natl.Acad. Sci. USA 98, 9748–9753.
R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis. Cambridge University Press, 1998.
R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, Lecture Notes in Computer Science, Vol. 3341, Springer-Verlag, 871-883, 2004.
S. Prager, and W. Spears, A hybrid evolutionary-graph approach for finding functional network paths, In Proceedings of the 17th ACM GIS Int. Conference on Advances in Geographic Information Systems, ACM, 306-315, Seattle, Washington, U.S.A., November 4-6, 2009.
Skiena, S. The Algorithm Design Manual (Springer, Berlin, 2008).
Thompson, J.D., Higgins, D.G., and Gibson, T.J. 1994. CLUSTAL W: Improving the sensitivity of progressive multiplesequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucl.Acids Res. 22, 4673–4680.
Waterman, M.S. 1995. Introduction to Computational Biology, Chapman and Hall, London.
Waterman, M.S., and Jones, R. 1990. Consensus methods for DNA and protein sequence alignment.Methods Enzymol.183, 221–237.
Waterman, M.S., and Perlwitz, M.D. 1984. Line geometries for sequence comparisons. Bull. Math. Biol. 46, 567–577.
Y. Hsu, S. Sun and D. Du, Finding The Longest Simple Path in Cyclic Combinational Circuits, IEEE Int. Conference on Computer Design, IEEE Computer Society, 530-535, Austin, Texas, U.S.A., 1998.
Y. ZHANG, M.S. WATERMAN. 2003. DNA Sequence Assembly and Multiple Sequence Alignment by an Eulerian Path Approach. Cold Spring Harbor Symposia on Quantitative Biology 68:1, 205.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.