PaperlayerView exact revision on arXiv

Source-linked AI summary

Sorting by Transpositions is Difficult

Laurent Bulteau, Guillaume Fertin, Irena Rusu

arXiv:1011.1157v1cs.DScs.CC

TL;DR

Sorting by Transpositions asks how difficult it is to compute the minimum transposition distance between permutation genomes, a relevant evolutionary measure whose complexity had remained unresolved. The paper uses a polynomial-time reduction from SAT to prove NP-hardness and derives NP-hardness for the db(π)/3 sorting decision problem. It also notes that the reduction does not resolve whether the problem has a polynomial-time approximation scheme.

  • Problem

    The computational complexity of computing transposition distance for genomes represented by permutations had remained undetermined despite its relevance to comparative genomics.

  • Method

    The paper constructs a polynomial-time reduction from SAT using basic blocks and transposition behavior to encode satisfiability.

  • Results

    The Sorting by Transpositions problem is NP-hard, and deciding whether π can be sorted using db(π)/3 transpositions is also NP-hard.

  • Takeaways & Limitations

    The paper answers the longstanding complexity question for Sorting by Transpositions and establishes hardness for the breakpoint-based db(π)/3 decision problem.

  • Takeaways & Limitations

    The reduction does not determine whether Sorting by Transpositions admits a polynomial-time approximation scheme because it is not a linear reduction.

Abstract

from arXiv · show

In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance, that is, the minimum number of transpositions needed to transform a genome into another, is, according to numerous studies, a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations, called the Sorting by Transpositions problem, has been introduced by Bafna and Pevzner in 1995. It has naturally been the focus of a number of studies, but the computational complexity of this problem has remained undetermined for 15 years. In this paper, we answer this long-standing open question by proving that the Sorting by Transpositions problem is NP-hard. As a corollary of our result, we also prove that the following problem is NP-hard: given a permutation pi, is it possible to sort pi using db(pi)/3 permutations, where db(pi) is the number of breakpoints of pi?

Introduction

Transpositions model large-scale genomic rearrangements, and their distance provides a parsimonious evolutionary scenario. The paper resolves the longstanding complexity question for Sorting by Transpositions by reducing SAT and proving NP-hardness, with a related breakpoint-based consequence.

  • Motivation: Transpositions exchange consecutive gene sequences, and transposition distance is the minimum number of such operations transforming one genome into another.This distance is used to represent a maximum parsimony evolutionary scenario between genomes.
  • Open problem: Sorting by Transpositions computes transposition distance for genomes represented by permutations.Its complexity class had remained undetermined since the problem’s introduction, motivating approximation algorithms, heuristics, bounds, and variants.
  • Contribution: A polynomial-time reduction from SAT proves that Sorting by Transpositions is NP-hard.The reduction studies transpositions that remove three breakpoints.
  • Contribution: The result also proves NP-hardness of deciding whether a permutation can be sorted using db(π)/3 transpositions.Here, db(π) denotes the number of breakpoints.

1 Preliminaries

The preliminaries formalize transpositions, breakpoints, and transposition distance for permutations, then establish a breakpoint lower bound and illustrate distance computation. These definitions support the later hardness result.

  • 1.1 Transpositions and Breakpoints: A transposition exchanges two consecutive factors of a sequence and is represented on permutations by τi,j,k with 0 < i < j < k ≤ n.Its inverse is also a transposition.
  • 1.1 Transpositions and Breakpoints: A breakpoint is a pair (x −1, x) that is not an adjacency, where adjacency requires π(x −1) = π(x) −1.The number of breakpoints is denoted db(π).
  • 1.1 Transpositions and Breakpoints: Applying one transposition can reduce the number of breakpoints by at most 3.Adjacencies away from the transposition’s cut positions are preserved under the corresponding inverse mapping.
  • 1.2 Transposition distance: The transposition distance dt(π) is the minimum number of transpositions needed to transform π into the identity permutation.The associated decision problem asks whether dt(π) ≤ k.
  • 1.2 Transposition distance: Every permutation satisfies the lower bound dt(π) ≥ db(π)/3.This follows because the identity has zero breakpoints and each transposition removes at most three.
  • 1.2 Transposition distance: For π = (0 2 4 3 1 5), two transpositions sort the permutation, while the breakpoint bound rules out a one-transposition solution.The example has db(π)/3 = 5/3 > 1.

2 3-Deletion and Transposition Operations

