Title
Sorting permutations by reversals through a hybrid genetic algorithm based on breakpoint elimination and exact solutions for signed permutations
Date Issued
05 March 2013
Access level
open access
Resource Type
journal article
Author(s)
Ayala-Rincón M.
Universidade de Brasília
Abstract
Sorting permutations by reversals is one of the most challenging problems related with the analysis of the evolutionary distance between organisms. Genome rearrangement can be done through several operations with biological significance, such as block interchange, transposition and reversal, among others; but sorting by reversals, that consists in finding the shortest sequence of reversals to transform one genome into another, came arise as one of the most challenging problems from the combinatorial and algebraic points of view. In fact, sorting by reversal unsigned permutations is an NP-hard problem, for which the question of NP-completeness remains open for more than two decades and for which several interesting combinatorial questions, such as the average number of reversals needed to sort permutations of the same size, remain without solution. In contrast to the unsigned case, sorting by reversals signed permutations belongs to P. In this paper, a standard genetic algorithm for solving the problem of sorting by reversals unsigned permutations is proposed. This approach is based on Auyeung and AbrahamE-s method which uses exact solutions for the signed case in order to build approximate solutions for the unsorted one. Additionally, an improved genetic algorithm is proposed, that in the initial generations applies reversals that simultaneously eliminate two breakpoints, a heuristic mechanism used by several approximation algorithms. As control mechanism for estimating the precision of the results, a correct implementation of an 1.5-approximation algorithm was developed. Also, the results were compared with permutations for which exact solutions are known, such as GollanE-s permutations and their inverses. Several experiments with randomly generated permutations were performed and the results showed that in average the precision of the outputs provided by both the standard and improved genetic algorithms overcome the results given by the 1.5-approximation algorithm as well as those results provided by previous known genetic approaches. © 2013 Elsevier B.V.
Start page
119
End page
133
Volume
292
Language
English
OCDE Knowledge area
Ciencias de la computación
Subjects
Scopus EID
2-s2.0-84875166887
Source
Electronic Notes in Theoretical Computer Science
ISSN of the container
15710661
Sources of information:
Directorio de Producción Científica
Scopus