An Improved Ant Colony Algorithm for Genome Rearrangements

Authors: Essam Al Daoud

Abstract:

Genome rearrangement is an important area in computational biology and bioinformatics. The basic problem in genome rearrangements is to compute the edit distance, i.e., the minimum number of operations needed to transform one genome into another. Unfortunately, unsigned genome rearrangement problem is NP-hard. In this study an improved ant colony optimization algorithm to approximate the edit distance is proposed. The main idea is to convert the unsigned permutation to signed permutation and evaluate the ants by using Kaplan algorithm. Two new operations are added to the standard ant colony algorithm: Replacing the worst ants by re-sampling the ants from a new probability distribution and applying the crossover operations on the best ants. The proposed algorithm is tested and compared with the improved breakpoint reversal sort algorithm by using three datasets. The results indicate that the proposed algorithm achieves better accuracy ratio than the previous methods.

Keywords: Ant colony algorithm, Edit distance, Genome breakpoint, Genome rearrangement, Reversal sort.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1092526

References:

[1] G. Fertin, A. Labarre, I. Rusu, E. Tannier, S. Vialette, Combinatorics of Genome Rearrangements. MIT Press, 2009.
[2] A. Bergeron, J. Mixtacki, J. Stoye, "A unifying view of genome rearrangements," Proc 6th Workshop Algs in Bioinf (WABI’06), Volume 4175 of Lecture Notes in Comp Sci Springer Verlag, Berlin, 163-173, 2006.
[3] G. Tesler, "Efficient algorithms for multichromosomal genome rearrangements," J Comput Syst Sci, 65(3):587-609, 2002.
[4] P. A. Pevzner, M. S. Waterman, "Open combinatorial problems in computational molecular biology," In Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems, 158-173, 1995.
[5] V. Bafna, P. A. Pevzner, "Genome rearragements and sorting by reversals," SIAM Journal on Computing, 25(2):272–289, 1996.
[6] N. El-Mabrouk, "Sorting signed permutations by reversals and insertions/deletions of contiguous segments," Journal of Discrete Algorithms, 1:105-122, 2001.
[7] A. Caprara, R. Rizzi, "Improved approximation for breakpoint graph decomposition and sorting by reversals," J. of Combin Optimization, 6(2):157-182, 2002.
[8] H. Kaplan, E. Verbin,"Effficient data structures and a new randomized approach for sorting signed permutations by reversals," In Proc. 14th Annual Symposium on Combinaotrial Pattern Matching (CPM ’03), 170–185, 2003.
[9] Q. P. Gu, S. Peng, H. Sudborough, "A 2-approximation algorithm for genome rearrangements by reversals and transpositions," Theoretical Computer Science, 210(2): 327–339, 1999.
[10] H. Kaplan, R. Shamir, R. E. Tarjan, "Faster and simpler algorithm for sorting signed permutations by reversals," SIAM Journal of Computing, 29(3):880–892, 2000.
[11] D. A. Bader, B. M. E. Moret, M. Yan "A linear-time algorithm for computing inversion distance between signed permutations with an experimental study," Journal of Computational Biology, 8(5): 483–491, 2001.
[12] V. Ganapathy, T. Tang, S. Parasuraman," Improved Ant Colony Optimization for Robot Navigation," Proceeding of the 7th International Symposium on Mechatronics and its Applications (ISMA10), Sharjah, UAE, April 20-22, 2010.
[13] Z. Zhang, Z. Feng, Z. Ren, "Novel Ant Colony Optimization Algorithm Based on Order Optimization," Journal of Xi'An Jiaotong University, 44(2): 15-19, 2010.
[14] M. Dorigo, L. M. Gambardella, M. Middendorf, T. Stutzle, "Ant Colony Optimization," IEEE Transactions on Evolutionary Computation, 6(4): 317–365,2002.
[15] B. Bullnheimer, R. F. Hartl, C. Strauss, "A new rank-based version of the Ant System: A computational study," Central European Journal for Operations Research and Economics, 7(1): 25–38. 1999.
[16] M. Dorigo, L. M. Gambardella, "Ant colonies for the traveling salesman problem," BioSystems, 43(2), 73–81, 1997.