Simulated Annealing and Genetic Algorithms based heuristics for computing the Non-Uniform Contiguous Translocation Distance

In this paper we study a classic combinatorial problem inspired by genome evolution that aims finding the minimum number of genome rearrangements required to derive one organism from another, thereby calculating the genetic distance between two organisms. More precisely, as part of this study, we consider only the genome rearrangements done by translocation events. The translocation operation is formally defined as a prefix interchange between two chromosomes, represented as strings over the DNA alphabet. The translocation operation is called uniform if the strings are swapping prefixes of equal length. Otherwise, it is called non-uniform. A translocation operation generates two new chromosomes. If these chromosomes are produced in a single copy, the translocation is named contiguous. The translocation distance between two genomes (sets of chromosomes or strings) is defined as the minimum number of translocation operations required to transition from one set to the other. We propose two heuristic algorithms to estimate the non-uniform contiguous translocation distance for a target set of size one. One algorithm is based on simulated annealing, and the other is based on genetic algorithms. We execute the proposed algorithms on both synthetic and real data, then compare the experimental results with those obtained using a greedy-inspired approximation algorithm.