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

- 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.
- Any suggestions for keywords for literature searches would be much appreciated