Algorithms Inspired by Petri Nets in Modeling of Complex Biological Systems

W rozprawie wprowadzone i opisane są nowe narzędzia obliczeniowe z dziedziny bioinformatyki, wydobywania danych oraz badań operacyjnych. Powstałe algorytmy oparto o formalizm sieci Petriego. Sieci Petriego należą do matematycznych języków modelowania, są używane w nauce i technice do reprezentowania oraz analizy skomplikowanych układów. Sieci te mają formę grafu dwudzielnego z dwoma typami wierzchołków: miejscami i tranzycjami, bywają reprezentowane jako macierze. Celem rozprawy było zbadanie możliwości nowego wykorzystania sieci Petriego w biologii obliczeniowej czy bioinformatyce strukturalnej oraz poszerzenie ich zastosowań o modelowanie złożonych systemów biologicznych. Poza sieciami klasycznymi, sieciami z czasem i z priorytetami, użyty został, sformułowany na potrzeby tych badań, nowy typ sieci Petriego – sieci losowo-priorytetowe. W sieciach tych prawdopodobieństwo realizacji tranzycji jest wprost proporcjonalne do jej priorytetu. Taka własność jest konieczna w modelowaniu trajektorii dynamiki molekularnej (MD) rozważanych w części rozprawy. Ponadto typowe sieci priorytetowe zostały zmodyfikowane pod kątem zastosowań w modelowaniu MD.Przy użyciu sieci Petriego stworzono ulepszony komputerowy model układu odpornościowego, który został następnie poddany tzw. analizie t-niezmienników. Wszystkie t-niezmienniki, t-klastry i zbiory MCT zostały w tym modelu zidentyfikowane i określono ich znaczenie biologiczne. Model ma własność CTI – każda tranzycja wchodzi w skład przynajmniej jednego t-niezmiennika, co potwierdza jego poprawność. Do modelu dodano modyfikacje kodujące wybrane zjawiska i choroby: wpływ gorączki, starzenie, infekcja choroby AIDS i Adult-Onset Immunodeficiency Syndrome (AOIS) oraz autyzm. Poprzez odpowiednie symulacje zbadano wpływ tych czynników na zachowanie się nowego modelu układu odpornościowego. Szczególnie pionierskie są przedstawione tu badania związku między gorączką a autyzmem.W rozprawie dyskutowany jest problem zrównoleglenia symulacji dynamiki sieci Petriego. Opracowano i przetestowano nowy algorytm symulacji z wykorzystaniem technologii CUDA/GPU. Testy pokazały, że dla dużych sieci algorytm ten jest znacznie wydajniejszy niż klasyczny.W celu wygenerowania testowych danych przeprowadzono symulacje dynamiki molekularnej (z ang. molecular dynamics MD) dwóch kompleksów białkowych: pyłku trawy z przeciwciałem (alergie) oraz chemokiny MCP-1 z przeciwciałem (autyzm). Wykonano zarówno klasyczne symulacje MD jak i symulacje metodą sterowanej MD. Wyniki potwierdzają potencjalną użyteczność nowych eksperymentalnych metod diagnostycznych opartych na mikroskopii sił atomowych. Własne zbiory danych strukturalnych zostały przeanalizowane w ramach nowo zaproponowanego podejścia do analizy danych opartego o sieci Petriego. Trajektorie MD są na ogół trudne do interpretacji, dlatego też zaproponowano trzy dedykowane algorytmy generowania sieci Petriego na podstawie trajektorii MD nazwane: OPOA (jedno miejsce - jeden atom/aminokwas), OPOC (jedno miejsce - jedna konformacja) oraz CON (algorytm śledzenia kontaktów). Wszystkie trzy algorytmy mogą generować różne sieci, m.in.: klasyczne sieci Petriego, sieci z czasem, sieci priorytetowe oraz losowo-priorytetowe. W rozprawie przedstawiono przykłady wygenerowanych sieci wraz z ich analizą i interpretacją. Taka metoda analizy masywnych danych MD ma szereg zalet, a jak dotąd nigdy nie była używana.Przeprowadzone badania pokazują, że formalizm sieci Petriego może być potężnym narzędziem w bioinformatyce, a szczególności w analizie wyników symulacji dynamiki molekularnej.

In this dissertation new tools for the fields of bioinformatics, data mining and operational research are developed. New algorithms were inspired by Petri nets. Petri nets (PNs) belong to mathematical modeling languages and are used in science and technology. The PNs typically have a form of a bipartite graph with two kinds of nodes: places and transitions, but they may be represented as matrices as well. The aims of the thesis were to exploit the properties and to extend the applications of PN in a new area of modeling of complex biological systems. Apart from the applications of classical, timed and priority-based PNs, a new type of the PNs – the random priority-based Petri nets - has been proposed for the first time. In those networks transitions are fired randomly and the probability of firing is proportional to the priority of the transition. This property is strongly desirable in the molecular dynamics simulations (MD) considered here. Moreover, the priority-based networks were tailored to aimed applications. A new, improved, PN based model of the immune system (IS) has been developed. The t-invariant analysis of the model has been performed. All t-invariant, t-clusters and MCT sets were found, and their biological meanings were identified. The model is correct, since it has the CTI property – every transition is a part of at least one t-invariant. Selected phenomena and diseases were added to the model, such as fever, ageing, infection of the HIV virus, Adult-Onset Immunodeficiency Syndrome disease and Autism Spectrum Disorders. The responses of the IS to such external stimuli were modeled. Particularly pioneering is the study of the correlation between fever and autism. A possibility of parallelization in PN studies is discussed. A novel algorithm for parallel Petri net simulations using the CUDA/GPU technology has been developed and tested. Our algorithm outperforms classical ones when used for very large PNs. In order to generate adequate biological data, sets MD computer simulation study of two complexes were performed: the grass pollen and its antibody and the chemokine MCP-1 and its antibody. Both classical MD and steered MD trajectories were calculated. Simulations substantiated the validity of certain experimental techniques based on Atomic Force Microscopy. Huge sets (>106) of structural data were further classified using our new Petri networks. MD trajectories are difficult to analyze. Therefore, completely new groups of methods of an MD trajectory analysis were formulated. Three algorithms were designed: OPOA (one place one atom/amino acid), OPOC (one place one conformation) and CON (contact algorithm) and their computational time complexity were analyzed. All three algorithms can generate classical, timed, priority-based or random priority-based Petri nets. In the thesis many biological examples of the generated PNs and their interpretations are presented. Such results have never been proposed before.Our studies show that PN formalism can be a powerful tool useful in bioinformatics and, in particular, in MD simulations analysis.