Computing Translocation Distance by a Genetic Algorithm
Lucas da Silveira$^{1}$, José Luis Soncco-Álvarez$^{1}$, Thaynara A. de Lima$^{1}$, Mauricio Ayala-Rincón$^{1}$
$^{1}$Universidade Federal de Goiás. Goiás Brazil
email: lucas.angel9@gmail.com, josesoal@hotmail.com, thaynaradelima@gmail.com, ayala@mat.unb.br

Schedule:Tue 20th@16:45, Room: D

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 that represent genes and chromosomes are modeled as substrings of the genomes; thus, translocation is an operation that models the interaction between chromosomes inside a genome. The translocation distance between two genomes is defined as the minimum number of translocations to convert one genome into another and has 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 particularly difficult, while the signed case, in which the orientation of genes is considered, has been proved to be polynomially decidable. This paper presents an innovative Genetic Algorithm (GA) approach to solve the unsigned translocation distance problem. A distinguishing feature of the proposed GA is that it uses as fitness function the translocation distance for randomly generated signed versions of the input (that is an unsigned genome). Experiments over randomly generated strings (synthetic genomes) showed that the proposed GA approach computes answers that are better than those computed by an 1.5+$\varepsilon$-approximation algorithm, the latter also implemented as part of this work.

BibTex

@InProceedings{CLEI-2015:144681,
	author 		= {Lucas da Silveira and José Luis Soncco-Álvarez and Thaynara A. de Lima and Mauricio Ayala-Rincón},
	title 		= {Computing Translocation Distance by a Genetic Algorithm},
	booktitle 	= {2015 XLI Latin American Computing Conference (CLEI)},
	pages 		= {810--821},
	year 		= {2015},
	editor 		= {Hector Cancela and Alex Cuadros-Vargas and Ernesto Cuadros-Vargas},
	address 	= {Arequipa-Peru},
	month 		= {October},
	organization 	= {CLEI},
	publisher 	= {CLEI},
	url 		= {http://clei.org/clei2015/144681},
	isbn 		= {978-1-4673-9143-6},
	}