7
$\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.

$\endgroup$

migrated from cstheory.stackexchange.com Oct 12 '12 at 19:03

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 3
    $\begingroup$ Looks like you want the edit-distance ( aka Levenshtein distance) ? $\endgroup$ – Arnab Oct 12 '12 at 17:00
  • $\begingroup$ See this question on Stackoverflow. $\endgroup$ – The Unfun Cat Oct 12 '12 at 19:13
  • 2
    $\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 Oct 12 '12 at 19:26
  • 1
    $\begingroup$ It might be disingenuous to call all of those distance functions metrics, as many may not obey the triangle inequality. $\endgroup$ – Nicholas Mancuso Oct 12 '12 at 19:41
  • 1
    $\begingroup$ By translocation do you mean taking the mirror image of part of the sequence? $\endgroup$ – highBandWidth Oct 12 '12 at 21:03
3
$\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.

$\endgroup$
  • $\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 Oct 14 '12 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 Oct 14 '12 at 1:16
  • $\begingroup$ @user1357015 found some python code here and this also might be helpful. $\endgroup$ – Bitwise Oct 14 '12 at 3:51
  • $\begingroup$ @Bitwise Note that Stack Overflow is the site you want to go to for actual code. $\endgroup$ – Raphael Oct 14 '12 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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