BeamGA Median: A Hybrid Heuristic Search Approach
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.
 A. C. Siepel, Exact Algorithms for the Reversal Median Problem,
Master’s thesis, University Of New Mexico, Albuquerque, New Mexi-co,
 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.
 J. P. P. Zanetti, P. Biller and J. Meidanis, On the Matrix Median Problem.
In Algorithms in Bioinformatics, pp. 230-243, Springer Berlin Heidelberg,
 D. Sankoff and M. Blanchette, Multiple genome rearrangement and
breakpoint phylogeny, Journal of Computational Biology, Vol. 5(3), pp.
 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.
 N. Eriksen, Reversal and transposition medians, Theoretical Computer
Science, Vol. 374(1-3), pp. 111-126, 2007.
 M. Bader, On Reversal and Transposition Medians, Ulmer
 V. Rajan, A. Xu, Y. Lin, K. M. Swenson and B. ME Moret, Heuristics
for the inversion median problem, BMC Bioinformatics, 2010.
 N. Gao, Using Genetic Algorithm to solve Median Problem
and Phylogenetic Inference, Doctoral dissertation, Retrieved from:
 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.