Graph matching, theory and SAT implementation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Mémoires D'étudiants -- Hal-Inria+ Année : 2019

Graph matching, theory and SAT implementation

Résumé

In systems biology, large biochemical reaction networks can either be represented by bipartitegraphs or by systems of ordinary differential equations. Modelers want to determine the existenceof reductions between those reaction networks. Because, it is not possible to decide this existencewith equation systems, a previous thesis [1] focussed on graph structures. A subgraph epimorphism(SEPI) framework was developed and gave results close to biologists’ expectations.Three main difficulties of the SEPI framework have been identified. First, establishing whethertwo models are linked through a SEPI is complex and computationally expensive. Second, thenumber of SEPIs found can be huge, making the analysis of SEPI sets between two given graphsvery difficult for biologists. Finally, some existing SEPIs do not have a biological interpretation.This diploma thesis led to three combined ways to improve the framework. One way consisted toredefine the decision problem into an optimisation problem to restrict the set of solutions. Asecond way was to determine, together with biologists, restrictions on one of the framework’soperations in order to filter irrelevant reductions. Lastly, a preprocessing step has been introduced,consisting of rewriting graphs according to subgraph isomorphism relations. The impact ofthese three combined implementations has been evaluated on models of the BioModels database.Results demonstrated that it contributed to make the SEPI framework more relevant, efficientand functional.
Fichier principal
Vignette du fichier
report.pdf (2.81 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02339907 , version 1 (30-10-2019)

Identifiants

  • HAL Id : hal-02339907 , version 1

Citer

Orianne Bargain. Graph matching, theory and SAT implementation. Bioinformatics [q-bio.QM]. 2019. ⟨hal-02339907⟩
97 Consultations
129 Téléchargements

Partager

Gmail Facebook X LinkedIn More