Nino Bašić: Nekateri algoritmi in računalniški programi za probleme sintetične biologije, 4. del

Povzetek. Naj bo s niz, ki vsebuje natanko dve pojavitvi vsake črke abecede A. Iščemo take funkcije f: {1, ..., |A|} -> A za katere velja naslednje:

Naj bo l(i) indeks tiste od črk iz f({1, ..., i}), ki se v nizu s pojavi najbolj levo, in analogno d(i) indeks tiste črke iz f({1, ..., i}), ki se v nizu pojavi najbolj desno. Za podniz niza s od l(i)-tega do d(i)-tega mesta pravimo, da je "rigiden". Vsaj eno od pojavitev črke f(i+1) v s mora ležati zunaj "rigidnega" podniza.

Pokazali bomo za katere nize s taka funkcija obstaja, kako jih preštejemo v času O(|A|^2) in kakšna je povezava s sintezno biologijo.

Nato si bomo ogledali popravljeno in nadgrajeno implementacijo algoritma dZIPA. Program po novem zna preverjati tudi stabilnosti z zamaknjenimi registri, antiparalelno in v podsekvencah.

Seminar je zanimiv predvsem za sodelavce projekta BioOrigami.