Parallelization of genetic algorithms for sorting permutations by reversals over biological data

摘要

Reversals are operations of great biological significance for the analysis of the evolutionary distance between organisms. Genome rearrangement through reversals, consists in finding the shortest sequence of reversals to transform one genome represented as a signed or unsigned permutation into another. When genes are non oriented and correspondingly permutations are unsigned, sorting by reversals came arise as a challenging problem in combinatorics of permutations. In fact, this problem is known to be NP-hard, but the question whether it is NP-complete remains open for more than twenty years. When permutations are signed and correspondingly genes are oriented, the problem is known to be in P. A parallelization of a standard GA (Genetic Algorithm) is proposed for the problem of sorting unsigned permutations. This GA was previously reported in the literature as the most competitive regarding precision for which as control mechanism an 1.5-approximation algorithm was used. For the parallelization, the MPI Library of the C language was used and experiments were performed for calculating the execution time and precision. By increasing the number of individuals, experiment showed improvement in relation to previous approaches. Additionally, a virtualization of the GA using a MicroBlaze processor from Xilinx was performed on OVP for which the average number of executed instructions was of approximately 1.40 Giga instruction per second. In this extended version of this works originally presented in NaBIC 2013 biological data was generated and it was shown how the parallelization can be applied for their analysis. Specifically, the evolutionary distances between different pairs of organism were computed based on the set of non common genes in their mitochondrial DNA genome and the reversal distance between the sequences of common genes.