(1+eps)-approximation of sorting by reversals and transpositions
2002 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 289, no 1, 517-529 p.Article in journal (Refereed) Published
Gu et al. gave a 2-approximation for computing the minimal number of inversions and transpositions needed to sort a permutation. There is evidence that, from the point of view of computational molecular biology, a more adequate objective function is obtained, if transpositions are given double weight. We present a (1+eps)-approximation for this problem, based on the exact algorithm of Hannenhalli and Pevzner, for sorting by reversals only.
Place, publisher, year, edition, pages
Amsterdams, Netherlands: Elsevier, 2002. Vol. 289, no 1, 517-529 p.
Permutations, Sorting, Genome rearrangements, Reversals, Transpositions, Approximation algorithm
IdentifiersURN: urn:nbn:se:oru:diva-41762DOI: 10.1016/S0304-3975(01)00338-3ISI: 000178999300023ScopusID: 2-s2.0-0037163953OAI: oai:DiVA.org:oru-41762DiVA: diva2:781049