Search
Tato úloha řeší problém skládání proteinů, které jsou syntetizovány v buňkách jako dlouhé řetězce aminokyselin, které se skládají do kompakních tvarů. Jak přesně toto skládání probíhá, není vědcům zatím jasné. Pod složením (anglicky folding) se nemyslí chemické složení, ale složení ve smyslu zavinutí proteinu jako provázku (např. do klubíčka).
Problém je tak těžký, že i zjednodušené varianty problému jsou těžko řešitelné. Představujeme zde variantu založenou na modelu čtvercové mřížky.
Úloha používá zjednodušenou dvourozměrnou verzi skládání proteinů. Váš úkol je pro danou sekvenci aminokyselin zjednodušeného proteinu najít optimální konfiguraci složení. Každé možné složení proteinové sekvence je asociováno s volnou energií, který nazýváme výsledek vašeho skládacího algoritmu. Optimální složení (které může být více než jedno) odpovídá konfiguraci s nejmenším možným výsledkem (čili konfigurace s nejmenší možnou volnou energií). V našem ideálním světě jsou pouze dva druhy aminokyselin: hydrofóbní (označené jako 1) a hydrofilní (označené jako 0). Protože protein existuje ve vodním prostředí, hydrofóbní aminokyseliny mají tendenci zůstávat pohromadě, kompaktně a tak daleko od vody, jak jen je možné.
Sekvence aminokyselin pro protein ukázaný níže je
a = [0 1 1 1 1 0]
kde hydrofóbní aminokyseliny jsou červené a hydrofilní aminokyseliny jsou modré.
Představte si aminokyseliny, ze kterých se protein skládá, jako články řetězu. Každý článek se může ohnout o násobek 90 stupňů, ale vzdálenost mezi články řetězu zůstávají stejné. Řetěz nemůže protínat sám sebe a výsledné složení je omezen tak, že leží v rovině. Můžete si tedy představit řetěz jako linii kroutící se po čtvercové mřížce, každá aminokyselina na jednom vrcholu mřížky. Tato linie se často označuje jako samovyhýbající se procházka.
Budeme se odkazovat k rovině jako k rovině komplexníh čísel, abychom zjednodušili konfiguraci každého řetězce. Sekvence složení, kterou vrátí vaše metoda, definuje ohyb každého článku, což vyjádříme pomocí komplexních čísel 1 (východ), i (sever), -1 (západ) a -i (jih).
Pokud dostanete sekvenci aminokyselin a = [0 1 1 1 1 0], můžete např. vrátit konfigurační sekvenci c = [1 1 1 1 1], což vyjadřuje přímou čáru podle diagramu nahoře. Konfigurační sekvence je nutně o jeden element kratší než sekvence aminokyselin, protože každý element konfigurační sekvence definuje vztah mezi dvěma aminokyselinami. Pokud uvažujeme, že první aminokyselina je zakotvená v počátku (0 + 0i), pak pozice dalších aminokyselin je kumulativní součet p=[0 1 2 3 4 5].
Pokud máme konfigurační sekvenci c=[1 1 i 1 1], potom je výsledek ve formě
p=[0 1 2 2+i 3+i 4+i].
Komplexní aritmetika zjednodušuje výpočty. Pokd chceme složit pravou část původní sekvence aminokyselin o 90 stupňů, můžeme vynásobit vektor, který se takto ohýbá:
c = [1 1 1 1 1]
f = [1 1 i i i]
c2 = c .* f (součin vektorů po jednotlivých prvcích)
c2 = [1 1 i i i]
p2 = [0 1 2 2+i 2+2i 2+3i]
Aplikací postupných skládacích vektorů c, váš kód by se měl snažit minimalizovat výslednou energii. Pokud tedy k předchozí konfiguraci přidáme ještě další konfiguraci, která ohne poslední dva elementy o dalších 90 stupňů, výsledek vypadá takto:
f2 = [1 1 1 i i]
c3 = c2 .* f2
c3 = [1 1 i -1 -1]
p3 = [0 1 2 2+i 1+i i]
Datová sada konfigurací aminokyselin (tj. různé proteiny) k ohýbání a skládání jsou dostupné ZDE.
Na této datové sadě bude také probíhat vyhodnocení úlohy.
Cílem úlohy je minimalizovat výslednou energii proteinů přes všechny konfigurace.
Volná energie se počítá jako součet vzdáleností mezi dvěma hydrofóbními aminokyselinami přes všechny dvojice hydrofóbních aminokyselin.
Čili výsledná konfigurace p3 na posledním obrázku má volnou energii:
E = 1 + 1 + 1 + 1 + sqrt(2) + sqrt(2)
To znamená, že nejlepší konfigurace bude mít hydrofóbní konfigurace v co nejvíce kompaktní formě.
Pro vyhodnocení kvality algoritmu spočítejte skóre vašeho algoritmu jako průměr energií přes celou datovou sadu a porovnejte s výsledky vítězů ve sloupečku “results”, příp. s průběžně dosahovanými skóre na stránce statistik.
Za úlohu je možné získat 10 bodů + možné extra ohodnocení až 5 bodů, pokud bude úloha opravdu vyjímečná.
Úloha se vyhodnocuje manuálně na konzultaci se cvičícím. Přepokládáme demonstraci přístupu - tj. načtení dat, vizualizaci výsledků a výpočet skóre pro datovou sadu. Cvičícímu se vysvětlí algoritmus, který problém řeší. V případě netriviálního algoritmu (a skóre na datové sadě, které nebude výrazně zaostávat za tabulkou vítězů na stránce výše) bude úloha ohodnocena plným počtem bodů.
Doporučujeme podrobně přečíst a pochopit zadání. Originál úlohy je k dispozici zde Protein Folding