BeamGA Median: A Hybrid Heuristic Search Approach

Authors: Ghada Badr, Manar Hosny, Nuha Bintayyash, Eman Albilali, Souad Larabi Marie-Sainte

Abstract:

The median problem is significantly applied to derive the most reasonable rearrangement phylogenetic tree for many species. More specifically, the problem is concerned with finding a permutation that minimizes the sum of distances between itself and a set of three signed permutations. Genomes with equal number of genes but different order can be represented as permutations. In this paper, an algorithm, namely BeamGA median, is proposed that combines a heuristic search approach (local beam) as an initialization step to generate a number of solutions, and then a Genetic Algorithm (GA) is applied in order to refine the solutions, aiming to achieve a better median with the smallest possible reversal distance from the three original permutations. In this approach, any genome rearrangement distance can be applied. In this paper, we use the reversal distance. To the best of our knowledge, the proposed approach was not applied before for solving the median problem. Our approach considers true biological evolution scenario by applying the concept of common intervals during the GA optimization process. This allows us to imitate a true biological behavior and enhance genetic approach time convergence. We were able to handle permutations with a large number of genes, within an acceptable time performance and with same or better accuracy as compared to existing algorithms.

Keywords: Median problem, phylogenetic tree, permutation, genetic algorithm, beam search, genome rearrangement distance.

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

References:

[1] A. C. Siepel, Exact Algorithms for the Reversal Median Problem, Master’s thesis, University Of New Mexico, Albuquerque, New Mexi-co, December, 2001.
[2] E. Ohlebush, M. I. Abouelhoda, K. Hockel and J. Stallkamp, The Median Problem for the Reversal Distance in Circular Bacterial Ge-nomes, in Proceedings of the 2005 international conference on Com-parative genomics, Ottawa, Canada, pp. 240-251, 2005.
[3] J. P. P. Zanetti, P. Biller and J. Meidanis, On the Matrix Median Problem. In Algorithms in Bioinformatics, pp. 230-243, Springer Berlin Heidelberg, 2013.
[4] D. Sankoff and M. Blanchette, Multiple genome rearrangement and breakpoint phylogeny, Journal of Computational Biology, Vol. 5(3), pp. 555-570, 1998.
[5] M. Bernt, D. Merkle and M. Middendorf, Genome Rearrangement Based on Reversals that Preserve Conserved Intervals, IEEE/ACM Trans. Comput. Biol. Bioinformatics 3, Vol. 3, 275-288, 2006. DOI=10.1109/TCBB.2006.38 http://dx.doi.org/10.1109/TCBB.2006.38
[6] N. Eriksen, Reversal and transposition medians, Theoretical Computer Science, Vol. 374(1-3), pp. 111-126, 2007.
[7] M. Bader, On Reversal and Transposition Medians, Ulmer Informatik-Berichte, 2009.
[8] V. Rajan, A. Xu, Y. Lin, K. M. Swenson and B. ME Moret, Heuristics for the inversion median problem, BMC Bioinformatics, 2010.
[9] N. Gao, Using Genetic Algorithm to solve Median Problem and Phylogenetic Inference, Doctoral dissertation, Retrieved from: http://scholarcommons.sc.edu/etd/2825
[10] D. Furcy and S. Koenig, Limited Discrepancy Beam Search, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), Edinburgh, Scotland, UK, 2005.