This section defines 3DT-instances and their deletion operations, then establishes their correspondence with permutations and transposition distance. A 3DT-step removes a well-ordered triple while rearranging remaining positions, and collapsibility corresponds to sorting with one transposition per triple.

  • 2.1 3DT-instances: A 3DT-instance consists of a set of symbols partitioned into ordered triples, an injection assigning positions, and a word representation over symbols and dots.The domain is the injection’s image, while positions outside the domain are represented by dots.
  • 2.1 3DT-instances: The successor function maps each symbol position to the next element in its ordered triple and is a fixed-point-free bijection whose third iterate is the identity.Thus, the triples induce 3-cycles over the domain.
  • 2.2 3DT-steps: A triple is well-ordered when its three successor-linked positions satisfy i < j < k, equivalently when one of abc, bca, or cab appears as a subword.Only well-ordered triples can define the associated transposition used by a 3DT-step.
  • 2.2 3DT-steps: A 3DT-step deletes a well-ordered triple and applies its associated transposition to shift the positions of the remaining elements.Consequently, another triple may become well-ordered or cease to be well-ordered after the step.
  • 2.2 3DT-steps: A 3DT-instance is collapsible if repeated 3DT-steps reduce it to the empty instance, and examples can contain multiple distinct paths to emptiness.The supplied example includes interactions where triples lose and regain well-orderedness during the sequence.
  • 2.3 Equivalence with the transposition distance: For an equivalent permutation π, breakpoints correspond to the instance domain, giving db(π) = |L| = 3|T|, while each well-ordered triple corresponds to a transposition resolving three breakpoints.Lemma 7 preserves equivalence after a 3DT-step by mapping π to π′ = π ◦ τ.

3 3DT-collapsibility is NP-Hard to Decide

The paper constructs a 3DT-instance from each Boolean formula and proves that the instance is collapsible exactly when the formula is satisfiable, establishing the reduction’s decision basis.

  • For any Boolean formula φ, the paper defines a corresponding 3DT-instance Iφ and proves that Iφ is 3DT-collapsible if and only if φ is satisfiable.

3.1 Block Structure

The reduction organizes 3DT-instances into ordered blocks connected by variables that transfer activation information. A 3DT-step either acts internally within a block or activates a variable and moves an element between source and target blocks while preserving the required structure.

  • Block decomposition: An l-block-decomposition partitions a 3DT-instance into ordered full blocks, while blocks retain only relative element order for the construction.Full blocks control positions in the word representation; blocks suffice when only relative order matters.
  • Variables: A variable is a pair of triples distributed across distinct source and target blocks, and its activation is the 3DT-step on the source-side triple.The source contains b, x, y; the target contains a, c, z.
  • Activation: In a valid variable, the activation triple is well-ordered exactly when x precedes y, whereas the paired triple is not well-ordered.This ordering property ensures that activation uses the intended external triple.
  • Effect of steps: An internal 3DT-step leaves block assignments unchanged, while activating a variable moves only its paired element into the variable’s target block and preserves other relative orders.These two cases are the structural behavior used to analyze assembled blocks.
  • Valid contexts: A valid context partitions all external triples into valid variables, and this partition remains valid after every 3DT-step.This invariant supports composing blocks throughout the reduction.

3.2 Basic Blocks

The construction defines four basic blocks whose behavior graphs encode Boolean operations through permitted variable-activation orders. Internal steps are contracted away so that the remaining graph exposes only dependencies among variables, enabling the blocks to be assembled.

  • Basic blocks: The four basic blocks are copy, and, or, and var, each combining internal triples with external input and output variables.Internal triples are unconstrained within a block, whereas external triples connect blocks through variables.
  • Behavior graphs: Behavior graphs are obtained by exhaustively following applicable 3DT-steps, then contracting internal-step arcs so only variable activations remain.This abstraction exposes which output variables become activable under each block’s input conditions.
  • copy: The copy block permits either output activation after the input, yielding the orders (A, A1, A2) and (A, A2, A1).Thus one activated variable is duplicated into two outputs.
  • and: The and block permits the output only after both inputs, with orders (A1, A2, A) and (A2, A1, A).The input order is interchangeable, but the output must be last.
  • or: The or block permits the output after either input, allowing both orders in which A is between the inputs and orders in which A is last.Its four possible orders are listed in Property 16.
  • var: The var block allows one output before the input, but after the input is activated the remaining output can be activated.Its possible activation orders encode an initial choice between A1 and A2 unless A is activated first.
  • Assembly: Assembling basic blocks concatenates their word representations and combines internal triples with external triples, requiring each variable to have one source and one target block.The resulting construction preserves valid contexts through subsequent 3DT-steps.

