Nejkratší společná supersekvence

• Data: scsp_data.zip

Kdybychom měli k úloze přistupovat jako k černé skříňce, neměli byste informace o dílčích sekvencích využívat nikde jinde než v ohodnocovací funkci. V této úloze ale je povoleno využívat či analyzovat konkrétní dílčí sekvence i jinde, např. v rekombinačních operátorech.

Je dána množina řetezců znaků dané abecedy. Cílem je nalézt takovou posloupnost znaků dané abecedy (supersekvenci), že všechny původní řetezce jsou v ní zcela obsažené. Řetězec r je obsažen v supersekvenci S právě tehdy, když všechny znaky řetězce r jsou přítomny v supersekvenci S a to v pořadí, v jakém se vyskytují v r.

• Vstup:
  • Abeceda A, ze které jsou tvořeny řetězce.
  • N řetězců (ne nutně stejné délky).
• Výstup: Supersekvence S splňující výše uvedenou vlastnost.

• Lineární řetězec znaků dané abecedy.

                   s1:  ca ag cca  cc ta    cat  c a
                   s2:  c gag ccat ccgtaaa g  tt  g
                   s3:   aga acc tgc  taaatgc t a ga
                        ----------------------------
      Supersequence S:  cagagaccatgccgtaaatgcattacga

• …

Kvalita supersekvence S se počítá jako

<latex> $f(S) = C(S) + L(S)$, </latex>

kde <latex>$C(S)$</latex> je celkový počet znaků, které S pokrývá, a <latex>$L(S)$</latex> je příspěvek za délku supersekvence počítaný jako

<latex> $L(S) = \frac{SumL - Length(S)}{SumL}$, </latex>

kde <latex>$SumL$</latex> je součet všech znaků ve vstupních řetězcích. Tato funkce je maximalizována.