基因组重排问题的近似算法研究 - 长度限制与成本函数的重排列排序

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）29-40www.elsevier.com/locate/entcs长度加权短重排排序的近似算法Alexsandro Oliveira Alexandrinoa，1，2Guilherme Henrique Santos Mirandaa，1，3Carla Negri Lintzmayerb，1，4 Zanoni Diasa，1，5a巴西坎皮纳斯大学计算研究所b巴西ABC联邦大学数学、计算和认知中心摘要基因组重排是一个基因组的大部分切除的事件。当使用重排距离来比较两个基因组时，人们希望找到一个将一个转化为另一个的最小成本重排序列。 由于我们将基因组表示为排列，我们可以将这个问题简化为用最小成本的重排序列对置换进行排序的问题。在传统的方法中，我们认为所有的重排发生的可能性是相同的，我们为所有的重排设置一个单位成本。然而，由于观察到涉及基因组大片段的重排很少发生，因此该问题有两种变化。 第一个变化增加了对重排长度的限制。 第二种变体使用基于重排长度的成本函数。 在这项工作中，我们提出了五个问题的近似算法结合这两种变化，即问题的长度限制和成本函数的基础上重新安排关键词：基因组重排，近似算法，排序排列。1介绍理解进化过程并找出两种不同生物之间的进化距离是计算生物学中具有挑战性的任务一1 这 项 工 作 得 到 了 国 家 技 术 和 科 学 发 展 顾 问 CNPq （ grannts400487/2016-0 和 425340/2016-3 ） ，SaoPauloResearchFoundation，FAPESP（grannts2013/08293-7，2015/11937-9，2017/12646-3，2017/16246-0和2017/16871-1），巴西联邦研究生教育支持和评估机构，CAPES和CAPES/COFECUB计划（赠款831/15）。2电子邮件：alexsandro@ic.unicamp.br3电子邮件：guilherme. students.ic.unicamp.br4电子邮件：carla. ufabc.edu.br5电子邮件：zanoni@ic.unicamp.brhttps://doi.org/10.1016/j.entcs.2019.08.0041571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。30A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）29一种被广泛接受的估计这种距离的方法是使用两种生物体的基因组之间的重排距离，该距离由将一个基因组转化为另一个基因组所需的最小重排基因组重排是改变基因组片段的事件。重排模型M是可用于估计进化距离的有效重排的集合。两种众所周知的基因组重排类型是逆转和反位，逆转和反位使基因组中元件的方向逆转和反位，反位交换基因组中两个相邻区段的位置。我们将基因组表示为整数的排列，其中每个元素对应于我们所比较的基因组共享的基因组片段。这种表示法假设没有重复的基因。如果基因的方向是已知的，我们使用一个有符号的排列，其中每个元素都有一个符号来表示它的方向。如果方向是未知的，符号被省略，我们使用一个无符号排列。由于代数性质，有可能将其中一个基因组表示为单位置换，并且通过这种方式，我们可以将估计重排距离的问题简化为找到最小重排次数以排序置换的问题。无符号置换的反转排序问题是NP难问题[3]。最著名的结果是近似因子为1的算法。375，由Berman et al. [1]的文件。另一方面，如Hannenhalli和Pevzner[6]所示，符号置换的反转排序问题是多项式的。通过转置对（无符号）排列排序的问题是NP-Hard问题[2]，并且最著名的结果是近似因子为1的算法。375，由Elias和Hartman给出[4]。当重排模型中含有反转和转置时，我们就遇到了用反转和转置对有符号和无符号置换进行排序的问题这两个问题的复杂性是未知的。对于无符号置换，最著名的结果是2k-近似算法[14]，其中k是断点图的循环分解的近似因子。对于符号置换，Walter等人[16]提出了一个2-近似算法。排序排列问题的许多变体受到不同生物逻辑相关性的启发[5，7其中一些变体[5，7这种限制的动机是观察到涉及基因组大片段的重排很少发生[11]。对于长度限制等于2和3的情况，我们分别称这些重排为超短重排和短重排。超短运算排序问题是多项式问题[5，8].通过短反转对有符号和无符号排列进行排序的最著名算法分别具有5[5]和2[7]的近似因子。通过短转置对（无符号）排列排序问题的最著名算法的近似因子为5/4[9]。对于同样的问题，存在一个（1+n/x）-近似[10]，其中n是元素的个数，x是置换中的反转数该算法对具有许多反演的置换给出了较低的近似因子。对于prob-A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）2931通过短反转和短转置对有符号和无符号排列进行排序的元素，最著名的算法分别具有3[5]和2[15]的近似因子。长度限制的相同动机激发了一些作者[12，13]考虑长度加权重排，即重排具有基于其长度的成本。在这种方法中，问题的目标是找到一个最小成本的重排序列，对排列进行排序。我们提出了五个这样的问题的近似算法：长度加权短环排序（SbR），长度加权短符号环排序（SbR<$），长度加权短换位排序（SbT），长度加权短反转和短换位排序（SbRT），长度加权短符号环和短换位排序（SbR<$T）。最好的是我们的知识的边缘，有没有在文献中考虑长度加权短后距的结果。这项工作安排如下。第2节介绍了与问题相关的所有概念和符号。第3、4和5节描述了我们开发的近似算法。第6章结束我们的工作2定义大小为n的带符号置换表示为π=（π1π2. π n），使得π i∈ {−n，.，-2，-1，1，2，...，n}和|π i|/= |π j|当且仅当i= j，对于所有i和j。一个大小为n的无符号置换也可以类似地表示，但π i∈ {1，2，.，n}和π i/= π j当且仅当i/= j，对于所有i和j。单位置换，i=（12. n），是我们将要研究的排序问题的目标。 对于符号置换，i的所有元素都具有正号。设一个符号edr ，πj，并且表示每个被选元素的符号。一个无符号反转ρ（i，j），其中1 ≤ i>|π j|.我们使用Inv（π）来表示置换π中的反转数。对于任何置换π，Inv（π）= 0，如果|π1|<|π2|...<...这是什么？< |π n|.注意，考虑到无符号置换，只有单位置换具有Inv（π）=0。引理2.1对于任意置换π，如果Inv（π）>0，则存在逆（π i，π i+1）。证据 设π1，...，π i是一个极大子序列，|π j|<|π j+1|对于所有1 ≤j< i.由于Inv（π）>0，我们有i n。所以，|π i|>>|π i+1|而（π i，π i+1）是一个反演。Q给定一个置换π和一个重排β，令ΔInv（π，β）= Inv（π）−Inv（π·β），即ΔInv（π，β）表示π中由β引起的反转数的变化。从引理2.1，我们可以得出结论，对于任何置换π，使得Inv（π）>0，存在超短重排β，ΔInv（π，β）= 1。引理2.2 提供了ΔInv（π，β）值的界限，其中|β| ≤ 3。引理2.2（GalvJetaoetal. [5]）给定一个置换π和一个序列排列β，我们有i) −1≤ ΔInv（π，β）≤1如果β的长度为 2，ii) −2≤ ΔInv（π，β）≤2，如果β是长度为3的转置，并且iii) − 3 ≤ ΔInv（π，β）≤ 3，如果β是长度为3的有符号或无符号反转。置换π的置换图或逆图是无向图G（π）=（V，E），其中V={π1，π2，.，π n}和E={（π i，π j）：对（π i，π j）是π的逆}。 图1示出了置换图的示例。给定一个带符号置换π，G（π）的连通分支C如果包含奇数个负元素（顶点）则为奇数，否则为偶数。 我们用c（π）和codd（π）分别表示G（π）的连通分支数和奇连通分支数。G（π）的一条边e，如果它的删除使G（π）的连通分支数增加，则称之为割边。 我们用γ（π）表示G（π）中非孤立点的个数，即π中属于至少一个逆的元素的个数A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）2933- − −πππ33| |β322我π我我我St2SrSRTSrSRTSRT≤+3 −4 +6 −1 +5 −2Fig. 1. 带符号置换π=（+3）的置换图G（π4 + 61 + 52）。在这个例子中，c（π）=codd（π）=1和γ（π）=6。2.2熵给定一个置换π，π i的熵定义为ent（π i）=||π i| −i|，因为1≤i≤n。换句话说，元素πi的熵是πi和它在单位置换中的位置之间的距离。 我们定义集合Eeven−={π i：π i<0且ent（π）是偶数}且E奇数+={π：π >0且ent（π）是奇数}。这些设置将b e用于SbR′和SbR′ T的下限。例如，对于π=（+5− 4 +3− 1 +2），我们有ent（+5）= 4，ent（−4）= 2，ent（+3）= 0，ent（-1）= 3，ent（+2）= 3，并且集合Eeven-={-4}，E奇数+={+2}。3无符号置换的逼近算法在本节中，我们提出了SbT的4它们是贪婪的算法，其选择是优先考虑重排，以最低的成本减少最多的反转数。这些算法被命名为4-T、2-R和2-RT，问题SbT、SbR和SbRT。为了证明近似因子，引理3.1给出了比率的界ΔInv（π，β）考虑β是一个短重排。有了这些结果，Lemmas图3.2和3.3给出了将排序距离与置换中的反转数相关联的问题SbT、SbR和SbRT的引理3.1给定一个置换π，任何短反转ρ都有比ΔInv（π，ρ）1|ρ|并且任何短转置τ都具有比率ΔInv（π，τ）≤2。|3|3引理3.2对任意置换π，cf（π）≥3Inv（π）.证据 根据引理3.1，对于任何转置τ，比率ΔInv（π，τ）|τ|至多为2，这意味着将Inv（π）减少1的最小成本是3。由于单位置换具有Inv（i）= 0，因此任何排序序列都需要减少π中的Inv（π）反转来对置换进行排序，从而导致下限3Inv（π）。Q引理3.3对任意置换π，cf（π）≥cf（π）≥Inv（π）。证据 由于问题SbR的任何排序序列都是有效的排序序列，对于SbRT，我们有cf（π）≥cf（π）。cf的证明（π）≥Inv（π）是类似的34A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）29323.Σ证明Lemma 3.2。 注意，对于任何重排β，比率ΔInv（π，β）|β|最多为1（引理3.1）。Q下面的引理描述了贪婪算法给出的距离的上界引理3.4对任意置换π，cf（π）≤2 Inv（π）且cf（π）≤cf（π）≤2Inv（π）。st srtsr证据 我们需要证明，考虑到三个重排模型，总是可以将逆的数量减少1，而成本小于或等于2。如果Inv（π）= 0，则π已经排序。如果Inv（π）>0，则π中存在反演（πi，πi+1）（引理2.1）。因此，转置τ（i，i+1，i +2）和再转置ρ（i，i+1）的成本都是2，并且ΔInv（π，τ（i，i+1，i +2））=ΔInv（π，ρ（i，i+1））= 1，因为逆（πi，πi+1）被移除。Q定理3.5 SbR和SbRT是2-逼近的，SbT是4-逼近的。时间复杂度是O（n）的，所以这个时间复杂度是O（n）的。n反转。除此之外，由于最多三个元素是不确定的，因此可以在恒定时间内计算由短重排由于存在O（n）可能的短重排，算法花费O（n）时间来选择在每个步骤应用的最佳重排。时间复杂度为O（n3）。我们注意到，超短距离排序问题的精确算法的时间复杂度为O（n2）[8]，它也是SbR，SbT和SbRT的有效算法给定一个置换π，在每一步，该算法删除一个长度为2的重排的逆。因此，通过该算法检索的排序序列具有正好2 Inv（π）的成本，这意味着该算法是SbR和SbRT的2-近似（引理3.3）和SbT的4-近似（引理3.2）。然而，上述贪婪算法检索排序序列的成本最多为2 Inv（π），因此，它们具有更好的实际效果。此外，由贪婪算法之一检索的排序序列S具有正好2 Inv（π）的成本，当且仅当它不包含任何长度为3的重排。4改进的转置近似本节介绍了一个改进的近似算法的置换与许多反演。该算法在算法1中定义。对于每个元素πk=i，其中1≤i≤n，算法1应用一个短转置序列将πk移动到其正确位置。这样，置换π在该算法结束时被排序。该算法的时间复杂度为O（n2），因为它有n次迭代，并且在每次迭代的最坏情况下，在π中应用O（n）个短转置。 引理4.1给出了算法1使用的排序序列的 成 本的上 限。A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）293522−232222222222223γ（π）算法1SbT的近似算法函数排序（π）c←0对于i从1到n，如果πi/=i，则设k是元素i的位置如果k-i是偶数，则π←π·τ（k − 2，k，k +1）·τ（k − 4，k − 2，k − 1）·. ·τ（i，i +2，i+3）否则π←π·τ（k − 2，k，k +1）·τ（k − 4，k − 2，k − 1）·. ·τ（i，i +1，i+2）c←c+ 3[k−i<$+2（（k−i）mod 2）返回C引理4.1对于任意置换π，算法1找到一个排序序列S，f（S）≤ Inv（π）+.证据 我们分析了在算法的每次迭代中去除反演的平均成本。考虑第i次迭代.设π为迭代开始时的置换，πJ为迭代结束时的置换。 此外，让πk=i。在该迭代中，我们知道π =（1 2. （i− 1）π i.πk... π n），且对任意i ≤ j k，存在一个逆（π j，π k）<，因为j< k和π k<π j.在用序列Sj将πk移动到其正确位置之后，置换πJ=（1 2... （i− 1）i π i.π k−1π k+1. π n）。如果k−i是偶数，则SJ包含k−i个长度为3的转置，并且f（SJ）=3（k-i）.否则，SJ有[k−i]个长度为3的转置和一个转置长度为2，这意味着f（SJ）=3[k−i] + 2=3（k−i）+1，因为k−i很奇怪由于SJ去除了k i个逆位，并且没有在置换中添加任何逆位，我们得出结论，SJ去除一个逆位的平均成本为3，如果k−i是奇数，它的额外成本为1。因此，f（S）= 3Inv（π）+1m，其中m是使用长度为2的转置的迭代次数。由于S的任何转置都至少去掉了一个反演，并且没有增加反演，因此G（π）的任何孤立元素都不被S所包围。因此，置换π在算法的n−γ（π）次迭代中不会改变因此，m≤γ（π）且f（S）≤3Inv（π）+1γ（π）。Q定理4.2算法1是SbT的（1 +γ（π）/（3 Inv（π）-近似。如果Inv（π）≥cn2，其中c是常数，则算法1的逼近因子为γ（π）n11+3 Inv（π）≤1+ 3 cn2 = 1 +3 cn。例如，如果n = 200且Inv（π）= 10000，则近似因子约为1。007.引理4.3算法1的近似因子至多为5。36A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）292ΣΣΣππ||. d（v）+|Eeven− |+的|E奇数+|是的。 d（v）+|Eeven−|+的|E奇数+ |Σ||πππ′π′πππ′π′+−+证据 图G（π）至少有γ（π）条边。 因此，近似因子为γ（π）γ（π）2 51+3 Inv（π）≤1+ 3 γ（π）/2 = 1 + 3 = 3。Q5符号置换在本节中，我们提出了SbR<$N和SbR<$T的粗略估算因子为3，分别称为3-R′和3-R′ T。很抱歉，我们现在一个7-近似的SbR<$T出租协议，称为7-R<$T。3 35.1SbR′和SbR′T的3-应用肟化法为了说明这些贪婪算法是如何工作的，我们基于π的反转图和集合Eeven−和Eodd+定义了一个得分函数φ。π π给定一个置换π和一个重排序列S，设πJ为结果将S应用于π之后的置换。score函数定义为φ（π，S）=πv∈G（π）π|β|β∈Sπ′π ′v∈G（π′）（2Inv（π）+|Eeven− |+的|E奇数+|）−（2 Inv（πJ）+|Eeven− |+的|E奇数+|）=|β|、β∈S因为对任意置换π， v∈G（π）d（v）= 2 Inv（π）。单位置换是唯一的置换，其中Inv（π）=Eeven−=E奇数+= 0。最优排序序列是具有最高得分函数的排序序列。因此，3-R<$d和3-R<$T的贪婪选择是始终应用具有最高得分函数的短置换，直到置换被排序。以下引理用于证明两种算法的近似因子引理5.1（GalvJetaoetal. [5]）F或任何符号置换π和符号置换2-置换我们有|Ee ven−|+的|Eodd|为|Ee ven|+的|Eodd|，其中πJ=π·ρ′。引理5.2F或任何符号ed置换π和sd符号edreverseρ<$，我们有φ（π，ρ<$）≤3。是的。 设πJ=π·ρ<$且ρ<$=ρ<$（i，j）。 回想一下，ΔI nv（π，ρ<$）=Inv（π）−I nv（πJ）。我们可以将证明分为以下几种情况：(i) 长度为1。 由于1-逆只改变元素πi的符号，所 以 πJ中 的 逆 的 个 数 与π 中的相同. 由于ent（πi）的奇偶性不A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）29373π′3π′πππ′π′ππ我ππππ′π′改变，我们有（|Eeven− |+的|E奇数+|）−（|Eeven− |+的|E奇数+|）≤ 1。因此，我们认为，π πφ（π，ρ<$）≤1。π′π′(ii) 长度为2。一个带符号的2-版本最多只能恢复一个版本，+结果ntly，2（Δ Inv（π，ρ<$））≤2. 更重要的是，我们有|Ee ven−|+的|Eodd|为π π|+的|Eo d d+|（引理5.1）。|(Lemma5.1). 因此，φ（π，ρ′）≤1。(iii) 长度为3。一个有符号的3-版本最多可以恢复三个版本，+结果ntly，2（Δ Inv（π，ρ′））≤6. 更重要的是，我们有一个（|Ee ven−|+|Eodd|）−（|Ee ven−|+|Eodd+|）≤3，因为o=3个元素由yρ′和Ee ve n−ε表示Eodd+=0。因此，φ（π，ρ<$）≤9=3。π3Q引理5.3对于任何符号置换π和短转置τ，我们有φ（π，τ）≤ 7。证据 类似于引理5.2的证明。Q引理5.4对于任何有符号置换πρ<$，其中φ（π，ρ<$）≥1。i，存在短符号反转是的。 设πJ=π·ρ<$。如果Inv（π）=0，则对π的所有元素πi，ent（πi）=0和|E奇数+|= 0。当π/=i时，E中存在一个元素π0偶数−，应用ρ′（i，i）i nπ，这个元素nt成为positive在πJ中。因此，我们认为，|−| E e v e n−|=1，φ（π，ρ <$）= 1。|=1 andφ(π,ρ¯)=1.ππ′如果Inv（π）>0，则π中存在反演（πi，πi+1）（引理2.1）。因此，在本发明中，有符号的2-逆变换ρ<$（i，i+1）将这个逆变换，得到2（Δ Inv（π，ρ<$））=2，|Ee ven−|+的|Eodd+|为|Ee ve n−|+的|Eodd+|（引理5.1）。因此，φ（π，ρ′）=1。Q定理5.53-R<$分别和3-R<$T的3-应用算法和SbR<$T，是的。 由于算法3-R<$l搜索具有最高得分函数的短有符号响应，因此算法每隔一步就找到φ（π，ρ<$）≥1的短有符号响应ρ <$（引理5.4）。 对于一个ny排序序列S，φ（π，S）的值小于或等于3（引理5.2），并且该算法确保得分函数大于或等于1，这给出了近似因子3。对于3-R<$T的proo是类似的。Q算法3-R<$T和3-R<$T的 时间复杂度都是O（n3）。 这种分析类似于算法4-T、2-R和2-RT的分析。注意，对于任何短的重排，得分函数φ可以在恒定时间内计算，因为最多三个元素是不确定的。5.2SbR<$T的7/ 3-应用氧化法38A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）29给定一个置换π和一个重排序列S，设πJ是将S应用于π后得到的置换。我们定义了一个新的得分函数A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）2939Σ- 是的.好 吧ΣΣ3323（π，S）==d（v）+codd（π）−d（v）+codd（πJ）v∈G（π）v∈G（π′）|β|β∈S（2 Inv（π）+codd（π））−（2 Inv（πJ）+codd（πJ））|β|β∈S单位置换是唯一一个Inv（π）+codd（π）= 0的置换。7-近似算法的贪婪选择是总是应用具有最高得分函数的短下面的引理给出了得分函数值的界引理5.6对任意符号置换π和短重排β，我们有<$（π，β）≤7。证据 设πJ= π·β。我们可以将证明分为以下几种情况：(i) β是长度为1的带符号反转。一个带符号的1-反转只选择一个元素，并且不改变排列中反转的数量。除此之外，由于只有包含被忽略元素的分量才可能成为even， 所 以 我 们 有 codd（π）-codd（πJ）≤1。因此，π（π，ρ<$）≤1。(ii) β是长度为2的重排。 设πi和πi+1是由β。我们进一步将分析分为以下子情况：(a) （πi，πi+1）是一个逆。重排β消除了反转（πi，πi+1），因此2（ΔInv（π，β））= 2。此外，注意πi和πi+1在G（π）的同一个分量中。因此，βa只包含一个分量，且codd（π）−codd（πJ）≤1。(b) （πi，πi+1）不是反演。重排β增加了反转（πiJ，πiJ+1），结果ntl y，2（ΔI nv（π，β））=−2。 另外，由于πi和π i+1是G（π）的不同分支，β a只包含两个分支，且codd（π）−codd（πJ）≤ 2。在这两种情况下，我们都有（2 Inv（π）+codd（π））−（2 Inv（πJ）+codd（πJ））≤3，因此，<$（π，β）≤。(iii) β是长度为3的重排。设πi，πi+1和πi+2是被β所包围的元素a。我们进一步将分析分为以下子情况：(a) πi，πi+1和πi+2在G（π）的同一个分量中。我们有2（ΔInv（π，β））≤6（引理2.2）和codd（π）−codd（πJ）≤1。(b) {πi，πi+1，πi+2}的两个元素在分量C1中，其余的元素是G（π）的一个分量C2由于只有一条边连接元素πi，πi+1和πi+2，我们有2（ΔInv（π，β））≤2。此外，βa只包含G（π）的两个分支，且codd（π）−codd（πJ）≤2。(c) π i，π i+1，和π i+2是G（π）的不同分支。在这种情况下，我们有2（ΔInv（π，β））≤ −4和codd（π）−codd（πJ）≤3。注意，一个短转置τ（i，j，i +3），其中i 0，则G（π）中存在边e=（πi，πi+1）. 设C是包含e的分量。假设e不是割边。重排β=τ（i，i+1，i +2）去除了反转（πi，πi+1），并且由于e不是切割边，所以G（πJ）的分量是G（π）的相同分量此外，组件的奇偶性保持不变，因为换位不会改变元素的符号因此，我们有（2 Inv（π）+codd（π））−（2 Inv（πJ）+codd（πJ））= 2和（π，β）≥1。现在，假设e是一个切边。 设C1和C2是C−e的分量。因为e是一个割边，所以元素πi和πi+1是C−e的不同分量。我们进一步将这个证明分为以下几种情况：(i) C1和C2都是偶数。在π上应用β=τ（i，i+ 1，i+ 2）后，我们得到2（ΔInv（π，β））= 2和codd（π）−codd（πJ）= 0。注意，C也是偶数，并且分量C1和C2的奇偶性保持不变。(ii) C1和C2是二进制的。 在对n π应用β=ρ<$（i，i+1）之后，我们得到了2（ΔInv（π，β））= 2和codd（π）−codd（πJ）= 0。注意，C是偶数，并且在π中应用有符号的2-反转之后，分量C1和C2变为偶数。(iii) C1和C2具有不同的奇偶性。在π上应用β=τ（i，i+1，i + 2）后，我们得到2（ΔInv（π，β））= 2和codd（π）−codd（πJ）= 0。注意，C是奇数，并且分量C1和C2的奇偶性保持相同。在所有情况下，我们有（2 Inv（π）+codd（π））−（2 Inv（πJ）+codd（πJ））= 2，n（π，β）≥1。Q定理5.87-R<$T是Sb R <$T的一个7-应用肟化算法。3 3是的。 由于算法7-R<$T总是搜索具有最高得分函数π的短重排，所以在每一步，算法都找到具有π（π，β）1的短重排β（引理5.7）。 对于任何排序序列S，π（π，S）的值小于或等于7（引理5.6），并且该算法确保得分函数大于或等于1，这给了我们近似因子7。Q算法7-R<$T的时间复杂度为O（n4）。 分析类似于以前的贪婪算法，除了它需要线性时间来找到由短重排引起的奇数分量数量的变化[5]。A.O. Alexandrino et al. /Electronic Notes in Theoretical Computer Science 346（2019）29416结论本文研究了长度加权短重排排序问题。我们为五个这样的问题开发了近似算法。在未来的工作中，我们的目标是提高问题的近似因子，涉及签署置换。此外，我们还研究了这个问题的一个新的变形，其中重排引用[1] Berman ， P. ， S. Hannenhalli 和 M. Karpinski ， 1.375-Approximation Algorithm for Sorting byReversals，in：Proceedings of the 10th Annual European Symposium on Algorithms（ESA200-210[2] 布尔托湖G. 费丁和我。Rusu，Sorting by Transpositions is Di？ecult，SIAM Journal on Computing26（2012），pp. 1148-1180。[3] Caprara，A.，Sorting Permutations by Reversals and Eulerian Cycle Decompositions，SIAM Journalon Discrete Mathematics12（1999），pp.91比110[4] 伊 莱 亚 斯 岛 和 T. Hartman ， A 1.375-Approximation Algorithm for Sorting by Transpositions ，IEEE/ACM Transactions on Computational Biology and Bioinformatics3（2006），pp.369-379.[5] GalvZhao，G. R.，O. Lee和Z. Dias，SortingSign edPermutationsbyShortOperation，AltaximsforMolecularBiology 10（2015），pp. 1-17号。[6] Hannenhalli，S.和p. A. Pevzner，将卷心菜转化为萝卜：通过反转排序有符号排列的多项式算法，ACM杂志46（1999），pp. 1比27[7] 希 思 湖 S. 和 j.P. C. Vergara ， Sorting by Short Swaps ， Journal of Computational Biology10（2003），pp.775-789[8] Jerrum ， M. R. ， The Complexity of Finding Minimum-Length Generator Sequences ， TheoreticalComputer Science36（1985），pp.265-289。[9] 江，H.，H. Feng和D. Zhu，An 5/4-Approximation Algorithm for Sorting Permutations by Short BlockMoves ， in ： Proceedings of the 25th International Symposium on Algorithms and Computation（ISAAC491-503.[10] 江 ， H. ， D. Zhu 和 B. Zhu ， A （ 1+ 1 ） -Approximation Algorithm for Sorting by Short Block-Moves，Theoretical Computer Science437（2012），pp.一比八[11] 列 斐 伏 尔 F. 、 N. El-Mabrouk ， E. R. M. Tillier 和 D. 单 基 因 倒 位 的 检 测 和 验 证 ， Bioinformatics19（2003），pp.i190-i196。[12] 阮 氏 T. C. 的 方 法 ， H. T. Ngo 和 N. B. Nguyen ， Sorting by Restricted-Length-Weighted Reversals ，Genomics Proteomics Bioinformatics3（2005），pp.120比127[13] 平特河Y. 和S.Skiena，长度加权反转的基因组排序，基因组信息学13（2002），p. 2002.[14] Rahman ， A. ， S. Shatabda 和 M. Hasan ， An Approximation Algorithm for Sorting by Reversals andTranspositions，Journal of Discrete Algorithms6（2008），pp.449-457[15] Vergara，J. P. C.，“有界排列排序”，博士。论文，弗吉尼亚理工学院和州立大学（1998年）。[16] 沃尔特，M。E. M. T.，Z. Dias和J. Meidanis，线性染色体的重复和易位距离，在：第五届字符串处理和信息检索国际研讨会论文集（SPIRE96比102