Computing Translocation Distance by a Genetic Algorithm

Abstract—Translocation is a useful operation on strings with challenging questions in combinatorics of permutations and interesting applications in analysis of sequences. A translocation operation essentially is the interchange of prefixes and suffixes among two substrings of a string. For the case of genomes represented as strings, symbols represent genes and chromosomes are modeled as substrings of the genomes; thus, translocation is an operation that models the interaction between chromo-somes among a genome. The translocation distance between two genomes is defined as the minimum number of translocations to convert one genome into the other and had been proved to be a meaningful manner of modeling the evolutive distance between organisms. The particular case of unsigned genomes, those in which the orientation of the genes are not considered, is partic-ularly difficult, while the signed case, in which the orientation of genes is considered, has been proved to be polynomially decidable. This paper compiles a proof of the NP-hardness and presents an innovative GA approach to solve the unsigned translocation distance problem. As distinguished feature, the proposed GA uses as fitness function the translocation distance for randomly generated signed versions of the unsigned genomes. Experiments over randomly generated strings (synthetic chromosomes) show that the proposed GA approach compute answers that are better than those computed by an 1.5+ε-approximation algorithm, the latter also implemented as part of this work. I