Shortest Common Superstring

Das "Shortest Common Superstring"-Problem (SCS) ist ein kombinatorisches Optimierungsproblem, das darin besteht, die kürzeste mögliche Zeichenkette zu finden, die jede Zeichenkette in einer gegebenen Menge als Teilzeichenkette enthält. Das SCS-Problem ist NP-vollständig,<ref>{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Theoretical Computer Science
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:Kari-Jouko Räihä, Esko Ukkonen|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref> daher sind Approximationsalgorithmen von Interesse.

Beispiel: Für die Teilzeichenketten ["AB", "AC", "BA", "BC", "CA", "CB"] lautet ein möglicher SCS "ABACBCA".

Ein bekannter Approximationsalgorithmus ist der Greedy-Algorithmus, der wiederholt zwei Zeichenketten mit maximaler Überlappung zusammenfügt, bis eine einzige Zeichenkette übrig bleibt.<ref>https://www.geeksforgeeks.org/shortest-superstring-problem/</ref>

Ein wichtiges Anwendungsgebiet des SCS findet sich bei der Genomanalyse: Aus einer großen Anzahl einzelner sequenzierter DNA-Bruchstücke lässt sich die Gesamtsequenz mittels des SCS ermitteln.

Literatur

Jonathan S. Turner, Approximation algorithms for the shortest common superstring problem, Information and Computation, Volume 83, Issue 1, 1989, Pages 1-20, ISSN 0890-5401, https://doi.org/10.1016/0890-5401(89)90044-8.

Einzelnachweise