On the Approximation Ratio of Algorithms for Sorting by Transpositions without Using Cycle Graphs

Autor:	Zanoni Dias, Gustavo Rodrigues Galvão
Rok vydání:	2012
Předmět:	Computer science Cycle graph Sorting Approximation algorithm Algorithm
Zdroj:	Advances in Bioinformatics and Computational Biology ISBN: 9783642319266 BSB
DOI:	10.1007/978-3-642-31927-3_3
Popis:	We study the problem of sorting by transpositions, which is related to comparative genomics. Our goal is to determine how good approximation algorithms which do not rely on the cycle graph are when it comes to approximation ratios by implementing three such algorithms. We compare their theoretical approximation ratio to the experimental results obtained by running them for all permutations of up to 13 elements. Our results suggest that the approaches adopted by these algorithms are not promising alternatives in the design of approximation algorithms with low approximation ratios. Furthermore, we prove an approximation bound of 3 for a constrained version of one algorithm, and close a missing gap on the proof for the approximation ratio of another algorithm.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::0bf1b12a14546e68f9865357c149ba19 https://doi.org/10.1007/978-3-642-31927-3_3 Zobrazit plný text záznamu