Étant donné certains fragments de chaîne, je voudrais trouver la chaîne unique la plus courte possible ("chaîne de sortie") qui contient tous les fragments. Les fragments peuvent se chevaucher dans la chaîne de sortie.
Exemple:
Pour les fragments de chaîne:
BCDA
AGF
ABC
La chaîne de sortie suivante contient tous les fragments et a été créée par ajout naïf:
BCDAAGFABC
Cependant, cette chaîne de sortie est meilleure (plus courte), car elle utilise des chevauchements:
ABCDAGF
^
ABC
^
BCDA
^
AGF
Je recherche des algorithmes pour ce problème. Il n'est pas absolument important de trouver la chaîne de sortie strictement la plus courte, mais plus elle est courte, mieux c'est. Je cherche un algorithme meilleur que celui naïf évident qui essaierait d'ajouter toutes les permutations des fragments d'entrée et de supprimer les chevauchements (qui semblerait être NP-Complete).
J'ai commencé à travailler sur une solution et cela s'avère assez intéressant; J'aimerais voir ce que les autres pourraient trouver. J'ajouterai mon travail en cours à cette question dans un moment.
la source
Réponses:
Ce que vous demandez, c'est le problème de Superstring Common le plus court, pour lequel il n'y a pas d'algorithme qui fonctionne pour tous les cas. Mais c'est un problème courant (en compression et séquençage d'ADN) et plusieurs algorithmes d'approximation sont bien connus.
Les algorithmes "gourmands" sont généralement considérés comme les plus efficaces (comme dans le cas, ils ont le pire des cas le moins mauvais).
Lisez l'article sur les algorithmes d'approximation pour le problème de chaîne le plus court commun par Jonathan Turner pour beaucoup plus d'informations.
la source