转座直径与孤独排列相关研究

# 转座直径与孤独排列相关研究 ## 1. 会议与研究背景 2012 年 8 月 15 - 17 日在巴西坎普格兰德举办了第 7 届巴西生物信息学研讨会（BSB 2012）。该研讨会是一个国际会议，涵盖了生物信息学和计算生物学的各个方面，由巴西计算机协会（SBC）的计算生物学特别兴趣小组组织。BSB 系列始于 2005 年，在 2002 - 2004 年期间名为巴西生物信息学研讨会（WOB），2012 年正值其 10 周年。 本次研讨会有 55 名成员组成的国际程序委员会，经过严格评审，16 篇论文被选中进行口头报告，所有论文至少由三名独立评审员评审。部分被接受的论文还受邀以扩展形式提交至《IEEE/ACM 计算生物学与生物信息学汇刊》（TCBB）的特刊。此外，研讨会还有主题演讲，邀请了多位知名专家。 ## 2. 研究问题引入 在比较基因组学中，通过比较两个生物体中共同基因的顺序，可以估计在进化过程中发生的一系列突变。在简化的基因组重排模型中，每个突变都是一次转座，每个生物体的唯一染色体用排列来建模，即没有重复或缺失的基因。转座是指染色体内基因顺序的重排，其中两个连续的基因块被交换。 转座距离是将一个染色体转换为另一个染色体所需的最少转座次数。确定两个排列之间的转座距离已被证明是 NP 难问题，但转座直径，即对称群 Sn 中转座距离的最大可能值，仍然是一个未解决的问题。 已知的转座直径下界，当排列长度为偶数时由 Meidanis、Walter 和 Dias 给出，当长度为奇数时由 Elias 和 Hartman 给出。Lu 和 Yang 提出了一个新的“超级坏排列”的定义，若存在这样的排列，将有可能构建一个转座距离大于当前已知下界的无限排列族。然而，研究表明不存在超级坏排列，当前最好的下界仍然由 Meidanis、Walter、Dias、Elias 和 Hartman 给出。 ## 3. 基本概念定义 ### 3.1 排列相关定义 - **排列**：一个排列 π = [π1π2 ... πn] 是 [n] = {1, 2, ..., n} 到自身的双射函数，使得 π(i) = πi ，其中 1 ≤ i ≤ n。任何长度为 n 的排列都是对称群 Sn 的元素，两个长度为 n 的排列 π 和 σ 的乘积也是一个长度为 n 的排列，每个排列 π 都有一个逆排列 π−1 ，满足 π · π−1 = ι[n] = [1 2 · · · n - 1 n] ，且对于任何长度为 n 的排列 π ，有 π · ι[n] = π 。这里 ι[n] 表示恒等排列，ρ[n] 表示逆排列 [n n - 1 · · · 2 1]。 - **转座**：转座用 t(i, j, k) 表示，其中 1 ≤ i < j < k ≤ n + 1，它是排列 [1 2 · · · i - 1 j j + 1 · · · k - 1 i i + 1 · · · j - 1 k · · · n]。π 和 t(i, j, k) 的乘积是将转座 t(i, j, k) 应用于 π 的结果，即 π · t(i, j, k) 是排列 [π1 π2 · · · πi - 1 πj · · · πk - 1 πi · · · πj - 1 πk · · · πn]。 - **转座距离**：排列 π 相对于排列 σ 的转座距离 dt(π, σ) 是将 π 转换为 σ 所需的最短转座序列 t1, t2, · · ·, tq 的长度 q 。如果 π = σ ，则 dt(π, σ) = 0。转座直径 TD(n) 是对称群 Sn 中所有排列的最大转座距离。由于 dt(π, σ) = dt(πσ−1, ι) ，我们可以考虑 σ = ι ，并记 dt(π) = dt(π, ι)。 ### 3.2 孤独排列 排列可以分为所谓的环面等价类，同一类中的排列相对于恒等排列具有相同的转座距离。然而，有些环面类只有一个排列，这些排列被称为孤独排列。 定理：一个排列 π 是孤独排列，当且仅当 π = [ℓ 2ℓ 3ℓ · · · nℓ] ，其中 ℓ ≥ 1 ，且 gcd(n + 1, ℓ) = 1 ，x 是 x 除以 n + 1 的余数。我们用 un,ℓ 表示孤独排列，其中 n + 1 和 ℓ 互质。例如，当 n = 10 且 ℓ = 8 时，孤独排列 u10,8 = [8 5 2 10 7 4 1 9 6 3]。 ### 3.3 断点图 给定一个排列 π ，其断点图 G(π) 是一个多重图，顶点集 V = {0, -1, +1, -2, +2, · · ·, -n, +n, -(n + 1)} ，边集是两个不相交集合的并集： - 期望边集 D = {(+i, -(i + 1)) | i = 0, · · ·, n} 。 - 现实边集 R = {(+πi, -πi + 1) | i = 1, · · ·, n - 1} ∪ {(0, -π1), (+πn, -(n + 1))} 。 每个顶点的度数为 2 ，因此 G(π) 可以划分为不相交的循环。我们说排列 π 中的一个循环长度为 k ，如果它恰好有 k 条现实边（或等价地，k 条期望边）。G(π) 中奇数长度循环的数量 codd(π) 是一个重要的度量。Bafna 和 Pevzner 证明，对一个排列应用一次转座后，其断点图中奇数循环的数量会有以下三种变化：增加两个单位、不变或减少两个单位。根据对奇数循环数量的影响，转座可以分为 2 - 移动、0 - 移动或 -2 - 移动。这导致了转座距离的下界：dt(π) ≥ ⌈(n + 1) - codd(π) / 2⌉ 。 ### 3.4 相关定理 Meidanis、Walter 和 Dias 观察到，对于 n ≥ 3 ，当 n ≡ 3 (mod 4) 时，逆排列 ρ[n] 中的奇数循环数量为 0 ，因此 dt(ρ) ≥ (n + 1) / 2 = ⌊n / 2⌋ + 1 。对于其他 n ≥ 3 的值，他们发现应用于 ρ[n] 的前两个连续转座不能都是 2 - 移动，因此 dt(ρ) ≥ ⌊n / 2⌋ + 1 也成立。而且，总是可以找到一个长度为 ⌊n / 2⌋ + 1 的转座序列将 ρ[n] 转换为 ι[n] ，所以长度为 n ≥ 3 的逆排列的转座距离 dt(ρ[n]) = ⌊n / 2⌋ + 1 。 ### 3.5 排列的简化与元素顺序表示 - **简化排列**：排列 π 的简化排列 gl(π) 是其断点图 G(gl(π)) 等于 G(π) 去掉长度为 1 的循环，并相应地重新标记顶点的排列。 - **等价简化**：两个排列 π 和 σ 是等价简化的，如果 gl(π) = gl(σ) 。 - **r - 简化**：如果存在一个长度为 r 的转座序列，且所有转座都是 2 - 移动，将 π 转换为一个与 σ 等价简化的排列，则称排列 σ 是 π 的 r - 简化。如果 σ 是 π 的 r - 简化，则 dt(π) ≤ dt(σ) + r 。 可以用 G(π) 中每个循环的非负元素序列或排列中元素的相应位置来表示排列 π 。 - **循环序列**：给定排列 π ，包含元素 i 的每个循环 i 中从最左边元素开始的非负元素序列记为 ci(π) ，这些序列的集合记为 C(π) ，用括号分隔循环序列。 - **位置序列**：给定排列 π 和每个非负元素序列 ci(π) ，相应元素的位置序列记为 pi(π) ，非负元素位置序列的集合记为 P(π) ，用尖括号分隔位置序列。 例如，对于排列 π = [1 2 7 6 3 5 4 8] ，C(π) = {(0), (1), (2 6), (7 5 3 4), (8)} ，P(π) = {⟨0⟩, ⟨1⟩, ⟨2 4⟩, ⟨3 6 5 7⟩, ⟨8⟩} 。 ### 3.6 结排列 设 un,ℓ 是一个孤独排列，且 ℓ > 1 ，则 G(un,ℓ) 满足： 1. 每个循环 ci(un,ℓ) 的长度 k = (n + 1) / gcd(n + 1, ℓ - 1) 。 2. 循环的数量 |C(un,ℓ)| = gcd(n + 1, ℓ - 1) 。 3. 每个循环 ci(un,ℓ) = (+i, +i + ℓ - 1, +i + 2(ℓ - 1), ..., +i + (k - 1)(ℓ - 1)) ，其中 i = 0, ..., |C(un,ℓ)| - 1 。 考虑包含顶点 0 的循环 c0(un,ℓ) = (0, +ℓ - 1, +2(ℓ - 1), ...) ，则 p0(un,ℓ) = ⟨0, m, 2m, ...⟩ ，其中 ℓ - 1 是一个整数，满足 ℓℓ - 1 ≡ 1 (mod n + 1) ，且 m ≡ 1 - ℓ - 1 (mod n + 1) 。 Christie 定义了一种排列 ω ，它只有一个称为结的循环，且有 2r 个元素，p(ω) = ⟨0, n / 2, n, n / 2 - 1, n - 1, n / 2 - 2, n - 2, · · ·, 1, n - (n / 2 - 1)⟩ 。排列 ω 只有在 r ∈ {3q, 3q - 1} （q ≥ 1 ）时存在，并且是唯一满足以下条件的排列：i) 只有一个循环；ii) 没有可以应用的 2 - 移动。 结排列 un,ℓ∗ 定义为： \[ \ell^* = \begin{cases} 2q + 1 & \text{for } n = 6q \\ 4q & \text{for } n = 6q - 2 \end{cases} \] 以下是相关概念的关系图： ```mermaid graph LR A[排列] --> B[孤独排列] A --> C[断点图] B --> D[结排列] C --> E[奇数循环数量] E --> F[转座距离下界] B --> G[转座直径研究] ``` ## 4. 研究结论 通过计算特定孤独排列（结排列）的两个副本的并集的精确转座距离，证明了不存在超级坏排列，因此当前转座直径的最佳下界仍然由 Meidanis、Walter、Dias、Elias 和 Hartman 给出。此外，研究还考虑了不同孤独排列的并集，并定义了一个满足当前下界的替代排列族。 ## 5. 研究方法与证明思路 ### 5.1 排除超级坏排列的存在性 为了证明不存在超级坏排列，研究聚焦于结排列。通过计算特定结排列的两个副本的并集的精确转座距离，发现其结果不支持超级坏排列的存在。这是因为超级坏排列的定义要求满足特定的性质，而结排列并集的转座距离计算结果与这些性质相矛盾。 ### 5.2 定义替代排列族 在排除超级坏排列后，研究进一步考虑不同孤独排列的并集。通过对这些并集的分析，成功定义了一个替代排列族，该族中的排列能够满足当前已知的转座直径下界。这一发现为研究转座直径问题提供了新的思路和方向。 ## 6. 研究的意义与应用 ### 6.1 理论意义 - **解决开放性问题**：本研究在一定程度上推进了转座直径问题的解决。虽然该问题仍然开放，但证明不存在超级坏排列有助于明确研究的方向，避免在错误的方向上浪费精力。 - **完善理论体系**：对孤独排列、结排列等概念的深入研究，丰富了比较基因组学和基因组重排理论的内容，为后续的研究提供了更坚实的理论基础。 ### 6.2 实际应用 - **进化研究**：通过比较不同生物体染色体上基因的顺序，利用转座距离和转座直径的概念，可以更准确地估计生物体在进化过程中发生的突变系列，从而深入了解生物的进化历程。 - **生物医学**：在生物医学领域，了解基因的排列和重排机制有助于研究疾病的发生和发展。例如，某些疾病可能与基因的异常重排有关，通过研究转座距离等概念，可以为疾病的诊断和治疗提供新的思路。 ## 7. 总结与展望 ### 7.1 总结 本研究围绕转座直径和孤独排列展开，通过对相关概念的定义和分析，证明了不存在超级坏排列，当前转座直径的最佳下界仍然由前人给出。同时，定义了一个满足当前下界的替代排列族，为转座直径问题的研究提供了新的视角。 ### 7.2 展望 - **进一步探索转座直径**：尽管目前已经取得了一定的进展，但转座直径问题仍然是一个开放的问题。未来的研究可以继续探索新的排列族，寻找更精确的下界，甚至尝试解决该问题。 - **结合其他领域**：可以将基因组重排的研究与其他领域的技术和方法相结合，如人工智能、机器学习等，以提高研究的效率和准确性。 以下是研究的关键步骤总结表格： |步骤|内容| | ---- | ---- | |定义概念|明确排列、转座、转座距离、孤独排列、断点图等基本概念| |分析下界|研究已知的转座直径下界，并提出超级坏排列的概念| |证明不存在|通过计算结排列并集的转座距离，证明不存在超级坏排列| |定义替代族|考虑不同孤独排列的并集，定义满足当前下界的替代排列族| |探讨意义|分析研究的理论意义和实际应用| |总结展望|总结研究成果，并对未来研究方向进行展望| 以下是研究流程的 mermaid 流程图： ```mermaid graph TD A[定义基本概念] --> B[分析转座直径下界] B --> C[提出超级坏排列概念] C --> D[计算结排列并集转座距离] D --> E[证明不存在超级坏排列] E --> F[定义替代排列族] F --> G[分析研究意义] G --> H[总结研究成果与展望未来] ``` 综上所述，本研究在转座直径和孤独排列的研究方面取得了重要的成果，为后续的研究奠定了基础。未来的研究有望在该领域取得更大的突破，为生物信息学和计算生物学的发展做出更大的贡献。