Cheap and Secure Web Hosting Provider : See Now

Algorithm for recovering paired lists when elements are broken

, , No Comments
Problem Detail: 

I am trying to solve an algorithmic problem. I came from upon an advise that this forum would be a better place to ask this.

I would like to hear your advice on where to search for hints. If my problem has got a name, I would like to know what it is called in the field, and what I should learn to solve it. Any partial suggestion would be welcome. Also if there is another forum that fits my question better than here, I would be happy to hear that too.

A description of my problem is as follows. Suppose you have a number of pairs of objects. Let $X$ be the first list of objects and $Y$ be the second list. Assume $X = Y$ in a sense they share the same list of objects.

Now, objects in both lists are "broken" into pieces; Each element $x \in X$ is decomposed to $x_1, x_2,...$. The same happens for $Y$. As a result, what you have is two sets $X', Y'$, which contain the broken pieces of the original objects.
The task is to recover the original objects in $X$ and $Y$ from $X'$ and $Y'$.

Here is an example where objects are strings.
Suppose $X = Y = [apple, banana]$, and the strings are decomposed as: $X' = [ban, le, ana, app]$ and $Y' = [na, ple, ap, na, ba]$. I would like to recover $banana$ and $apple$ from information $X'$ and $Y'$.

Does this problem have a name? Or, what do you think the good things to learn for me to study this type of problem?

Asked By : Kota Mori
Answered By : D.W.

Look at the literature on algorithms for the shotgun sequencing and shortest common supersequence problems. It appears that your problem might not be exactly identical to them, but researchers have developed sophisticated algorithmic techniques for handling this kind of problem. Therefore, I suspect you might be able to use the same techniques for your problem, or adapt them to work well for your situation.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback