====== Skládání proteinů: Popis úlohy ======
===== Sekvence aminokyselin =====

Pro skládání proteinů použijeme zjednodušený svět ve formě 2D pravoúhlé mřížky, kde se vyskytují pouze dva druhy aminokyselin: hydrofóbní (označené jako 1) a hydrofilní (označené jako 0). Mějme následující sekvenci aminokyselin, kde jsou hydrofóbní aminokyseliny označeny červené a hydrofilní modře:

{{ :courses:a4b99rph:cviceni:folding1.gif?200 |Protein 1}}

Takovouto sekvenci budeme reprezentovat jako seznam nul a jedniček: 
<code python>
>>> a = [0, 1, 1, 1, 1, 0]
</code>

===== Protein = Složená sekvence aminokyselin =====
Představte si sekvenci aminokyselin, z níž máme složit protein, jako řetěz. Každý jeho článek se může ohnout o násobek 90 stupňů, ale vzdálenosti mezi články řetězu zůstávají stejné. Řetěz nemůže protínat sám sebe a lze jej skládat jen v rovině (tj. v naší 2D mřížce). Složený řetěz pak tvoří linii "kroutící se" ve čtvercové mřížce, kde každá aminokyselina leží v nějakém vrcholu mřížky. Taková linie se někdy označuje jako [[https://en.wikipedia.org/wiki/Self-avoiding_walk|sobě se vyhýbající procházka]].

Pro popis pozic mřížky můžeme použít komplexní čísla (kde souřadnice pozice bude určena reálnou a imaginární složkou), např.:
<code python>
>>> a = 3+2j
>>> a.real
3.0
>>> a.imag
2.0
</code>
Podobně pro určení směru v mřížce můžeme použít komplexní čísla jednotkové velikosti: ''1'' (východ), ''1j'' (sever), ''-1'' (západ) a ''-1j'' (jih). 

===== Konfigurace proteinu =====
Konfigurací budeme nazývat předpis pro složení řetězce aminokyselin. Budeme-li mít sekvenci aminokyselin 
<code python>
>>> a = [0, 1, 1, 1, 1, 0]
</code>
můžeme k ní přiřadit např. konfiguraci 
<code python>
>>> c = [1, 1, 1, 1, 1]
</code> 
což odpovídá přímé "vodorovné" linii (viz obrázek výše), pokud se domluvíme na následujících vlastnostech a interpretaci konfigurace:

  * Konfigurace je sekvence jednotkových komplexních čísel a je nutně o jeden element kratší než sekvence aminokyselin.
  * První aminokyselina je umístěna v počátku (''0 + 0j'').
  * Umístění dalších aminokyselin se řídí jednotlivými prvky konfigurační sekvence, a to tak, že se k pozici předchozí aminokyseliny přičte první dosud nepoužitý prvek konfigurace. Pro příklad nahoře tedy
    * druhá aminokyselina leží na pozici ''1 + 0j'' (protože ''(0 + 0j) + 1 = (1 + 0j)'',
    * třetí aminokyselina leží na pozici ''2 + 0j'' (protože ''(1 + 0j) + 1 = (2 + 0j)'',
    * atd.

===== Pozice aminokyselin podle konfigurace =====
Připomeňme, že první aminokyselina je zakotvená v počátku ''(0 + 0j)''. Jistě jste si všimli, že pozice dalších aminokyselin je dána kumulativním součtem konfigurační sekvence. S využitím funkce ''accumulate'' z modulu ''itertools'' tak lze poměrně snadno získat pozici všech aminokyselin:
<code python>
>>> from itertools import accumulate
>>> p = [0]   # Začni s pozici první aminokyseliny
>>> p.extend(accumulate(c))
>>> p
[0, 1, 2, 3, 4, 5]
</code>

Jiný příklad: pro konfiguraci ''c = [1, 1, 1j, 1, 1]'' dostáváme
<code python>
>>> c = [1, 1, 1j, 1, 1]
>>> p = [0]   # Začni s pozici první aminokyseliny
>>> p.extend(accumulate(c))
>>> p
[0, 1, 2, (2+1j), (3+1j), (4+1j)]
</code>

Taková konfigurace je vidět na následujícím obrázku:

{{ :courses:a4b99rph:cviceni:folding2.gif?200 |Protein 2}}


===== Ohýbání konfigurace =====
Jednu konfiguraci můžeme změnit v jinou např. tak, že ji za nějakou aminokyselinou ohneme po nebo proti směru hodinových ručiček. Komplexní aritmetika zjednodušuje výpočty. Pokud např. chceme ohnout pravou část původní konfigurace ''c'' o 90 stupňů, můžeme ji po prvcích vynásobit sekvencí ''f'', která je takto ohnutá:
<code python>
>>> c = [1, 1, 1, 1, 1]
>>> f = [1, 1, 1j, 1j, 1j]
>>> c2 = [a*b for a, b in zip(c, f)]  # Součin sekvencí c a f po prvcích
>>> c2
[1, 1, 1j, 1j, 1j]
</code>

Pozice aminokyselin pak spočteme již známým způsobem:
<code python>
>>> p2 = [0]
>>> p2.extend(accumulate(c2))
>>> p2
[0, 1, 2, (2+1j), (2+2j), (2+3j)]
</code>

{{ :courses:a4b99rph:cviceni:folding3.gif?100 |Protein 3}}

V již ohnuté konfiguraci ''c2'' můžeme znovu ohnout např. poslední dva elementy o dalších 90 stupňů. Výsledek vypadá takto:
<code python>
>>> f2 = [1, 1, 1, 1j, 1j]
>>> c3 = [a*b for a, b in zip(c2, f2)]
>>> c3
[1, 1, 1j, (-1+0j), (-1+0j)]
>>> p3 = [0]
>>> p3.extend(accumulate(c3))
>>> p3
[0, 1, 2, (2+1j), (1+1j), 1j]
</code>

{{ :courses:a4b99rph:cviceni:folding4.gif?100 |Protein 4}}

Sekvencí několika ohnutí/skladů jsme získali výslednou konfiguraci ''c3''. Jak dobrá ale tato konfigurace je?


===== Volná energie proteinu =====
Protože protein existuje ve vodním prostředí, hydrofóbní aminokyseliny (1) mají tendenci zůstávat pohromadě v kompaktních útvarech. Každé možné složení sekvence aminokyselin (možný protein) je asociováno s volnou energií. A protože v přírodě často systémy zaujímají stavy s nejnižší energií, optimální složení (které máte najít a které může být více než jedno) odpovídá konfiguraci s nejmenší volnou energií.

**Volná energie** se v naší úloze počítá jako součet vzdáleností mezi každými dvěma hydrofóbními aminokyselinami, přičemž použijeme Euklidovskou vzdálenost. Neformálně řečeno, vaším úkolem je najít takovou konfiguraci, díky které budou hydrofóbní aminokyseliny "co nejblíže u sebe".

V posledním příkladu jsme našli konfiguraci ''c3'', jíž odpovídají pozice aminokyselin ''p3'' na posledním obrázku. Tato konfigurace má volnou energii:
\( E = 1 + 1 + 1 + 1 + \sqrt{2} + \sqrt{2} \) 

Vaším úkolem je tedy pro nějakou vstupní sekvenci aminokyselin ''a'' najít takovou konfiguraci ''c'', která minimalizuje volnou energii.