9
$\begingroup$

I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it would find the minimum number of translocations required to go from string a to string b.

My strings are always of the same size and I know there are no errors/substitutions.

Example:

1 2 3 4 5
3 2 5 4 1

This would give me two:

3 2 5 4 1 (start)
-> 3 2 1 4 5 
-> -> 1 2 3 4 5

If this is already implemented in R that would be even better.

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ Looks like you want the edit-distance ( aka Levenshtein distance) ? $\endgroup$
    – Arnab
    Commented Oct 12, 2012 at 17:00
  • $\begingroup$ See this question on Stackoverflow. $\endgroup$
    – The Unfun Cat
    Commented Oct 12, 2012 at 19:13
  • 3
    $\begingroup$ In your particular example where the characters of the string have an implied order, you might want to count inversions. en.wikipedia.org/wiki/Inversion_(discrete_mathematics) $\endgroup$
    – Joe
    Commented Oct 12, 2012 at 19:26
  • 2
    $\begingroup$ It might be disingenuous to call all of those distance functions metrics, as many may not obey the triangle inequality. $\endgroup$
    – Nicholas Mancuso
    Commented Oct 12, 2012 at 19:41
  • 1
    $\begingroup$ By translocation do you mean taking the mirror image of part of the sequence? $\endgroup$
    – highBandWidth
    Commented Oct 12, 2012 at 21:03

2 Answers 2

Reset to default
4
$\begingroup$

Finding the minimal distance is called the "Sorting By Translocation" problem. Part of an abstract from a paper:

"Given two signed multi-chromosomal genomes Pi and Gamma with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Pi to Gamma, where the length of the sequence is called the translocation distance between Pi and Gamma. In 1996, Hannenhalli gave the formula of the translocation distance for the first time, based on which an $O(n^3)$ algorithm for SBT was given. In 2005, Anne Bergeron et al. revisited this problem and gave an elementary proof for the formula of the translocation distance which leads to a new $O(n^3)$ algorithm for SBT."

What's called "translocation" here is called a transposition, i.e., a permutation of exactly two elements in a list, in traditional combinatorial language.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is exactly what I need! Do you happen to know of any working implementation, in either C or R? There doesn't seem to be one in the paper! $\endgroup$
    – user1357015
    Commented Oct 14, 2012 at 0:50
  • $\begingroup$ @user1357015 google it a bit and look through their references, I am sure you will find an implementation. I will also look. Also, note the last line which was added by someone - you might be looking for something a bit different, which is called "reversals". Pavel Pevzner has several papers on this. $\endgroup$
    – Bitwise
    Commented Oct 14, 2012 at 1:16
  • $\begingroup$ @user1357015 found some python code here and this also might be helpful. $\endgroup$
    – Bitwise
    Commented Oct 14, 2012 at 3:51
  • $\begingroup$ @Bitwise Note that Stack Overflow is the site you want to go to for actual code. $\endgroup$
    – Raphael
    Commented Oct 14, 2012 at 9:30
0
$\begingroup$

We need to find the minimum number of transpositions that take one string $a$ to another string $b$, where $a, b$ are permutations. It looks like you are looking for the minimum distance between two given vertices $a, b \in S_n$ in the complete transposition graph, which is the Cayley graph of $S_n$ generated by the set of all transpositions.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.