Masarykova Univerzita Fakulta Informatiky ¤§¨­°´¸Ý Detekce kolizí mezi proteiny Filip Andres Teze disertační práce Školitel: doc. Ing. Jiří Sochor, CSc. V Brně dne: 16. srpna 2007 Podpis školitele: ......................... 1 Úvod Detekce kolizí aplikované na proteinové struktury představují významnou aplikaci těchto technik na specifický problém určování kolizí mezi molekulárními strukturami. Použití metod pro určování kolizí v proteinových strukturách hraje významnou úlohu při snahách biochemiků o nalezení nových léčiv. Proteiny jsou struktury vyskytující se ve všech živých organismech a jsou nepostradatelnou součástí chemických reakcí, jejichž produktem mohou být různé látky, mimo jiné i ty tvořící základ nových medikamentů. V dnešní době stále existuje velké množství nemocí, na něž dosud nebyl vyvinut účinný prostředek. Tento stav je zapřičiněn zejména tím, že provádění chemických reakcí probíhajících uvnitř proteinu je velmi zdlouhavý a náročný proces. Právě při těchto reakcích, kdy mezi sebou reaguje část proteinu a molekula substrátu dopravená dovnitř proteinu, může vzniknout základ nového léčiva. Abychom tento proces dokázali urychlit, musíme umět tyto reakce simulovat pomocí počítačového programu, který eliminuje ty reakce, které by nevedly k uspokojivému výsledku. Ve výsledku tedy biochemik provádí pouze ty reakce, které při simulacích vykazovaly dobré výsledky. Pokud navíc simulace dokáže odhadnout i ,,slabá místa procesu (tím je myšleno například zdržení molekuly substrátu při průchodu dovnitř proteinu), biochemik pak v některých případech dokáže s použitím různých katalyzátorů toto zdržení potlačit. Čím lépe jsme tedy schopni prozkoumat strukturu proteinů a pochopit jejich zákonitosti, tím rychlejší a úspěšnější bude návrh nových léčiv. A právě na simulaci takovýchto procesů uvnitř proteinových struktur je zaměřen náš projekt. Všechny proteiny mají stejnou strukturu, jejímž základem je peptidický řetězec tvořený atomy uhlíku, dusíku a kyslíku. Tyto prvky se v řetězci pravidelně opakují. Na uhlík v tomto řetězci je navázáno takzvané reziduum (označováno též jako aminokyselina). Jednotlivé proteiny se navzájem liší ve složení reziduí a v jejich uspořádání. To ovlivňuje i funkci, kterou daný protein vykonává. Každá molekula je složena z atomů určitých chemických prvků. Každý atom má svůj pevně daný poloměr, jehož velikost je udávána v °Angströmech. Tento poloměr se nazývá van der Waalsův poloměr a platí, že pokud mezi dvěma atomy existuje chemická vazba, pak součet jejich van der Waalsových poloměrů je větší než vzdálenost mezi středy těchto atomů, jak je vidět na obrázku 1. Obrázek 1: Molekula zobrazena pomocí van der Waalsových poloměrů. 1 Mezi atomy molekul působí různé síly, které mají za následek jedinečné prostorové uspořádání molekuly, ve kterém je molekula na své minimální energetické hladině. Důsledkem působení těchto sil a vnějšího prostředí, které se nachází v okolí molekuly, dochází k oscilacím jednotlivých atomů kolem svých stabilních poloh. To má za následek neustálý pohyb celého proteinu. Produkt chemické reakce, ze kterého může být vytvořeno nové léčivo, může vzniknout pouze v určitém místě molekuly proteinu, které se nazývá aktivní místo. Geometricky toto místo představuje dutinu uvnitř proteinu, do které musíme dopravit malou molekulu substrátu. Substrát reaguje s atomy, které se vyskytují v okolí aktivního místa. Ve výsledku pak vzniká produkt a zbytek po reakci. Vzledem k výše zmíněným vlastnostem molekul proteinů byl definován zásadní problém dopravení molekuly substrátu do aktivního místa, aby mohla proběhnout reakce. Na základě toho vznikl projekt, jehož cíle a požadavky na řešení byly stanoveny skupinou biochemiků Přírodovědecké fakulty Masarykovy univerzity vedenou doc. Mgr. Jiřím Damborským, Dr. Základním požadavkem bylo určení cest vedoucích z povrchu molekuly proteinu do aktivního místa. Tyto cesty byly označeny termínem tunely a jejich šířka v jednotlivých místech je definována okolními atomy (viz obrázek 2). Hlavním kritériem pro určení kvality spočteného tunelu je tedy jeho minimální šířka, která určuje velikost molekuly substrátu přicházející do aktivního místa. Součástí projektu je nejen analýza proteinových struktur vedoucí k nalezení tunelů a následná vizualizace dosažených výsledků, ale i detekce kolizí ve spočteném tunelu. vstup do tunelu část molekuly proteinu Obrázek 2: Část molekuly proteinu se spočteným tunelem. Díky neustálému pohybu celé molekuly nestačí jako výsledek analýzy pouze jeden spočtený tunel, ale výstupem je sada tunelů, z nichž si biochemik vybere ten s nejlepšími vlastnostmi (toto zpracování spočtených tunelů je třeba provádět ručně, protože existuje řada chemických vlastností tunelů, které nejsou algoritmicky zachytitelné). Vlastnosti a chování tunelů významně ovlivňuje i výše zmiňovaný pohyb celé molekuly. Důsledkem toho je změna tvaru a šířky tunelu v čase. Některé tunely 2 se mohou dočasně nebo trvale zavřít, což je nutné při analýze vzít v úvahu. Na obrázku 3 je znázorněna molekula proteinu společně s několika spočtenými tunely. Obrázek 3: Zobrazení molekuly proteinu a spočtených tunelů vedoucích z aktivního místa. Následující obrázek 4 ilustruje situaci, ve které máme dvě molekuly substrátu a protein se spočteným tunelem. Chceme určit, jestli některá z těchto molekul může projít tunelem až k aktivnímu místu proteinu. Pokud se na tento problém díváme ze statického pohledu, je vidět, že substrát A (v červené kružnici) tímto tunelem bez problémů projde a substrát B (v zelené kružnici) je příliš velký. V tomto druhém případě bychom tedy označili tento tunel jako nevhodný pro průchod substrátu B. Pokud se ale na probém podíváme z dynamického hlediska, může nastat situace, kdy se na příslušných místech tunel rozevře natolik, že umožní substrátu B průchod až k aktivnímu místu (za přiměřeně dlouhou dobu). Tím by se tento tunel stal vhodným kandidátem pro simulaci tohoto jevu ve zkumavce a umožnil by tak chemickou reakci, která by jinak nemusela vůbec proběhnout. Kolizní systém, který by byl aplikovatelný na tento problém, se musí vypořádat nejen s pohyby molekuly proteinu, ale rovněž s dynamicky se měnící molekulou substrátu, která podléhá stejným zákonitostem jako celý protein. Při určování kolize molekuly substrátu s tunelem, kterým molekula prochází, může významně pomoci fakt, že tunel je definován jako sada po sobě jdoucích tetrahedronů. Ty vznikly při detekci tunelů, která funguje na principu Delaunayho tetrahedrizace. Tyto tetrahedrony definují hranici tunelu, proto se při detekci kolizí můžeme omezit pouze na prostor vymezený těmito tetrahedrony. Hlavním problémem, který je nutné v nově navrženém systému pro detekci kolizí řešit, je určení,zda substrát při průchodu tunelem narazí na místo, které se okolním vlivem zúžilo tak, že v daném momentu substrát nemůže tunelem projít dál k ak- 3 substrát A substrát B Obrázek 4: Nahoře: tunel uvnitř části molekuly proteinu, dole: dvě molekuly sub- strátu. tivnímu místu. Proto je potřeba určit, zda se toto místo někdy v blízké budoucnosti rozšíří natolik, že malá molekula bude moci pokračovat dále. Pokud by se takováto detekce podařila uspokojivě vyřešit, zamezilo by to situacím, ve kterých biochemik odstraní z výběru potenciálně použitelných tunelů i ty, které by mohly být ty nej- kvalitnější. Cílem mé práce na tomto projektu je tedy na základě uvedených skutečností navrhnout kolizní systém, který bude vyhovovat všem výše zmíněným požadavkům. Jeho nasazení pak umožní rychlejší a kvalitnější určování těch nejlepších tunelů pro vstup konkrétní molekuly substrátu. Součástí projektu je nejen návrh a implementace nových technik, ale rovněž intenzivní testování jejich vhodnosti skupinou biochemiků pro použití při syntéze nových léčiv. 4 2 Současný stav řešené problematiky Detekce kolizí je hledání těch objektů scény, které mají v daném časovém okamžiku neprázdný průnik. Naivním řešením daného problému je testování všech párů objektů scény na společný průsečík. Protože tento přístup je příliš pomalý (O(n2)), hledají se metody, které by kolizní situaci ve scéně vyhodnotily rychleji. Před popisem samotných technik pro detekci kolizí vysvětlíme základní pojmy týkající se této oblasti. 2.1 Základní pojmy * Spojitá detekce kolizí ­ problém zjištění kolize v každém okamžiku spojitého časového intervalu. * Diskrétní detekce kolizí ­ problém zjištění kolize v sekvenci časových oka- mžiků. * Časová koherence ­ časová koherence je míra změny scény v průběhu času, mnoho algoritmů urychluje svůj výpočet tím, že používá výsledky z předchozích snímků. * Časový alias ­ situace, ke které může dojít při diskrétní detekci kolizí, pokud má objekt příliš vysokou rychlost vzhledem k jemnosti vzorkování časového intervalu. V takovém případě nemůže algoritmus detekovat kolizi, ke které došlo mezi dvěma po sobě jdoucími snímky. Protože našimi vstupními daty jsou výsledky výpočtu molekulové dynamiky vzorkované v pravidelných intervalech, budou dále popsány pouze algoritmy pro detekcí kolizí v diskrétních okamžicích. V současné době existuje několik rozdílných přístupů k řešení problému detekce kolizí v dynamicky se měnících scénách. Tyto techniky budou v dalším textu podrobněji vysvětleny. 2.2 Hierarchie obalových těles První skupinou jsou algoritmy založené na detekci kolizí pomocí hierarchií obalových těles. Tyto algoritmy jsou velice často používány a bylo prozkoumáno jejich chování s více druhy známých obalových těles. Detekce kolizí probíhá zpravidla dvoufázově: * v první fázi (broad phase) se vyloučí ty páry objektů scény, které spolu nemohou kolidovat * ve druhé fázi (narrow phase) se zjistí kolize mezi zbývajícími páry objektů Pro první fázi se během předzpracování vytvoří strom obsahující objekty ve scéně, shlukované ve vyšších úrovních stromu podle jejich vzájemné polohy. Výpočet kolizí ve druhé fázi vyžaduje vytvoření podobného stromu pro každý objekt. Vnitřní uzly všech stromů reprezentují příslušné obalové těleso pro daný podstrom. Toto obalové těleso lze vytvořit dvěma způsoby ­ jako tzv. wrapped hierarchy, ve které vnitřní uzel 5 obsahuje obalové těleso objektů jeho podstromu nebo layered hierarchy, kde vnitřní uzel obsahuje obalové těleso všech obalových těles svých potomků (viz. obr. 5). Výhodou prvního způsobu je těsnější obalení příslušných objektů, nevýhodou je však složitější výpočet. Obrázek 5: Vlevo wrapped, vpravo layered hierarchy (obkresleno podle [3]) Při použití hierarchií obalových těles pro detekci kolizí v dynamických scénách je zapotřebí zajistit dostatečně rychlou úpravu hierarchie tak, aby byla včas připravena pro použití v dalším požadovaném časovém okamžiku. Toho může být dosaženo dvěma rozdílnými způsoby: přebudováním hierarchie (rebuilding) nebo přepočítáním obalových těles v uzlech stromů (refitting). Přetvoření hierarchie slibuje rychlejší detekci, bohužel je výpočet náročnější než přepočítání obalových těles (van den Bergen [10] pozoroval desetkrát rychlejší úpravu hierarchie při použití přepočítání obalů oproti prvnímu přístupu). Nevýhodou přepočítání obalů je zvětšení obalových těles, ke kterému může dojít. 2.2.1 Řetízky koulí V kontextu detekce kolizí mezi proteinem a substrátem se jeví zajímavým algoritmus Guibase a spol. ([3]). Jejich algoritmus pracuje s objekty, které lze reprezentovat jako řetězec koulí s omezením na poloměr jednotlivých koulí (mj. páteř libovolného proteinu tuto podmínku splňuje). Autoři dále připouštějí průnik pouze u sousedních koulí v rámci jednoho řetízku. Nad objekty s těmito vlastnostmi je vytvořena wrapped hierarchie obalových koulí. V průběhu detekce se při rozhodování, ve kterém stromu se má sestoupit na nižší úroveň, používá heuristika, podle které se sestupuje v tom stromu, jehož aktuálně prohlížený uzel, tj. obalová koule, obsahuje více elementárních koulí. Při použití této heuristiky platí, že detekce je ve složitostní třídě O(n 3 n) v trojrozměrném prostoru. Využití zmíněného alogritmu pro detekci kolizí mezi proteinem a substrátem je omezeno zejména tím, že protein se nedá modelovat jako řetízek koulí ­ k páteři proteinu jsou navázány boční řetězce tvořené rezidui různých aminokyselin. Druhou nevýhodou algoritmu je drahá úprava obalových koulí v uzlech stromu, pokud dojde 6 k deformaci řetízku. Tato úprava trvá déle zejména pro řetízky, které jsou stočené sami do sebe, což je právě případ proteinů, se kterými pracujeme. 2.3 Dělení prostoru Hierarchie obalových těles je metoda, která urychluje výpočet detekce kolizí tím, že rekurzivně dělí objekty tak, aby bylo možné včas vyloučit ty části objektů, které se nemohou protnout. Podobný přístup se dá použít i tím způsobem, že prostor, ve kterém se objekt nachází, se rozdělí na menší části a následně se hledají kolize pouze mezi těmi částmi objektů, které okupují stejný prostor. Algoritmy, které pro urychlení výpočtu používají dělení prostoru, zpravidla využívají buď uniformní dělení prostoru do mřížky (např. [9]) nebo nějakou hierarchickou strukturu (např. [6], [1]). Podobně jako u algoritmů využívajících obalová tělesa, i tento přístup vyžaduje udržování informace o poloze objektů scény v každém snímku. V následujícím textu budou na příkladech představeny dva přístupy, které toto v příznivém čase umožňují. 2.3.1 BucketTree algoritmus BucketTree algoritmus ([1]) řeší detekci kolizí dvou objektů scény (narrow phase algoritmus), neklade žádná omezení na topologii objektů. Pro každý objekt je během předzpracování vytvořen oktalový strom, kořen stromu je tvořen osově orientovanou obalovou krychlí objektu, v listech je množina primitiv, která zasahují do dané části prostoru. Obrázek 6: Reprezentace oktalového stromu u BucketTree algoritmu (převzato z [1]) 7 Rychlá úprava struktury je zajištěna pomocí její implementace: všechna primitiva jsou zatříděna ve třech seznamech podle souřadnic v osách x, y, a z. Listy stromu jsou ukazatele na první prvek seznamu, který přísluší do daného listu. Při přechodu k dalšímu snímku animace se na každý ze seznamů použije třídicí algoritmus insertion sort. Za předpokladu, že primitiva mají velkou časovou koherenci mezi snímky, tento algoritmus běží s očekávanou složitostí O(n). Celkový čas potřebný k údržbě datových struktur mezi snímky je lineární vůči počtu primitiv daného objektu. 2.3.2 Algoritmus prostorového hašování Jiný přístup využívají Teschner a spol. [7] ve svém algoritmu pro deformovatelné objekty, které se skládají ze čtyřstěnů. Jejich algoritmus dělí prostor do buněk o stejném objemu. Každé buňce je přiřazena hodnota spočtená z jejích souřadnic pomocí hašovací funkce. Detekce kolizí probíhá tak, že se nejprve každý vrchol každého čtyřstěnu zařadí do příslušné buňky (tj. záznamu v hašovací tabulce). Ve druhém kroku se testuje poloha každého čtyřstěnu vůči vrcholům v buňkách, které protíná. Ke kolizi došlo, pokud se našel vrchol patřící jinému čtyřstěnu uvnitř právě testovaného čtyřstěnu. Očekávaná složitost úpravy je O(n), složitost je ovlivněna kvalitou hašovací funkce a velikostí buněk vůči čtyřstěnům. 2.4 Detekce kolizí v prostoru obrazu Se zvyšujícím se výkonem běžných grafických karet získává v posledních letech na popularitě přístup, který detekuje kolize ve scéně pomocí projekce objektů na plochu, ve které se kolize zjišťují. Výhodami tohoto přístupu jsou zejména: * možnost přesunout výpočet na grafickou kartu * není potřeba žádné předzpracování * není nutno zvlášť ošetřovat objekty s nestandardní topologií Naopak nevýhodou tohoto přístupu je nutnost během detekce rasterizovat všechna primitiva a rozlišení obrazu, které omezuje přesnost algoritmu (navíc málokterá paměť hloubky umožňuje pracovat s IEEE-754 desetinnými čísly). Pokud je algoritmus implementován na GPU, dochází ke zpomalení výpočtu vzhledem k nutnosti vyčíst výsledek z grafické karty zpět do hlavní paměti. 2.4.1 CULLIDE Algoritmus CULLIDE ([2]) je metoda, která využívá schopností moderních grafických karet (OpenGL rozšíření GL NV occlusion query) k tomu, aby zmenšila počet párů primitiv, která podstupují vlastní test na průnik (na CPU). Algoritmus pracuje ve třech hlavních krocích, z nichž první dva probíhají na GPU a poslední na CPU. V prvním kroku se odstřelí ty objekty, které nemohou kolidovat s ostatními, ve druhém kroku se zbývající objekty rozdělí na menší množiny primitiv a provede 8 Obrázek 7: Ilustrace pozorování 1 (převzato z [2]) se odstřel těch množin, které nemohou kolidovat s dalšími množinami. Ve třetím kroku se provede detekce kolizí mezi zbývajícími primitivy. Rozhodnutí o tom, jestli objekt (podobjekt) postoupí do další fáze zpracování nebo bude zahozen, záleží na jeho příslušnosti do množiny potenciálně kolidujících objektů (PCS ­ potentially colliding set). Na začátku příslušné fáze jsou všechny objekty v PCS, rozhodnutí o vyřazení objektu z PCS je založeno na následujícím pozorování: Pozorování 1: Pokud existuje směr pohledu takový, že všechny fragmenty vzniklé při rasterizaci objektu O jsou před (mají menší hodnotu Z v paměti hloubky) fragmenty vzniklými rasterizací objektů množiny S, pak objekt O nekoliduje s žádným objektem z množiny S (viz. obr. 7). Podmínka uvedená v předchozím pozorování je postačující, nikoliv však nutná. Tento směr nemusí vůbec existovat, přesto mohou mít dva objekty prázdný průnik (např. dvě sféry se stejným středem a různými poloměry). Na druhou stranu, přestože v námi vybraném směru podmínka splněna není (směr 2 na obr. 7), objekty mohou být disjunktní. V algoritmu CULLIDE jsou za směry pohledu vybrány směry os prostoru. Prořezání PCS probíhá pomocí dvouprůchodového algoritmu se složitostí O(n). V prvním průchodu je objekt porovnán se všemi objekty vykreslenými před ním, ve druhém průchodu se pořadí vykreslování obrátí. Díky tomu je objekt porovnán se všemi ostatními objekty v PCS. Testování v každém průchodu probíhá tak, že nejprve se objekt vykreslí bez zápisu do paměti hloubky, ale se spuštěným testem hloubky s funkcí GL GEQUAL. Pokud nebyl vykreslen žádný pixel (zjistí se pomocí funkce grafické karty occlusion query), pak je objekt přede všemi objekty vykreslenými před ním. Poté se objekt vykreslí ještě jednou, tentokrát už se zápisem do paměti hloubky. Pokud je objekt přede všemi ostatními objekty v obou průchodech, může se vyjmout z PCS, protože do ní nepatří. 9 2.5 Stochastické metody V informatice jsou často využívány náhodnostní algoritmy, které umožňují výrazně snížit očekávaný čas běhu algoritmu za cenu snížené přesnosti. Pro použití při detekcích kolizí je tento přístup ospravedlněn tím, že kvalitní vjem u interaktivních 3D aplikací je zaručen zejména plynulostí zobrazování. Kromě toho se v současnosti mnoho objektů modeluje pomocí trojúhelníkových sítí aproximujících přesný povrch objektů. 2.5.1 ABD-stromy ABD-stromy ([5]) jsou stromy hierarchie obalových těles, kde je každý uzel obohacen o informaci o pravděpodobnosti kolize daného uzlu. Tato informace je odhadnuta v průběhu předzpracování pomocí celkové plochy polygonů obsažených v daném uzlu. Výhodou ABD-stromů je možnost ovlivnit počet testovaných uzlů a tím i přesnost a rychlost detekce pomocí číselných parametrů detekce, které se mohou snímek od snímku měnit. Obrázek 8: Kolize dvou uzlů ABD-stromů (převzato z [5]) Odhad kolize dvou uzlů ABD-stromů probíhá tak, že se objem průniku těchto uzlů rozdělí do pravidelné mřížky a odhaduje se počet buněk mřížky, ve kterých by mohlo dojít ke kolizi (viz. obr 8). Výsledný algoritmus detekce kolizí pomocí ABD-stromů vznikl úpravou algoritmu pro detekci pomocí hierarchií obálek: 1. traverse(A, B) { 2. priority queue q, k = 0 3. q.insert(A, B, 1) 4. while (!q.empty()) { 5. A, B = q.pop() 6. for (successorsA[i], B[j]) { 7. p = computeProb(A[i], B[j]) 8. if (p pmin) 9. if (++k kmin) return "Collision" 10. if (p > 0) q.insert(A[i], B[j], p) 11. } 12. } 13. return "No collision" 14. } 10 Celý algortimus je parametrizován dvěma hodnotami ­ pmin, kmin, díky kterým se dá upravovat rychlost a přesnost algoritmu. Parametr pmin je práh, který určuje minimální pravděpodobnost, se kterou je buňka považována za kolizní, kmin je minimální počet kolizních buněk, které musí být nalezeny, aby byla kolize detekována. Pokud nebyla nalezena kolize, pokračuje se ve výpočtu tou dvojicí potomků obou uzlů, která má největší pravděpodobnost kolize. 2.5.2 Detekce kolizí pomocí náhodného vzorkování Jde o velice přímočarou stochastickou metodu. Na počátku se náhodně vyberou vzorky (tj. páry primitiv) z potenciálně kolidujících objektů a určí se jejich kolizní situace. V dalších snímcích animace se sledují pouze vybrané páry a na základě jejich pozice se určuje, zda nastala kolize. Tato metoda je citlivá na kvalitu vzorkování, pro kvalitní výsledky je potřeba vybírat vzorky ze všech částí objektů. Pro pohybující se a deformující se objekty se využívá časové koherence, kdy se vzorky znovu použijí v dalších snímcích, pokud během předchozího testu byly k sobě dostatečně blízko. 2.6 Využití pole vzdáleností Pole vzdáleností je funkce, která každému bodu prostoru přiřazuje skalární hodnotu ­ vzdálenost bodu od objektu. Pole implicitně definuje povrch objektu jako množinu bodů s hodnotou 0. Pole může být znaménkové, v tom případě body se zápornou hodnotou představují vnitřek objektu. Pomocí pole se dají snadno reprezentovat objekty s libovolnou topologií. Obrázek 9: Tři řezy pole vzdáleností Šťastného Buddhy (převzato z [8]) 11 Pro reprezentaci pole vzdáleností se využívají různé prostorové struktury ­ uniformní mřížka, oktalový strom, BSP strom. Při použití mřížky jsou dotazy na vzdálenost vyhodnoceny v čase O(1) a dá se snadno rekonstruovat zakřivený povrch. Naproti tomu má mřížka vysoké paměťové nároky a předem danou přesnost, s jakou zachycuje povrch objektu. Z těchto důvodů se využívají adaptivní datové struktury umožňující přesnější reprezentaci oblasti zájmu. Detekce kolizí mezi objekty, které mají předpočítané pole vzdáleností, je velmi jednoduchá ­ pro každý bod jednoho objektu zjistíme jeho hodnotu v poli objektu druhého. Pokud je tato hodnota záporná, došlo ke kolizi. Stejně jednoduše lze zjistit míru vzdálenosti/zanoření bodu vůči druhému objektu. Protože pole nebývá dáno spojitě, ale často je navzorkováno v bodech, upravuje se podmínka kolize tak, že kolize nastává, pokud testovaný bod má vzdálenost ve druhém poli menší než předem dané . Využití pole vzdáleností pro detekci kolizí deformovatelných objektů je ovlivněno nutností přepočítat pole při každé deformaci daného objektu. 12 3 Záměr disertace Cílem mé disertační práce je vytvoření nových přístupů k detekcím kolizí v proteinových strukturách. Hlavním tématem pak bude zejména detekce kolizí v dynamicky se měnících strukturách, jakými jsou právě molekuly se spočtenými tunely. 3.1 Způsob řešení V následujících letech mého doktorského studia bych se chtěl zaměřit na využití a modifikaci stávajících technik pro detekci kolizí mezi molekulami proteinů měnících v čase svoje prostorové uspořádání a na jejich implementaci. Dále bych se chtěl věnovat vytváření nových technik, které by plně vyhovovaly specifickým podmínkám vyskytujícím se v proteinových strukturách. 3.2 Očekávané výsledky Výsledky měho výzkumu v této oblasti by měly být následující: * Aplikace umožňující analýzu tunelů v proteinech pomocí prozkoumaných metod detekce kolizí. * Sada článků věnujících se této problematice. Formou těchto článků bych rád prezentoval dosažené výsledky na mezinárodních konferencích. 3.3 Časový harmonogram 1. Rok 2007/08 ­ návrh a implementace nových technik pro detekci kolizí v molekulách proteinů, sepsání článků na toto téma a jejich prezentace na konferencích, obhájení tezí disertační práce a státní doktorská zkouška. 2. Rok 2008/09 ­ pokračování v práci na zvoleném tématu, publikace výsledků, začátek sestavování disertační práce. 3. Rok 2009/10 ­ dokončení a obhájení disertační práce. 13 Reference [1] F. Ganovelli, J. Dingliana, and C. O'Sullivan. Buckettree: Improving collision detection between deformable objects. [2] Naga K. Govindaraju, Stephane Redon, Ming C. Lin, and Dinesh Manocha. Cullide: interactive collision detection between complex models in large environments using graphics hardware. In HWWS '03: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, pages 2532, Aire-la-Ville, Switzerland, Switzerland, 2003. Eurographics Association. [3] Leonidas Guibas, An Nguyen, Daniel Russel, and Li Zhang. Collision detection for deforming necklaces. In SCG '02: Proceedings of the eighteenth annual symposium on Computational geometry, pages 33­42, New York, NY, USA, 2002. ACM Press. [4] Ladislav Kavan. Real-Time Skeletal Animation. PhD thesis, Czech Technical University, 2007. [5] J. Klein and G. Zachmann. Adb-trees: Controlling the error of time-critical collision detection, 2003. [6] Stan Melax. Dynamic plane shifting BSP traversal. In Graphics Interface, pages 213­220, 2000. [7] M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, and M. Gross. Optimized spatial hashing for collision detection of deformable objects, 2003. [8] M. Teschner, S. Kimmerle, G. Zachmann, B. Heidelberger, Laks Raghupathi, A. Fuhrmann, Marie-Paule Cani, Fran¸cois Faure, N. Magnetat-Thalmann, and W. Strasser. Collision detection for deformable objects. In Eurographics Stateof-the-Art Report (EG-STAR), pages 119­139. Eurographics Association, Eurographics Association, 2004. [9] Greg Turk. Interactive collision detection for molecular graphics. Technical report, University of North Carolina at Chapel Hill, Chapel Hill, NC, USA, 1990. [10] Gino van den Bergen. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools: JGT, 2(4):1­14, 1997. 14 4 Souhrnná zpráva o dosavadních výsledcích studia V dosavadní práci na řešení tohoto projektu jsem byl spolutvůrcem nově vznikající aplikace pro vizualizaci molekulárních struktur a základní analýzu proteinů vedoucí k nalezení tunelů. Veškeré možnosti, které aplikace umožňuje, byly implementovány po dohodě s biochemickou skupinou vedenou doc. Mgr. Jiřím Damborským, Dr. Tato aplikace vznikla již v průběhu magisterského studia a výsledkem byla diplomová práce. Po přijetí na doktorský stupeň studia jsem pokračoval v rozvoji stávající aplikace a implementaci technik nutných pro další vývoj výzkumu. Zároveň jsem se intenzivně věnoval studiu různých kolizních systémů, které by byly využitelné k našim účelům. Na celý projekt jsme od ledna 2007 získali tříletý grant GAČR (201/07/0927), na jehož řešení se od té doby podílím. Výsledkem spolupráce s Mgr. Barborou Kozlíkovou je program vizualizující tunelů v molekulách proteinů a článek, který byl přijat na konferenci ACM Afrigraph 2007. Tomuto problému jsem se věnoval z důvodu nutnosti nalezení dostatečně kvalitních vizualizačních technik pro práci s tunely před tím, než dojde k implementaci detekčních technik do stávající aplikace. Výsledky určení kolizních oblastí je totiž třeba příslušným způsobem biochemikovi zobrazit, což lze pouze v kombinaci s vizualizací příslušného tunelu. V průběhu studia jsem vedl cvičení předmětu Základy počítačové grafiky. V současné době vedu diplomovou práci věnující se problematice, která je spojena se zadáním našeho projektu. V letošním roce se zúčastním konference Eurographics 2007 a byl jsem přítomen na dvou schůzkách Centra počítačové grafiky, jehož členem je i Laboratoř interakce člověka s počítačem na Fakultě informatiky Masarykovy univerzity. 15