PA081: Programování numerických
výpočtů
PA081: Programování numerických výpočtů
10. Simulace dynamických dějů
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
jaro 2013
Silové
interakce
molekul
Model interakce molekul
dvě molekuly
► pevná, velká - receptor
► menší, pohyblivá - Ugand
pohyblivou molekulu ovládáme
► myš a klávesnice,
► zařízení silové zpětné vazby
molekuly silově interagují
► přitažlivé i odpudivé síly
► každý atom s každým
význam
► nalezení místa, kde si ligand „sedne"
► pochopení vlastností interakce v okolí
simulace musí působit důvěryhodně
► co nejdokonalejší iluze manipulace s reálnými objekty
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□     s   4 :
■OQ.O
Zařízení silové zpětné vazby
PA081: Programování numerických
výpočtů
vyvinula se z teleoperátorů
► manipulace na dálku, např. v nebezpečném prostředí
► manipulace s virtuálním prostředím
impedanční (odporové)
► zařízení snímá polohu, případně rychlost
► působí vypočtenou silou
► modelovaný systém je vyjádřen jako „odpor" - silová reakce systému na změnu polohy
admitanční (vodivostní)
► zařízení snímá silové působení
► přesune se do vypočtené polohy
► modelovaný systém je vyjádřen jako „vodivost" - ochota systému reagovat na vnější silové působení
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Zařízení silové zpětné vazby
PA081: Programování numerických
výpočtů
v ideálním případě lze modelovat vše obojím
► vstupují nedokonalosti zařízení
► prakticky jsou impedanční zařízení lepší v modelu, kde převládá aktivita operátora
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Zařízení silové zpětné vazby
PA081: Programování numerických
výpočtů
Model interakce I molekul
v ideálním případě lze modelovat vše obojím
► vstupují nedokonalosti zařízení
► prakticky jsou impedanční zařízení lepší v modelu, kde převládá aktivita operátora
hmat má výrazně nižší latenci než zrak
nutná obnovovací frekvence 1 kHz
vysoká náročnost na numerické vyhodnocení modelu
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Přímé mapování síly
model je de facto statický
► vstup (souřadnice zařízení) jsou přímo promítnuty do modelu
► na jejich základě je vypočtena silová interakce interakce
► síla je opět přímo aplikována na zařízení
např. kolize dvou koulí, modelujeme tvrdou pružinou
0
fcCRi
R2
r > Ri + R2 r <R\+R2
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
Přímé mapování síly
model je de facto statický
► vstup (souřadnice zařízení) jsou přímo promítnuty do modelu
► na jejich základě je vypočtena silová interakce interakce
► síla je opět přímo aplikována na zařízení
např. kolize dvou koulí, modelujeme tvrdou pružinou
0
fcCRi
R2
r > Ri + R2 r <R\+R2
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
jednoduché, přehledné, ale takhle reálný svět nefunguje
► veškeré dynamické chování (tj. jaký je efekt aplikované síly) jsme z modelu vyloučili
► zejména nedokážeme modelovat různé hmotnosti kolidujících objektů
► dynamicky se chová fyzické zařízení atd., ale to nestačí
nezatracujeme úplně, na některé aplikace stačí
Silové
interakce
molekul
Virtuální spojení
„virtual coupling"
manipulovaný objekt je k zařízení připojen viskoelastickým spojem
paralelní pružina a tlumič
F = kAx + bAv
silová zpětná vazba
► jakou silou má zařízení působit na operátora vstup pro model
► jak působí operátor na manipulovaný virtuální objekt tj. 3. Newtonův zákon v praxi
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□     s   4 :
■OQ.O
Fyzikálně věrné modely
Model interakce I molekul
cílem je modelovat virtuální svět
ne vše se v takovém světě chová podle očekávání
► nemusíme mít ani odpovídající zkušenost chování modelu nemůže být zcela překvapivé musí odpovídat základním zkušenostem z reálného světa ty jsou vyjádřeny elementárními fyzikálními zákony platí obecně pro jakékoli modelování
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 = ►   < -Š ►
Fyzikálně věrné modely
PA081: Programování numerických
výpočtů
Newtonovy zákon, zejména druhý:
F = ma
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Fyzikálně věrné modely
PA081: Programování numerických
výpočtů
Newtonovy zákon, zejména druhý:
F = ma
Model interakce I molekul
1. termodynamický zákon
Celková energie izolovaného systému zůstává konstantní.
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
Fyzikálně věrné modely
PA081: Programování numerických
výpočtů
Newtonovy zákon, zejména druhý:
F = ma
Model interakce I molekul
1. termodynamický zákon
Celková energie izolovaného systému zůstává konstantní.
2. termodynamický zákon
Entropie izolovaného systému nikdy neklesá.
► vnímání spontánní změny, vnímání času
► každý systém má tendenci „zbavit se" své energie
► http://secondlaw.oxy.edu
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
Kinematika a dynamika hmotného bodu
Opakování středoškolské fyziky
► rovnoměrný pohyb x = v t
► rovnoměrně zrychlený pohyb v = at
► obecněji (nerovnoměrný pohyb, vektorové vyjádření)
Model interakce I molekul
dx
dv
spolu s 2. Newtonovým zákonem a zavedením hybnosti P = mv dostaneme pohybové rovnice
dx     P       ■ ďP
x = — = —      P= — = F dt    m dt
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
postupné řešení (integrace) v ubíhajícím čase je simulace chování systému
□     s   4 :
Kinematika a dynamika hmotného bodu
Příklad - pružinový oscilátor
► hmotný bod na pružině, pohyb jen v jednom směru ► vše ostatní zanedbáno
pohybové rovnice
dt     m dt
vede na diferenciální rovnici
d2y k dt1 m
řešením v R — R je funkce
y = 0
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
y(t) = ci sin,/—t + C2cos,í~~t m V m
ci,cz vyplývají z počátečních podmínek
Metody integrace
ne vždy lze řešit pohybové rovnice analyticky
nemožné, když na proces působí uživatelský vstup řešíme numerickou integrací
main(int argc,char ** argv) {
float     km = 1, p = 1, y = 0, t = 0,
dt = atof(argv[l]); int        i, max = 50*km/dt;
for (i=0;i<max;i++) {
float pl = p - km*y*dt, yl = y + p*dt;
printf("%f %f\n",t,y); t += dt;
Metody integrace
Něco je špatně
* A
1 1
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
0 5 10 15 20 25 30 35 40 45 50
Ař = 0.0001 (zelená), Ař = 0.01 (červená)
Metody integrace
Eulerova dopředná
► řešíme rovnici (resp. systém rovnic)
dy
f(t,y(t))
počítáme posloupnost
yn+i = y n
At
dy
Model interakce I molekul
explicitní metoda
► k výpočtu dalšího kroku známe vše potřebné sinx je ideálně nešikovná funkce
► pro x G [0, tt] je sinx > 0 a je konvexní, pro x G [n, 2tt] je sinx < 0 a je konkávni
► použitá derivace vždy nadhodnocuje
► výpočet do systému přidává energii
pružinový oscilátor je velmi typickou komponentou modelovaných systémů
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Metody integrace
Eulerova zpětná
Model interakce I molekul
použijeme derivaci až v bodě tn+i
yn+i = yn + At —
dosazením vede na řešení rovnice
yn+i = yn + At/(t n+11 yn+1))
implicitní metoda
► pro výpočet dalšího kroku musíme řešit rovnici nebo systém rovnic
► obecně nemusí být triviální
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
Metody integrace
Eulerova zpětná
Model interakce I molekul
pro pružinový oscilátor
Ař
yn+i = yn + —Pn+i
m
Pn+1 = Pn- Atkyn+i
Fyzikálně věrné modely
Metody integrace
jednoduchý systém lineárních rovnic
řešení lze vyjádřit analyticky a naprogramovat
Silové
interakce
molekul
Metody integrace
Eulerova zpětná
► výstup pro Aŕ = 0.01
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
metoda také není numericky stabilní má sklon systém tlumit
► pro simulace v principu vyhovuje
► nutné řešení systému rovnic v každém kroku může být problém
stabilní metody samozřejmě existují
► příliš komplikované pro naše použití
Silové
interakce
molekul
Kinematika a dynamika pevného tělesa
hmotný bod je příliš zjednodušující abstrakce pevné těleso
► nenulový objem, nepodléhá žádným deformacím k popsání stavu systému jsou nutné další veličiny aktuální orientace (natočení)
► matice 3x3 nebo kvaternion úhlová rychlost
► vektor co
► velikost - rychlost rotace
► směr - osa rotace
matice (tenzor) setrvačnosti
► analogie hmotnosti
► prostorové rozložení hmotnosti
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□     s   4 :
■OQ.O
Matice setrvačnosti a úhlová hybnost
► lineární hybnost P = mv je relativně intuitivní veličina
► úhlová hybnost L = Mco už ne
► jednoduché vyjádření pohybové rovnice
L(ř) =T(ř)
► analogie P(ř) = F(ř)
► pro volně rotující těleso zůstává L konstantní (co ne)
► matice setrvačnosti
► vychází z T = F x r
/ m(ry + rj)
-mrvr
y' x
\
— riLlXly
-mr2ry
-mrxrz \
-TYlTyTz
-mrzrx
*■ závisí na aktuální orientaci více viz http://www. cs. cmu. edu/~baraff/sigcourse/
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□      (5    4 :
Pohybové rovnice pevného tělesa
stavový vektor y = (x, q, P, L)r
► x - poloha
► q - orientace
► P - lineární hybnost (vyjadřuje rychlost)
► L - úhlová hybnost (vyjadřuje úhlovou rychlost)
rovnice
(   -P \
m
F T
úhlovou rychlost co vypočteme
co = qíM^q-^L)) co^ je vnoření co do prostoru kvaternionů
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       <ff ►   4 = ►   < -Š ►
Integrace pohybové rovnice
složitější stabilní metody nestihneme spočítat
dopředná Eulerova metoda nevyhovuje - nestabilní simulace
zpětná Eulerova metoda vyžaduje řešení systému nelineárních rovnic
Yn+l = Yn + Atýn+i
semiimplicitní metoda (Otaduy, 2005)
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
Integrace pohybové rovnice
časovou derivaci ý chápeme jako funkci f (y) Taylorův rozvoj
9f
f(y
n+l>
f(Yn)
dy
(Yn+l -Yn)
Model interakce ni ulekni
Fyzikálně věrné modely
Metody inlegrace
Silové
interakce
moU-kiil
2
Integrace pohybové rovnice
► časovou derivaci ý chápeme jako funkci f (y)
► Taylorův rozvoj
f(Yn+l) = f(Yn) +
(Yn+l-Yn)
Model interakce I molekul
Yn
zanedbáme nelineární členy a dosadíme do zpětné metody
af
I -At
By
(Yn+l " Yn) = Atýn
systém lineárních rovnic pro (yn+i - yn)
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Integrace pohybové rovnice
► časovou derivaci ý chápeme jako funkci f (y)
► Taylorův rozvoj
f(Yn+l) = f(Yn) +
(Yn+l-Yn)
Model interakce I molekul
Yn
zanedbáme nelineární členy a dosadíme do zpětné metody
af
J-Ar
dy
(Yn+l -Yn)= AřÝn
systém lineárních rovnic pro (yn+í - yn) musíme spočítat Jakobián df/dy
► v čase n, nikoli n + 1, proto semiimplicitní metoda
► Otaduy vyjadřuje analyticky - omezené použití
► automatické derivování (příště)
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
■O0.O
Silové interakce molekul
molekulu Ugandu modelujeme jako pevné těleso
► vzájemná poloha atomů se nemění
► hmotnosti atomů koncentrovány v jádrech — matice setrvačnosti
► silová interakce atomu vždy působí v místě jádra
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < -š ►
Silové interakce molekul
molekulu ligandu modelujeme jako pevné těleso
► vzájemná poloha atomů se nemění
► hmotnosti atomů koncentrovány v jádrech — matice setrvačnosti
► silová interakce atomu vždy působí v místě jádra van der Waalsova - LJ potenciál
Flj
12 A 6B
\T 1 3 'yl
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
elektrostatická
Silové
interakce
molekul
□       <ff ►   4 = ►   < -E ►
Silové interakce molekul
molekulu ligandu modelujeme jako pevné těleso
► vzájemná poloha atomů se nemění
► hmotnosti atomů koncentrovány v jádrech — matice setrvačnosti
► silová interakce atomu vždy působí v místě jádra van der Waalsova - LJ potenciál
Flj
12 A 6B
\T 1 3 'yl
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
elektrostatická
Silové
interakce
molekul
n « 104 atomů receptoru, 100 atomů ligandu mxn interakcí nespočítáme lOOOx za vteřinu
□      (5    4 :
van der Waalsova interakce
předvýpočet potenciálu na mřížce
► běžně používáno
v chemickém software
► interpolace příliš vyhladí strmé stěny
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
23/34
van der Waalsova interakce
předvýpočet potenciálu na mřížce
► běžně používáno v chemickém software
► interpolace příliš vyhladí strmé stěny
díky vysokým exponentům relativně krátký dosah můžeme si dovolit ořez
► uvažujeme pouze dvojice atomů o vzájemné vzdálenosti menší než daná konstanta
► typicky 4-8 Ä
vypočítat mxn vzdáleností dvojic atomů je pořád příliš
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
23/34
van der Waalsova interakce
prostor rozdělíme na pravidelné buňky
tak, aby se „největší" atom receptoru vešel do jedné buňky
► při náhodné pozici zasahuje nanejvýš do 8 buněk
hashovací funkce souřadnic buňky struktura připravená před simulací
► projdeme všechny atomy receptoru
► atomy, které padnou (i částečně) do buňky zařadíme do příslušného řádku
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 = ►   < -Š ►
van der Waalsova interakce
prostor rozdělíme na pravidelné buňky
tak, aby se „největší" atom receptoru vešel do jedné buňky
► při náhodné pozici zasahuje nanejvýš do 8 buněk
hashovací funkce souřadnic buňky struktura připravená před simulací
► projdeme všechny atomy receptoru
► atomy, které padnou (i částečně) do buňky zařadíme do příslušného řádku
atom ligandu uměle zvětšíme o vzdálenost ořezu překryje « 10-500 buněk
uvažujeme pouze atomy receptoru v příslušných řádcích
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
van der Waalsova interakce
i po ořezu zůstává příliš mnoho atomů receptoru silové působení (síla i točivý moment) jsou aditivní první derivace jsou také aditivní lze vše počítat paralelně a na závěr sečíst
► round-robin rozdělení atomů receptoru mezi jádra CPU
► statisticky rovnoměrné
technicky používáme MPI
musí běžet na jednom stroji nebo na velmi rychlé síti
► vysoké nároky na latenci
► rozeslání dat, výpočet, sesbírání výsledku za méně než lms
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
Elektrostatická interakce
nízký exponent (2) - dlouhý dosah nelze efektivně použít ořez vypočítáme silové pole na mřížce
► působení na jednotkový náboj
► lze spočítat dopředu
při běhu simulace interpolace pro všechny atomy ligandu
► interpolace ořezává vysoké hodnoty
► v kombinaci s přesnou VdW interakcí to není problém
► extrémy jsou ve stejných místech
► VdW nedovolí tohoto stavu dosáhnout
mřížka je příliš velká
► 2563 ■ 3 ■ 4B ~ 200MB
► adaptivní rozlišení mřížky
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Shrnutí simulace
► off-ľine výpočet
► elektrostatického pole
► hashovací tabulka pro VdW interakce
► řídící simulační vlákno (1 kHz)
► elektrostatické působení na všechny atomy Ugandu
► součet dílčího silového působení VdW sil
► působení zařízení silové zpětné vazby na Ugand (3 nebo 6 DoF)
► integrace pohybové rovnice (systém 13 lineárních rovnic)
► Nx výpočty dílčích VdW sil
► synchronně s řídícím vláknem
► pevně mezi sebe rozdělené atomy receptoru
► každý pro všechny atomy Ugandu
► řízení zařízení silové zpětné vazby (1 kHz)
► asynchronní
► implementace viskoelastického spojení s ligandem
► grafika (25 Hz)
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□     s   4 :
■oq.o
Pohyblivý receptor
model tuhé molekuly neodpovídá realitě
► při nenulové teplotě mění svůj tvar spontánně
► při vzájemné interakci se ovlivňují a mění tvar
spontánní pohyby receptoru umíme napočítat dopředu
~ 1000 a více snímků
hash tabulka pro všechny snímky
► 1000 x 200 kB není problém
► neřešíme, i když umíme přepočítávat změny dostatečně rychle
elektrostatické pole
► 1000 x 50 MB, kdo neplýtvá diskem s námi...
► komprese proměnlivého vektorového pole
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Komprese vektorového pole
Model interakce I molekul
série snímků, každý 3D mřížka 2563 vektorů výrazná časová i prostorová spojitost algoritmus komprese vycházející z audia a videa
sekvence snímků IBBBPBBBP apod.
► I - komprimovaný samostatně
► P - závisí na předchozím I nebo P
► B - interpolace mezi I-P resp. P-P
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
Komprese vektorového pole
I-snímek
analogie komprese audia
► každá složka zvlášť
► logaritmická transformace
► kvantizace na 16 bitů
► průchod 3 D mřížkou definovaným způsobem
lineární prediktor
► předpokládáme, že následující bod je stejný
► zaznamenáváme odchylku
Riceovo kódování odchylek
► i = ndiv2fc, j = n mod 2k
► unární zakódování i, následované 0 a k bity j
► vhodné pro geometrické rozložení
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□     s   4 :
Komprese vektorového pole
B,P snímky
► opět Riceovo kódování odchylek adaptivní mřížka
► strukturu fixujeme pro frameset
► změna mezi framesety může způsobit nespojitosti
► zpětné sjednocení mřížek
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 = ►   < -Š ►
On-line dekomprese
Model interakce I molekul
časově náročná komprese příliš nevadí (off-line)
rychlá dekomprese je kritická
ligand je malý - není třeba celý snímek
aktualizace 1-10 Hz
paralelní implementace
► sady procesů pro I a P/B snímky
► celý I s předstihem (závislosti mezi bloky)
► B/P jen potřebné bloky (podle polohy ligandu)
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 ■= *   < ►
On-line dekomprese
Model interakce I molekul
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
Použili dat ve snimki
Dala pro další snímek: -
□      (5    4 :
Proměnlivý ligand
Model interakce I molekul
změny v tvaru důsledkem interakce s receptorem
► nelze napočítat dopředu řádově menší molekula
► popsat změny tvaru dalšími volnými proměnnými
► zahrnout do on-line simulace
vypsaná diplomová práce
Fyzikálně věrné modely
Metody integrace
Silové
interakce
molekul
□       4 (5 ►   4 = ►   < -Š ►