3.3 Construction

For a CNF formula, the construction builds a 3DT-instance from variables and assembled Boolean blocks representing literals, clauses, and the whole formula. The formula variable is designed to activate only when the formula is satisfiable.

  • Formula assumptions: The input formula is a CNF formula φ = C1 ∧ C2 ∧ ... ∧ Cγ with literals xi or ¬xi, subject to stated multiplicity and clause-size assumptions.The construction may add tautological clauses or duplicate literals to enforce these assumptions.
  • Instance assembly: The instance Iφ is formed by concatenating the selected block word representations and their internal and external triples.The relative block order is chosen mainly for readability, not for the construction’s semantics.
  • Variables: The construction creates variables for positive and negative literal occurrences, clause variables Γc, formula variables Aφ, and intermediate variables.Intermediate variables include U, ¯U, V, W, and Y.
  • Block construction: It assembles var blocks for Boolean-variable choices, copy blocks for propagating occurrences, or blocks for clauses, and and blocks for combining clauses into φ.Each variable is assigned exactly one source and one target block.

3.4 Main Result

The reduction proves that a CNF formula is satisfiable exactly when its constructed 3DT-instance is collapsible. Combined with the correspondence between 3DT-collapsibility and transposition sorting, this establishes the paper’s hardness result.

  • Equivalence: Theorem 19 states that Iφ is constructible in polynomial time and is 3DT-collapsible if and only if φ is satisfiable.The proof uses the activation behavior of copy, and, or, and var blocks.
  • Main result: The construction therefore satisfies φ ⇔ Iφ is 3DT-collapsible.The forward and reverse arguments establish both directions of the reduction.
  • Collapsible case: If Iφ is collapsible, the variables activated before Aφ define a truth assignment, and each clause must contain a literal activated before its clause variable.The activation constraints of var, copy, and or ensure that this assignment satisfies every clause.

4 Sorting by Transpositions is NP-Hard

The paper constructs, in polynomial time, a permutation equivalent to each relevant assembling of basic blocks, enabling a reduction from SAT that proves Sorting by Transpositions NP-hard. The construction also establishes NP-hardness for sorting with one-third as many transpositions as breakpoints and for the corresponding 3-permutation restriction.

  • Permutation construction: Theorem 20 constructs a permutation πI in polynomial time for every 3DT-instance that is an assembling of basic blocks, with I ∼πI.The construction partitions the permutation domain into block intervals and defines πI as bijections onto corresponding sets while enforcing endpoint constraints.
  • Permutation construction: The permutation πI is defined block by block for copy, and, and var blocks using rules that ensure the required interval and variable relationships.The construction specifies values through α and β for variables and applies rules R1–R5 across each block interval.
  • Main result: Theorem 21 proves that the Sorting by Transpositions problem is NP-hard.The proof uses the polynomial-time reduction from SAT through 3DT-instances and equivalent permutations.
  • Reduction: The reduction maps a SAT instance to a basic-block 3DT-instance, then to an equivalent 3-permutation πIφ, and sets k = db(πIφ)/3 = n/3.Both transformations are polynomial-time, and the intermediate instance is 3DT-collapsible exactly when the SAT formula is satisfiable.
  • Corollaries: The construction yields two NP-hard decision problems: whether dt(π) = db(π)/3, and whether dt(π) = n/3 for a 3-permutation.For the constructed permutation, the number of breakpoints is db(πI) = n.

Conclusion

The paper establishes NP-hardness for Sorting by Transpositions but leaves approximation and parameterized tractability questions open. Its reduction is not linear, and the smallest exchanged factor remains bounded by 6 in the constructed instances.

  • Open questions: The reduction does not establish whether Sorting by Transpositions admits a polynomial-time approximation scheme because it is not a linear reduction.For an unsatisfiable formula, the constructed instance has dt(πIφ) = db(πIφ)/3 + 1.
  • Open questions: Bounding only the smallest factor exchanged by a transposition does not yield tractability, since this factor is at most 6 for every transposition needed in the reduction.The bound holds independently of the formula φ, while fixed-parameter tractability for other relevant parameters remains open.
Loading 1011.1157v1…