Parallel memetic genetic algorithms for sorting unsigned genomes by translocations

The rearrangement of genomes is an important tool for studying the evolution of genomes and specifically for the construction of phylogenies. A translocation splits and combines the strings of genes of a pair of chromosomes inside a genome and is considered a suitable operation for rearrangement of genomes with multiple chromosomes. The translocation distance between two genomes is the minimum number of translocations necessary to convert one of them into the other. Computing the translocation distance between two unsigned genomes, that is the case in which the direction of the genes between the chromosomes is not considered, is known to be an MV-hard optimization problem. Among several approximation algorithms that were proposed for solving this problem, the authors introduced in a previous work a genetic algorithm approach improved with opposition based learning and memetic mechanisms. In this paper, two parallel treatments of the sequential memetic approach are introduced for solving the translocation distance problem for unsigned genomes. The first approach, computes in parallel the fitness over all individuals of a population. This method intends speeding-up the sequential memetic algorithm. The second approach, processes in parallel multiple populations and was proposed for improving precision providing solutions with a less number of translocations than the sequential memetic algorithm. Several experiments were performed with randomly generated synthetic and biologically based genomes. Results show that the parallel approaches outperform the sequential memetic algorithm.