### An Audit Tool for Genome Rearrangement AlgorithmsAn Audit Tool for Genome Rearrangement Algorithms

Access Restriction
Subscribed

 Author Galvo, Gustavo Rodrigues ♦ Dias, Zanoni Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Genome rearrangements ♦ Ranking and unranking permutations ♦ Sorting by prefix reversals ♦ Sorting by prefix transpositions Abstract We consider the combinatorial problem of sorting a permutation using a minimum number of rearrangement events, which finds application in the estimation of evolutionary distance between species. Many variants of this problem, which we generically refer to as the rearrangement sorting problem, have been tackled in the literature, and for most of them, the best known algorithms are approximations or heuristics. In this article, we present a tool, called $\textit{GRAAu},$ to aid in the evaluation of the results produced by these algorithms. To illustrate its application, we use GRAAu to evaluate the results of four approximation algorithms regarding two variants of the rearrangement sorting problem: the problem of sorting by prefix reversals and the problem of sorting by prefix transpositions. As a result, we show that the approximation ratios of three algorithms are tight and conjecture that the approximation ratio of the remaining one is also tight. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-01-07 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 19 Page Count 34 Starting Page 1.1 Ending Page 1.34

#### Open content in new tab

Source: ACM Digital Library