Skládání proteinů: Popis úlohy

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:

Takovouto sekvenci budeme reprezentovat jako seznam nul a jedniček:

>>> a = [0, 1, 1, 1, 1, 0]

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 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ř.:

>>> a = 3+2j
>>> a.real
3.0
>>> a.imag
2.0

Konfigurací budeme nazývat předpis pro složení řetězce aminokyselin. Budeme-li mít sekvenci aminokyselin

>>> a = [0, 1, 1, 1, 1, 0]

>>> c = [1, 1, 1, 1, 1]

• 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.

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:

>>> from itertools import accumulate
>>> p = [0]   # Začni s pozici první aminokyseliny
>>> p.extend(accumulate(c))
>>> p
[0, 1, 2, 3, 4, 5]

Jiný příklad: pro konfiguraci c = [1, 1, 1j, 1, 1] dostáváme

>>> 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)]

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

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á:

>>> 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]

Pozice aminokyselin pak spočteme již známým způsobem:

>>> p2 = [0]
>>> p2.extend(accumulate(c2))
>>> p2
[0, 1, 2, (2+1j), (2+2j), (2+3j)]

V již ohnuté konfiguraci c2 můžeme znovu ohnout např. poslední dva elementy o dalších 90 stupňů. Výsledek vypadá takto:

>>> 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]

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

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.