Skip to Main content Skip to Navigation
Master thesis

Graph matching, theory and SAT implementation

Abstract : 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.
Document type :
Master thesis
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download
Contributor : Orianne Bargain Connect in order to contact the contributor
Submitted on : Wednesday, October 30, 2019 - 3:40:03 PM
Last modification on : Friday, February 4, 2022 - 3:12:33 AM


Files produced by the author(s)


  • HAL Id : hal-02339907, version 1


Orianne Bargain. Graph matching, theory and SAT implementation. Bioinformatics [q-bio.QM]. 2019. ⟨hal-02339907⟩



Record views


Files downloads