I have a question, stimulated by some biology, about comparing sets of permutations.

The problem

Let's think of genes on a bacterial chromosome as beads on a string - atomic, unique objects, with an ordering. I'm deliberately ignoring some things, and want to look at a simplified model. So let's say the chromosome is the interval [1,1000], and there are 1000 genes, one at each integer in the interval.

Now suppose I have a set of 100 chromosomes, each from a different individual in a population, each with their 1000 genes, but the ordering is allowed to differ.

In other words, I have 100 different permutations of the integers 1..1000. Let's look at an example. Here are 4 toy bacterial chromosomes, each with 10 genes:

1 2 3 4 5 6 7 8 9 10

1 8 9 2 3 4 5 6 7 10

1 4 3 2 7 8 9 10 5 6

1 4 3 2 10 8 9 5 6 7

When I look at these, I see two things.

First, that the first two both contain 1 2 3 4 5 6 7 10 as a subsequence.

Second, that the final two contain 1 4 3 2 8 9 5 6

I want to construct an algorithm for splitting a list of permutations into subsets like that, such that within the subsets, all permutations contain a common subsequence - a "backbone".

A trivial solution is to make each permutation a subset of size 1 of course, so what I really want is to minimize the number of subsets, and maximize the length of the subsequences.

Prior Work

There is a history of analysing the arrangement genes on chromosomes - afaik it goes back to Dobzhansky and STurtevant in 1938, where they published an evolutionary tree for fruit flies showing "inversions", such as

1 2 3 4 5 6 ---> 1 4 3 2 5 6

There are known biological processes for inverting chunks of DNA, so 2 3 4 goes to 4 3 2.

From the 1980s onwards various people (Watterson, Nadeu, Taylor,Bafna, Pevzner) worked on these problems. But as far as I can tell, all of this work is about finding the "distance" between pairs of genomes, and comstructing trees of relatedness. I'm not trying to do that. I want to split a set of permutations into groups which "share a backbone"

What is my actual question (get to the point!)

I really have two questions

  1. Are there known algorithms that take a set of permutations and try to find long shared subsequences? In terms of complexity, I want to analyse datasets of the order of 100 chromosomes (ideally thousands), each with ~3000 genes. ie I have ~100 permutations of 1..3000.
  2. Any suggestions for keywords for literature searches would be much appreciated

closed as unclear what you're asking by Myshkin, user1688, Stefan Kohl, Wolfgang, Mikhail Katz Feb 7 '16 at 14:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ The question is much improved after the latest edit. I have voted to reopen. $\endgroup$ – Tony Huynh Feb 7 '16 at 22:26
  • $\begingroup$ Not a bad question. Not a good fit for here. Teu scicomp.stackexchange they deal with this kind of problem routinely. Or CrossValidated $\endgroup$ – john mangual Feb 7 '16 at 22:48
  • $\begingroup$ OK - if not a good fit, feel free to delete. The process of framing the question has been useful for me, and I've found a local combinatorialist I can talk to. $\endgroup$ – user1213546 Feb 7 '16 at 22:53

Browse other questions tagged or ask your own question.