Search
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.
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 C(S) je celkový počet znaků, které S pokrývá a L(S) je příspěvek za délku supersekvence počítaný jako
<latex> L(S) = \frac{SumL - Length(S)}{SumL}, </latex>
kde SumL je součet všech znaků ve vstupních řetězcích. Tato funkce je maximalizována.