ACM Journal of Experimental Algorithmics · 2014 · 10 citations · 28 references
Life SciencesBiologyAlgorithmsGenome EvolutionGenomicsGenome RearrangementSorting AlgorithmsGenome Rearrangement AnalysisGenomic Rearrangement Analysis
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 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.
28
Vineet Bafna, Pavel A. Pevzner · SIAM Journal on Discrete Mathematics · 1998 · 416 citations
Genome Rearrangements and Sorting by Reversals
Vineet Bafna, Pavel A. Pevzner · SIAM Journal on Computing · 1996 · 406 citations
Life Sciences, Biology, Genetics +12