Lintzmayer Carla Negri, Fertin Guillaume, Dias Zanoni
† Institute of Computing, University of Campinas, Campinas, São Paulo, 13083-852, Brazil.
‡ Laboratoire des Sciences du Numérique de Nantes, UMR CNRS 6004, University of Nantes, 44322 Nantes Cedex 3, France.
J Bioinform Comput Biol. 2017 Feb;15(1):1750002. doi: 10.1142/S0219720017500020. Epub 2017 Feb 9.
Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2-approximation and ([Formula: see text])-approximation algorithms for these problems, where [Formula: see text] is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms.
一些有趣的组合问题源自基因组重排，基因组重排是影响基因组大部分区域的突变。当我们将基因组表示为排列时，目标是以最少的重排次数将给定排列转化为恒等排列。当它们影响排列起始（分别对应末尾）部分的片段时，就被称为前缀（分别对应后缀）重排。本文给出了涉及反转和转置的前缀和后缀版本的重排问题的结果，同时考虑无符号排列和有符号排列。我们针对这些问题给出了2 - 近似算法和（[公式：见正文]） - 近似算法，其中[公式：见正文]是一个常数除以输入排列中的断点（在恒等排列中不应相邻的连续元素对）数量。我们还给出了这些问题的直径界限，并提供了改进我们算法实际结果的方法。
