Leírás
A fehérjék aminosavak láncaiból épülnek fel és ezek a láncok a térben
különböző konformációkat ölthetnek. Minden fehérjének van egy természetes
egyensúlyi állapota, amely ugyan nem statikus, mégis egyensúlynak tekintendő.
Ezeket a térbeli konformációkat meg lehet feleltetni egy rácspontokra
"ráhajtogatott" törött vonalnak, mely nem keresztezi saját magát. A cél olyan
algoritmus tervezése, amely olyan konformációt eredményez, amely a lehető
legkevesebb energiát igényli (vagyis ami közel van az egyensúlyi állapothoz).
Matematikailag ezt úgy lehet megfogalmazni, hogy egy 0-1 karakterekből álló
stringet úgy akarunk ráhajtogatni a négyzetrácsra, hogy a szomszédos
egyesekből álló párok száma maximális legyen. Ez a feladat NP-nehéz, de
léteznek közelítő algoritmusok.
Az előadáson szó lesz egy 1/4-közelítő algoritmusról, valamint arról, hogy az
"U-hajtogatás" illetve az "S-hajtogatás" módszere nem javítja meg ezt az
értéket, a "C-hajtogatás" módszere viszont igen, éppen 1/3-ra, valamint ezzel
kapcsolatban beszélünk egy érdekes visszavezetésről párosításokra és egy
érdekes sejtésről. Ezen kívül szó lesz még egy másik 1/3-közelítő
algoritmusról, melyet Alantha Newman talált.