1
$\begingroup$

I have a question that relates to the classical "longest common subsequence" problem. I'll give the background to the problem, but you could skip to the formulation below if you like

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

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

There is a lot of previous work on finding the longest common subsequence of a fixed set (https://en.wikipedia.org/wiki/Longest_common_subsequence_problem) but I can't find any works addressing how to partition your strings to maximise the length of common subsequence within subsets.

Does anyone know if this is a classical/solved problem also?

PS I posted a (slightly less well formulated) version of this on mathOverflow and the organisers sent me over here.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.