Orienting biochemical reactions in metabolic pathways and networks

id182921   ORIENTING BIOCHEMICAL REACTIONS IN METABOLIC PATHWAYS AND NETWORKS ZEPHYR SERRET VERBIST Thesis supervisor: GABRIELVALIENTEFERUGLIO(DepartmentofComputerScience) Degree:BachelorDegreeinInformaticsEngineering(Computing) Bachelor's thesis Facultat d'Informàtica de Barcelona (FIB) Universitat Politècnica de Catalunya (UPC) - BarcelonaTech  Table of contents 1 Introduction and contextualization 8 1.1 Terms and concepts used in this study ..................... 8 1.1.1 Hypergraphs ............................. 8 1.1.2 Metabolic Pathway .......................... 8 1.1.3 Internal and external vertices ..................... 9 1.2 Problem definition .............................. 10 1.3 Stakeholders .................................. 10 2 Justification 11 3 Scope 11 3.1 Objective ................................... 11 3.2 Sub-objectives ................................. 11 3.3 Identification of Functional and Non-Functional Requirements: ....... 12 3.3.1 Functional requirements ....................... 12 3.3.2 Non-Functional Requirements: .................... 12 3.4 Risk assessment ................................ 12 4 Methodology: Kanban for Solo Development 13 4.1 Adapting Kanban for Solo Development: ................... 13 4.2 Benefits of Kanban for Solo Development: .................. 14 5 Time planning 14 5.1 Task descriptions ............................... 14 5.1.1 T1 - Project Management ...................... 14 5.1.2 T2 - Design of the ILP Model .................... 15 5.1.3 T3 - App Development: ....................... 15 5.1.4 T4 - Implicit Task - Project Documentation: ............. 16 5.1.5 T5 - Preparation for the oral defence ................. 16 5.2 Task duration estimates ............................ 16 5.3 Resources ................................... 19 5.3.1 Human Resources: .......................... 19 5.3.2 Material Resources: ......................... 19 5.4 Risk Management: Obstacles and alternative plans .............. 22 5.4.1 Project Timeline ........................... 22 5.4.2 Computational power ........................ 22 5.4.3 Integration Challenges ........................ 22 5.4.4 Inexperience with ILP: ........................ 22 6 Budget 23 6.1 Staff costs ................................... 23 6.2 Generic costs ................................. 25 6.3 Budget Deviations ............................... 25 6.3.1 Contingency ............................. 25 6.3.2 Incidental Costs ........................... 25 6.4 Management Control ............................. 26 6.4.1 Metrics for Budget Adherence: .................... 26 6.4.2 Adaptation for Budget Control .................... 26 6.5 Total Budget .................................. 26 1 7 Sustainability report 26 7.1 Economic dimenstion ............................. 27 7.2 Environmental Dimension .......................... 27 7.3 Social Dimension ............................... 28 8 Creating an effective AMPL model 28 8.1 Understanding the Basics of AMPL ..................... 29 8.2 Desired inputs/outputs ............................. 29 8.3 Explaining our models ............................ 30 8.3.1 First prototype ............................ 30 8.3.2 Models Developed by the Professor and His Colleagues ....... 32 8.4 Initial Benchmarking ............................. 34 8.5 Creating and optimizing our final model ................... 35 8.6 Mathematical proof of the final model .................... 37 8.6.1 Introduction of Predicates and Functions: .............. 37 8.6.2 Obtaining is internal from has outgoing and has incoming ..... 37 8.6.3 Obtaining has outgoing from the X and Y sets ............ 40 8.6.4 Obtaining has incoming from the X and Y sets ........... 41 8.6.5 Additional Constraints: forcing internal ............... 43 8.6.6 Additional Constraints: forcing external ............... 43 8.6.7 Additional Constraints: respecting the invertability of hyperedges . . 44 8.6.8 Comparing the mathematical correctness of Model A and Serret’s models 44 8.7 Final Benchmark and conclusions ...................... 44 9 Database Integration 47 9.1 Acknowledgment of Attempted Integration using bioservices ........ 47 9.2 REST API Data Mapping: Needs and Retrievals ............... 47 9.3 Equation Discovery: Unveiling Reaction Formulas and Compound IDs Across Varied Endpoints ............................... 49 10 Navigating the Design and User Experience of our Python GUI 53 10.1 Installing and Running the GUI ........................ 53 10.2 Pathway Selector ............................... 54 10.3 Pathway Solver/Visualizer .......................... 56 10.4 Benchmark View ............................... 63 11 Program architecture and Data Structures 64 11.1 Design Choices and Development Approach ................. 64 11.2 File Organization ............................... 65 11.2.1 Entry Point of the Application .................... 65 11.2.2 Views ................................. 65 11.2.3 Models ................................ 65 11.2.4 Utils ................................. 65 11.2.5 Dynamically Generated Files ..................... 66 11.3 Classes and Data Structures .......................... 66 11.3.1 KEGGIntegration .......................... 66 11.3.2 GridUtil ............................... 67 11.3.3 Pathway selector ........................... 68 11.3.4 Pathway view ............................ 69 11.3.5 Benchmark view ........................... 70 12 Conclusions and final thoughts 71 12.1 Summary of Contributions .......................... 71 2 12.2 Limitations and Challenges .......................... 72 12.3 Future Research Directions .......................... 72 12.4 Final Thoughts ................................ 72 List of Figures 1 Example of a directed hypergraph H=(V,E)................. 8 2 Sphingolipid metabolism. Source: KEGG entry hsa map00600 ....... 9 3 Example of the orientation of a hypergraph and its impact on its internal and external nodes. ................................ 10 4 Gantt Diagram. Source : own compilation .................. 18 5 The model file of the first prototype ...................... 32 6 AMPL Model - Model A ........................... 33 7 AMPL Model - Model B ........................... 34 8 Serret’s DualImply Model (with extra restrictions) .............. 36 9 Strong AMPL rules used to define has internali............... 39 10 Serret’s UniImply model ........................... 45 11 Integration attempt using bioservices ..................... 47 12 Obtaining compound ids from the human readable equation ......... 52 13 Pathway Selector - User view ......................... 54 14 Pathway Selector - Labeled Features ..................... 54 15 Show Image - Image corresponding to the entry ’map00010’ ......... 55 16 Feature tooltips - tooltip of the show image button .............. 56 17 Warning Message on Updating Dataset .................... 56 18 Solver/Visualizer - User View ......................... 57 19 Output for map00908 - Zeatin biosynthesis .................. 58 20 Solver-Visualizer - Saving the result in a file ................. 59 21 An example of how to represent a hypergraph using a graph ......... 59 22 Solver-Visualizer - Visualizing a oriented pathway .............. 60 23 Solver-Visualizer - Visualizing a oriented pathway, with labels toggled off . . 60 24 Solver-Visualizer - The ’Extra restrictions’ menu ............... 61 25 Solver-Visualizer - Adding items to a list of a restriction ........... 61 26 Solver-Visualizer - Items added to a list of a restriction ............ 62 27 Solver-Visualizer - Item removed from a list of restrictions .......... 62 28 Benchmark View - User Interface ....................... 63 29 Benchmark View - Completed Benchmarks ................. 63 30 Benchmark View - Expanded Benchmarks .................. 64 List of Tables 1 Task Duration and dependencies ....................... 16 2 Table of requirements (Human and Material) corresponding to each task . . . 21 3 Estimated Staff Costs per hour (1736 working hours per year [1]) ...... 23 4 Personnel Cost per Activity (PCA) based on the costs defined in table 3 . . . 24 5 Amortization of physical resources ...................... 25 6 Incidental Costs ................................ 26 7 Final Budget ................................. 27 8 Initial Benchmark ............................... 35 9 Truth table of the equivalence of is internal and the system of inequations . . 38 10 Optimizing is internal by removing a redundant inequation ......... 39 3 11 Truth table of the ’∧’ operator and the construction a+b=2......... 43 12 Truth table of the negated ’∧’ operator and the construction toNum(a)+ toNum(b)<2................................. 43 13 Final Benchmark ............................... 46 4 Abstract This study offers a comprehensive exploration into the orientation of hypergraphs within metabolistic pathways. Our focus was on formulating an AMPL model, enabling researchers to attain effective solutions through ILP optimization. Key contributions of our work encompass: • Development of a logically robust model for solving hyperedge orientation in metabolistic pathways. • Benchmarking the model against alternatives, identifying strengths, weaknesses, and optimal application scenarios. •Introduction of additional constraints deemed significant in metabolistic pathways, including: 1. Prevention of inversion in specific reactions. 2. Identification of certain vertices as internal. 3. Identification of certain vertices as external. Additionally, this paper introduces a user-friendly GUI tool that facilitates model exploration, result analysis, constraint addition, and pathway orientation in real-world scenarios. 5 Abstract Este estudio ofrece una exploraci´ on integral sobre la orientaci´ on de hipergrafos en el contexto de las v´ ıas metab´ olicas. Nuestro enfoque se centr ´ o en la formulaci ´ on de un modelo AMPL, permitiendo a los investigadores obtener soluciones efectivas mediante la optimizaci ´ on de ILP. Las principales contribuciones de nuestro trabajo abarcan: • Desarrollo de un modelo l ´ ogicamente robusto para resolver la orientaci ´ on de hiperedges en v´ ıas metab´ olicas. • Evaluaci ´ on comparativa del modelo con alternativas, identificando fortalezas, debilidades y escenarios de aplicaci´ on ´ optimos. •Introducci´ on de restricciones adicionales consideradas significativas en las v´ ıas metab´ olicas, incluyendo: 1. Prevenci´ on de la inversi´ on en reacciones espec´ ıficas. 2. Identificaci´ on de ciertos v´ ertices como internos. 3. Identificaci´ on de ciertos v´ ertices como externos. Adem´ as, este art´ ıculo presenta una herramienta de interfaz gr´ afica de usuario (GUI) amigable que facilita la exploraci´ on del modelo, el an´ alisis de resultados, la adici´ on de restricciones y la orientaci´ on de v´ ıas metab´ olicas en escenarios del mundo real. 6 Abstract Aquest estudi ofereix una exploraci ´ o integral sobre l’orientaci ´ o d’hipergr ` afs dins de les vies metab` oliques. El nostre focus va estar en la formulaci ´ o d’un model AMPL, permetent als investigadors obtenir solucions efectives mitjanc¸ant l’optimitzaci´ o de ILP. Les principals contribucions del nostre treball inclouen: • Desenvolupament d’un model l ` ogicament robust per resoldre el problema de l’orientaci ´ o d’hiperarestes en vies metab` oliques. • Avaluaci ´ o comparativa del model respecte alternatives, identificant punts forts, punts febles i escenaris d’aplicaci´ o` optims. • Introducci ´ o de restriccions addicionals considerades significatives en el camp de les vies metab` oliques, incloent´ ı: 1. La prevenci´ o de la inversi´ o en reaccions espec´ ıfiques. 2. La identificaci´ o de certs v` ertexs com interns. 3. La identificaci´ o de certs v` ertexs com externs. A m ´ es, aquest article presenta una eina d’interf ´ ıcie gr ` afica d’usuari (GUI) amigable que facilita l’exploraci ´ o del model, l’an ` alisi de resultats, l’addici ´ o de restriccions i l’orientaci ´ o de vies metab` oliques en escenaris del m´ on real. 7 1 Introduction and contextualization This article provides context for the research conducted in Zephyr Serret Verbist’s Bachelor’s Thesis, undertaken at the Faculty of Informatics of Barcelona (FIB) at the Universitat Polit ` ecnica de Catalunya, under the guidance of Gabriel Valiente Feruglio. It encompasses an exploration of the research’s background, the applied methodology, the rationale behind the study, and the obtained results. 1.1 Terms and concepts used in this study 1.1.1 Hypergraphs Hypergraphs are an extension of graphs that employs hyperedges instead of edges. A hyperedge is defined by two non-empty sets of nodes: a tail set and a head set. The hyperedge models a relationship originating from all elements in its tail set to all elements in its head set, or it can be undirected. Let us recall from [2] the following definition, where we impose the tail set and head set of a hyperedge to be nonempty sets of nodes. Definition. A directed hypergraph H =( V,E )consists of a set of nodes V and a set of hyperedges E={(T(e),H(e)) |T(e)⊆V,H(e)⊆V,T(e),∅,H(e),∅}. v1 v2 v3 v4 v5 v6 v7 e1e2 e3 e4 e5 e6 Figure 1: Example of a directed hypergraph H=(V,E) with V={v1,v2,v3,v4,v5,v6,v7}and E={e1,e2,e3,e4,e5,e6}, where e1=({v1},{v2,v3}), e2=({v2,v3},{v4}), e3=({v4,v5},{v6,v7}), e4=({v5},{v7}), e5=({v2,v3},{v1}), e6=({v7},{v5}). 1.1.2 Metabolic Pathway A metabolic pathway is a set of linked chemical reactions that occur in the cell. Hypergraphs are particularly well-suited for modeling metabolic pathways because metabolic reactions often involve multiple substrates and multiple products [3]. While these reactions typically have a dominant direction, it is also possible for some reactions to proceed in the opposite direction [ 4 ]. Figure 2shows a representation of the Sphingolipid metabolic pathway map in Homo Sapiens. 8 T1.3 Budget and sustainability: This phase entails determining the financial resources required for the project’s execution, including budget allocation for various tasks and activities. Additionally, it involves a study of the project’s sustainability impact, assessing its environmental, social, and economic implications. T1.4 Integration of Key Project Components: In this stage, we integrate and consolidate the key components of the project, including the defined context and scope, the finalized temporal plan, the budget allocation, and the sustainability impact assessment. This holistic approach ensures that all project elements work seamlessly together and provides a comprehensive reference for project execution. T1.5 Meetings with the tutor: Regular meetings with the project tutor are essential for maintaining effective communication and mentorship throughout the project’s lifecycle. These meetings provide opportunities to discuss progress, seek guidance, address challenges, and ensure that the project remains aligned with its objectives. Meetings with the tutor are valuable checkpoints for the project’s success. 5.1.2 T2 - Design of the ILP Model This phase constitutes the core of the project, involving the conceptualization and formulation of the Integer Linear Programming (ILP) model. It encompasses identifying variables, formulating constraints, and fine-tuning the model to accurately represent hypergraph orientation. T2.1 Study of ILP Modeling Using AMPL: Dive into the study of Integer Linear Programming (ILP) modeling principles using AMPL (A Mathematical Programming Language) as the platform. This subtask involves gaining a deep understanding of ILP concepts, syntax, and best practices for model formulation. T2.2 Formulate the Hypergraph Model: Develop an ILP model that accurately represents hypergraph orientation and obtains a solution to our optimization problem. This subtask includes identifying and defining the model’s decision variables, objective function, and constraints. Ensure that the model effectively captures the complexities of hypergraph structures. T2.3 Validation with Handcrafted Data: Test the formulated ILP model using carefully crafted or synthetic hypergraph data. This subtask involves creating hypergraphs with known properties to validate the model’s accuracy and functionality. T2.4 Testing with Real Data: Apply the ILP model to real-world hypergraph data, such as metabolic pathway information from the KEGG database. This subtask assesses the model’s performance and adaptability in handling practical and complex data sets. T2.5 Benchmarking and Optimization: Conduct benchmark tests to evaluate the ILP model’s efficiency and scalability. Explore alternative models and solvers. 5.1.3 T3 - App Development: Following the design of the ILP model, attention will shift towards the development of the application. This phase involves implementing the ILP model within the application framework, ensuring seamless interaction with the KEGG database, and incorporating user-friendly interfaces for efficient utilization. T3.1 Database Interaction Setup Establish robust mechanisms for the application to interact with the KEGG database, allowing for data retrieval and updates as needed. 15 T3.2 ILP Model Integration Integrate the designed ILP model into the application’s architecture, ensuring that it functions seamlessly within the software. T3.3 Functionality Implementation Implement the core functionalities of the application, ensuring that it can effectively perform hypergraph orientation tasks based on the ILP model. T3.4 User Interface Design Design and develop user-friendly interfaces for the application, focusing on usability and efficiency for end-users. T3.5 User Documentation Creation Develop comprehensive user documentation, including user guides and manuals, to assist users in effectively utilizing the application. 5.1.4 T4 - Implicit Task - Project Documentation: Throughout the different project tasks, comprehensive documentation is an ongoing process. This includes detailing the methodology, presenting results, and providing user instructions for the application. Additionally, any supplementary materials or resources are continuously compiled for future reference. 5.1.5 T5 - Preparation for the oral defence In the lead-up to the oral defense, thorough preparation is essential. This subtask includes finalizing the presentation materials, rehearsing the oral defense, and conducting mock presentations to ensure a confident and effective delivery during the defense session. ID Task Dependencies Duration (hours) T1 Project Management 85 T1.1 Definition of the context and project scope 25 T1.2 Temporal planning of the project 15 T1.3 Budget and sustainability 15 T1.4 Integration of Key Project Components T1.1, T1.2, T1.3 15 T1.5 Meetings with the tutor 15 T2 Design of the ILP Model 90 T2.1 Study of ILP Modeling Using AMPL 40 T2.2 Formulate the Hypergraph Model T2.1 15 T2.3 Validation with Handcrafted Data T2.2 10 T2.4 Testing with Real Data T2.2, T3.1 15 T2.5 Benchmarking and Optimization T2.4 10 T3 App development 210 T3.1 Database Interaction Setup 35 T3.2 ILP Model Integration T2.2 25 T3.3 Functionality Implementation T3.1, T3.2 50 T3.4 User Interface Design T3.3 50 T3.5 User Documentation Creation T3.4 50 T4 Project documentation 50 T5 Preparation for the oral defence T1, T2, T3, T4 30 Total: 435 Table 1: Task Duration and dependencies 5.2 Task duration estimates In this section we give an estimating of the time required for the completion of tasks and subtasks. Additionally, we will identify and declare any interdependencies between these tasks where applica16 ble. We provide the table 1which displays the durations and dependencies of the tasks. We also provide the figure 4which depicts the Gantt Chart representing the proposed workflow of the project. 17 Figure 4: Gantt Diagram. Source : own compilation 18 5.3 Resources In the pursuit of this research endeavor, several essential resources, both human and material, play a crucial role in facilitating the project’s success. These resources are integral to the project’s development, documentation, and overall execution. 5.3.1 Human Resources: In this section, we introduce the team members working on this project and outline their roles and responsibilities: • Main Developer (Author): The principal architect of this project, the author is responsible for the project’s design, development, and execution. • University Thesis Supervisor: The invaluable guidance and mentorship provided by the university thesis supervisor are instrumental in shaping the project’s direction and ensuring academic rigor. •GEP Tutor: The GEP (GESTI ´ O DE PROJECTES) tutor contributes to the project by offering instructions and feedback on the project management aspect of the research. We have identified five distinct roles, and assigned specific responsibilities within the project: 1. Junior Project Manager: Responsibilities: Project coordination, task scheduling, and overall project management. Assigned team member: Author 2. Project Manager: Responsibilities: Project supervision, guidance, research leadership, methodology development, and academic oversight. Assigned team members: Thesis supervisor,GEP tutor 3. Junior Researcher: Responsibilities: Research tasks, studying hypergraphs and AMPL modeling. Assigned team member: Author 4. Senior Researcher: Responsibilities: Research and academic guidance, leadership, methodology development. Assigned team member: Thesis supervisor 5. Junior Full Stack Developer: Responsibilities: Software development, programming, and application design. Assigned team member: Author 5.3.2 Material Resources: Overleaf: A collaborative LaTeX platform, Overleaf simplifies project documentation, enabling efficient collaboration and progress tracking with the project team. Atenea: The university’s Atenea platform serves as a communication hub, providing instructions and feedback from the GEP tutor. PyCharm IDE: A top-tier Python Integrated Development Environment (IDE) empowers the author with advanced programming capabilities, streamlining development tasks. ChatGPT: A versatile AI tool, ChatGPT assists in text composition and programming tasks, ensuring the generation of grammatically correct and comprehensive text. AMPL IDE: The AMPL Integrated Development Environment is employed for the development and testing of AMPL (A Mathematical Programming Language) models, a critical component of the project. 19 GitHub: A robust version control platform, GitHub facilitates collaborative coding, version management, and project organization. High-Performance Computer: Equipped with a formidable Ryzen 7 5800x3D CPU, 32GB RAM operating at 3600MHz, and an AMD Radeon RX 6900XT GPU, this high-performance computer serves as the primary development environment. In the event that this setup proves insufficient for computational demands, access to the Department of Computer Science’s supercomputer cluster may be requested. 20 ID Task Roles Material Resource T1 Project Management Junior Project Manager, Project Manager Overleaf,Atenea,ChatGPT,High-Performance Computer T1.1 Definition of the context and project scope Junior Project Manager, Project Manager Overleaf,Atenea,ChatGPT,High-Performance Computer T1.2 Temporal planning of the project Junior Project Manager, Project Manager Overleaf,Atenea,ChatGPT,High-Performance Computer T1.3 Definition of the budget and study of sustainability impact Junior Project Manager, Project Manager Overleaf,Atenea,ChatGPT,High-Performance Computer T1.4 Integration of Key Project Components Junior Project Manager, Project Manager Overleaf,Atenea,ChatGPT,High-Performance Computer T1.5 Meetings with the tutor All roles T2 Design of the ILPModel Junior Researcher AMPL IDE,High-Performance Computer T2.1 Study of ILP Modeling Using AMPL Junior Researcher T2.2 Formulate the Hypergraph Model Junior Researcher AMPL IDE,High-Performance Computer T2.3 Validation with Handcrafted Data Junior Researcher AMPL IDE,High-Performance Computer T2.4 Testing with Real Data Junior Researcher AMPL IDE,High-Performance Computer T2.5 Benchmarking and Optimization Junior Researcher AMPL IDE,High-Performance Computer T3 App development Junior Full Stack Developer GitHub,PyCharm IDE,ChatGPT,High-Performance Computer T3.1 Database Interaction Setup Junior Full Stack Developer GitHub,PyCharm IDE,ChatGPT,High-Performance Computer T3.2 ILP Model Integration Junior Full Stack Developer GitHub,PyCharm IDE,ChatGPT,High-Performance Computer T3.3 Functionality Implementation Junior Full Stack Developer GitHub,PyCharm IDE,ChatGPT,High-Performance Computer T3.4 User Interface Design Junior Full Stack Developer GitHub,PyCharm IDE,ChatGPT,High-Performance Computer T3.5 User Documentation Creation Junior Full Stack Developer GitHub,PyCharm IDE,ChatGPT,High-Performance Computer T4 Project documentation Junior Full Stack Developer ChatGPT T5 Preparation for the oral defence Junior Researcher, Junior Full Stack Developer ChatGPT Table 2: Table of requirements (Human and Material) corresponding to each task 21 5.4 Risk Management: Obstacles and alternative plans In the pursuit of this research project, we have identified several potential risks that may affect its execution. In this section, we discuss these risks, propose solutions, and provide estimates of possible consequences in terms of additional time and resources required. 5.4.1 Project Timeline Risk: Some tasks may have been underestimated and may take longer than expected for various reasons. Proposed Solution: It is crucial to monitor our progress and be aware of the expected development stage at any given time. This enables us to adjust our plans if necessary. Possible Consequences: In the worst-case scenario, we may require an additional 50 to 80 hours of labor. Probability: Low. We have already conducted a comprehensive field study during the document’s preparation, allowing us to identify potential obstacles and adapt the project plan and scope accordingly. 5.4.2 Computational power Risk: The computer we have may not be powerful enough to handle the largest hypergraphs efficiently. Proposed Solution: In case our current setup proves insufficient, we will establish contact with the computing cluster of the Department of Computer Science to process more demanding cases. Possible Consequences: In the event of computational limitations, there might be a delay of multiple days. During this time, Task T2.4 might be affected. However, our project plan allows us to proceed with different tasks that do not rely on T2.4 as a predecessor. At worst, we anticipate a delay of 15 hours. Probability: Low. Early testing shows that the computer at our dispositions is sufficiently powerful. 5.4.3 Integration Challenges Risk: Integration with the KEGG database may present challenges, including content and format discrepancies. Proposed Solution: To address integration challenges effectively, we will implement the following strategies: - Stay informed about updates to the KEGG database. - Establish communication channels with the KEGG team if possible. - Develop a flexible application architecture capable of accommodating changes as they occur. Possible Consequences: Integration challenges may lead to additional effort and time spent on data processing and application adaptation. The extent of the consequences will depend on the nature and frequency of changes in the KEGG database. We expect a delay of up two 50 hours. Probability: High. We have already identified several shortcomings in the data available that could impact Tasks T3.3 and T3.4. 5.4.4 Inexperience with ILP: Risk: The author’s limited experience with Integer Linear Programming (ILP) poses a potential challenge. Proposed Solution: To overcome inexperience with ILP, we will adopt a proactive approach that includes: 22 - Utilizing educational resources, such as online courses and textbooks. - Seeking guidance and mentorship from experts in the field. - Engaging in practical exercises to apply ILP concepts. - Collaborating with individuals experienced in ILP. - Committing to continuous learning throughout the project. Possible Consequences: While there may be an initial learning curve, dedicating time and effort to gaining proficiency in ILP should mitigate potential challenges related to inexperience. Some tasks may have been underestimated and may take longer than expected for various reasons. We may expect up to extra 20 hours. Probability: Low. We already have a working model. 6 Budget In this section, we present a comprehensive budget estimation for the successful completion of the project. The budget is categorized into two main components: Personnel Costs per Activity and Generic Costs. This breakdown offers transparency and insight into the allocation of resources. 6.1 Staff costs As we saw in section 5.3.1, we identified three key individuals (the Author, the thesis supervisor and the GEP supervisor) who are involved in various roles to ensure the successful execution of the project. In table 3, we present the estimated hourly rates for each of the roles, taking into account Social Security contributions. The cost estimation is based on average salaries for each role in the region of Barcelona. Role Annual Salary Annual Salary +SS (35%) Cost Per hour Project Manager €44,000.00 [5]€59,400.00 €34.22 Junior Project Manager €30,000.00 [6]€40,500.00 €23.33 Junior Researcher €25,000.00 [7]€33,750.00 €19.44 Senior Researcher €39,000.00 [8]€52,650.00 €30.33 Junior Full Stack Developer €25,000.00 [9]€33,750.00 €19.44 Table 3: Estimated Staff Costs per hour (1736 working hours per year [1]) In table 4, we present the estimated cost of each task by defining how many hours each role must spend on it and by using the data from table 3. What we obtain is an estimation of the Personnel Cost per Activity or PCA. 23 ID Task Hours per role Total Hours Price Project Manager Jr.Project Manager Jr. Researcher Sr. researcher Jr. Full Stack Dev. T1 Project Management 25 75 5 10 5 120 €3,102.82 T1.1 Context and scope 5 25 0 0 0 30 €754.32 T1.2 Temporal planning of the project 5 15 0 0 0 20 €521.03 T1.3 Budget and sustainability 5 15 0 0 0 20 €521.03 T1.4 Integration of Key Project Components 5 15 0 0 0 20 €521.03 T1.5 Meetings with the tutor 5 5 5 10 5 30 €785.43 T2 Design of the ILPModel 0 0 90 0 0 90 €1,749.71 T2.1 Study of ILP Modeling Using AMPL 0 0 40 0 0 40 €777.65 T2.2 Formulate the Hypergraph Model 0 0 15 0 0 15 €291.62 T2.3 Validation with Handcrafted Data 0 0 10 0 0 10 €194.41 T2.4 Testing with Real Data 0 0 15 0 0 15 €291.62 T2.5 Benchmarking and Optimization 0 0 10 0 0 10 €194.41 T3 App development 0 0 0 0 210 210 €4,082.66 T3.1 Database Interaction Setup 0 0 0 0 35 35 €680.44 T3.2 ILP Model Integration 0 0 0 0 25 25 €486.03 T3.3 Functionality Implementation 0 0 0 0 50 50 €972.06 T3.4 User Interface Design 0 0 0 0 50 50 €972.06 T3.5 User Documentation Creation 0 0 0 0 50 50 €972.06 T4 Project documentation 0 0 0 0 50 50 €972.06 T5 Preparation for the oral defence 0 0 15 0 15 30 €583.24 Sum: €19,425.69 Table 4: Personnel Cost per Activity (PCA) based on the costs defined in table 3 24 •substrates not inverted This constraint forces the has in variable assigned to every vertex ito not be 0 when at least one of i ’s hyperedges where it appears as substrate hasn’t been inverted. •substrates inverted This constraint forces the has out variable assigned to every vertex i to not be 0 when at least one of i ’s hyperedges where it appears as substrate has been inverted. •products not inverted This constraint forces the has out variable assigned to every vertex i to not be 0 when at least one of i’s hyperedges where it appears as product hasn’t been inverted. •products inverted This constraint forces the has in variable assigned to every vertex i to not be 0 when at least one of i ’s hyperedges where it appears as product has been inverted. •products inverted This constraint forces the has in variable assigned to every vertex i to not be 0 when at least one of i ’s hyperedges where it appears as product has been inverted. •not substrate at all This constraint forces the has in variable assigned to every vertex i to be 0 when none of i’s hyperedges where it appears as substrate hasn’t been inverted and none where it appears as product has been inverted. •not product at all This constraint forces the has out variable assigned to every vertex ito be 0 when none of i ’s hyperedges where it appears as product hasn’t been inverted and none where it appears as substrate has been inverted. •respect invertability This constraint forces the inverted variable assigned to every hyperedge i to be 0 when it isn’t allowed to be inverted by the problem definition. As observed, the presence of numerous strong constraints creates a significant interdependency among the variables: inverted,has in,has out, and is internal. Notably, when there is an outgoing edge, has out can only assume a value of 1, and a similar condition applies to has in. This strict mathematical relationship eliminates any ambiguity. It is through this robust mathematical correlation that we can confidently affirm the fidelity of our model in representing the problem. 31 1##################### 2## Inputs 3##################### 4 5set V; # nodes 6set E; # hyperedges 7 8set X{E}; # for each hyperedge , its tail set 9set Y{E}; # for each hyperedge , its head set 10 11 param invertible{E} binary;# determines whether an edge is invertible 12 13 ##################### 14 ## Helpers 15 ##################### 16 17 set substrate_in{i in V} := {j in E: i in X[j]}; 18 set product_in{i in V} := {j in E: i in Y[j]}; 19 20 ##################### 21 ## Variables 22 ##################### 23 24 var inverted {E} binary;#determines whether an edge is inverted 25 26 var has_out {V} binary; 27 var has_in{V} binary; 28 29 var is_internal{V} binary; 30 31 ##################### 32 ## Rules 33 ##################### 34 35 maximize obj: sum{i in V} is_internal[i]; 36 37 subject to compute_is_internal{i in V}: 38 is_internal[i] <= has_in[i] + has_out [i] - 1; 39 40 subject to substrates_not_inverted{i in V, j in substrate_in[i]}: 41 has_in[i] >= 1-inverted[j]; 42 43 subject to substrates_inverted{i in V, j in substrate_in[i]}: 44 has_out [i] >= inverted [j]; 45 46 subject to products_not_inverted{i in V, j in product_in[i]}: 47 has_out [i] >= 1inverted [j]; 48 49 subject to products_inverted{i in V, j in product_in[i]}: 50 has_in[i] >= inverted[j]; 51 52 subject to not_substrate_at_all{i in V}: 53 has_in[i] <= 54 sum{j in substrate_in[i]} (1-inverted [j]) + 55 sum{j in product_in[i]} inverted[j]; 56 57 subject to not_product_at_all{i in V}: 58 has_out [i] <= 59 sum{j in product_in[i]} (1inverted[j]) + 60 sum{j in substrate_in[i]} inverted[j]; 61 62 subject to respect_invertability {i in E}: 63 inverted [i] <= invertible[i]; Figure 5: The model file of the first prototype 8.3.2 Models Developed by the Professor and His Colleagues In this section, we introduce two models developed by the professor and their colleagues. To enhance clarity within the context we presented, various aspects such as parameters, variables, sets, and/or rule names have been modified, ensuring that all the models share similar names. This deliberate adjustment simplifies comprehension and facilitates a more coherent understanding 32 of the models as they are discussed in the subsequent content. We present below the first model (Figure 6) which we call ”Model A”. 1##################### 2## Parameters 3##################### 4set V; 5set E; 6 7set X{E} within V; # The tail set for each hyperedge 8set Y{E} within V; # The head set for each hyperedge 9 10 ##################### 11 ## Variables 12 ##################### 13 14 var inverted{E} binary;# 1 iff edge is inverted (Head and Tail) 15 var is_internal{V} binary;# to maximize 16 17 18 ##################### 19 ## Rules 20 ##################### 21 22 maximize obj: sum {j in V} is_internal[j]; 23 24 subject to outgoing_half_implies_internal {j in V}: 25 sum {i in E: j in X[i]} (1inverted [i]) + 26 sum {i in E: j in Y[i]} inverted[i] 27 >= is_internal[j]; 28 # will only allow is_internal to be one if there ’s an outgoing edge. 29 30 subject to incoming_half_implies_internal {j in V}: 31 sum {i in E: j in Y[i]} (1inverted [i]) + 32 sum {i in E: j in X[i]} inverted[i] 33 >= is_internal[j]; 34 # will only allow is_internal to be one if there ’s an incoming edge. Figure 6: AMPL Model - Model A Model A is comparatively simpler, featuring only two rules and two variables, both of which also appear in the first prototype (Figure 5). Although the rules ’outgoing half implies internal’ and ’incoming half implies internal’ are presented slightly differently, they are mathematically equivalent to the rules ’not substrate at all’ and ’not product at all’ from the first prototype. As we will see in the following sections, this model excels in speed but lacks the mathematical robustness needed to accommodate more complex constraints, such as forcing certain vertices to be external or internal. Similarly, the second model ”Model B” (Figure 7), is displayed below: 33 1set V; 2set E; 3 4param M = card(V); 5 6set X {E} within V; 7set Y {E} within V; 8 9 10 var inverted {E} binary; 11 var source {V} binary; 12 var sink {V} binary; 13 var is_internal{V} binary; 14 15 maximize internal: sum {j in V} is_internal[j]; 16 17 ############# 18 19 s.t. outgoing_1{j in V}: #for every vertex 20 sum{i in E: j in Y[i]} inverted[i] + 21 sum{i in E: j in X[i]} (1inverted [i]) #how many times it appears as substrate 22 - M * source[j] 23 <= 0; 24 25 s.t. outgoing_2{j in V}: 26 sum{i in E: j in Y[i]} inverted[i] + 27 sum{i in E: j in X[i]} (1-inverted[i]) 28 - 0.5 * source[j] 29 >= 0; 30 31 ############## 32 33 s.t. incoming_1{j in V}: 34 sum{i in E: j in Y[i]} (1inverted [i]) + 35 sum{i in E: j in X[i]} inverted[i] 36 - M * sink[j] 37 <= 0; 38 39 s.t. incoming_2{j in V}: 40 sum{i in E: j in Y[i]} (1inverted [i]) + 41 sum{i in E: j in X[i]} inverted[i] 42 - 0.5 * sink[j] 43 >= 0; 44 45 ############### 46 47 s.t. internal_1 {j in V}: 48 source[j] + sink[j] -1 - M * is_internal[j] <= 0; 49 50 s.t. internal_2 {j in V}: 51 source[j] + sink[j] -1 - 0.5 * is_internal[j] >= 0; Figure 7: AMPL Model - Model B Model B’s design philosophy aimed to follow a mathematical procedure to convert a mathematical problem into an optimization problem. Model B’s model is much stronger mathematically than Model A’s and strongly inspired the final model chosen for the project. 8.4 Initial Benchmarking Our benchmarking approach involves running 25 pathway optimizations for each of the models we want to evaluate, including the three largest ones. We conducted these benchmarks using the dedicated Benchmark View of our Python program, detailed in Section 10.4. The computer for all benchmarks is the high-end desktop computer described in Section 5.3.2. The outcomes of our initial benchmark are summarized in Table 8, featuring five columns. The first column displays the pathway ID, the second indicates the solver used, and the last three columns depict the time taken by each model to complete the optimization problem in seconds. Upon examination of the results, a noticeable performance gap emerges, particularly for the first prototype. This initial version exhibits suboptimal performance, taking roughly three times 34 longer than Model B and eight times longer than Model A to solve the most challenging pathway problem. This difference highlights specific areas where improvements or optimizations could enhance the overall performance of our prototype models. entry solver First Prototype Model A Model B map01100 cbc 74.960s 8.572s 24.458s map01110 cbc 25.927s 3.938s 10.407s map01120 cbc 9.042s 1.186s 4.058s map01200 cbc 0.474s 0.258s 0.521s map01210 cbc 0.462s 0.343s 0.604s map01212 cbc 0.467s 0.211s 0.385s map01230 cbc 0.432s 0.243s 0.419s map01232 cbc 0.350s 0.244s 0.424s map01250 cbc 0.401s 0.245s 0.710s map01240 cbc 1.148s 0.301s 1.373s map01220 cbc 0.769s 0.276s 0.479s map00010 cbc 0.357s 0.275s 0.339s map00020 cbc 0.351s 0.281s 0.308s map00030 cbc 0.351s 0.256s 0.365s map00040 cbc 0.296s 0.387s 0.352s map00051 cbc 0.345s 0.299s 0.341s map00052 cbc 0.294s 0.194s 0.316s map00053 cbc 0.389s 0.335s 0.317s map00500 cbc 0.310s 0.287s 0.304s map00520 cbc 0.491s 0.355s 0.540s map00620 cbc 0.357s 0.246s 0.406s map00630 cbc 0.446s 0.516s 0.970s map00640 cbc 0.999s 0.464s 0.516s map00650 cbc 0.769s 0.372s 0.464s map00660 cbc 0.401s 0.238s 0.271s Table 8: Initial Benchmark 8.5 Creating and optimizing our final model This section focuses on optimizing our models. Serret’s DualImply model will be introduced in this section. Drawing insights from extensive testing and our initial benchmark, we’ve identified key principles that contribute to improving the model’s efficiency compared to others. Our optimization principles include: Simplicity in Representation: An effective model is achieved by minimizing the number of rules and variables for a concise representation. Multiplication of Binary Variables: Despite support for the multiplication of binary variables in the maximize/minimize function in newer AMPL versions, we explore the efficiency gained by manually introducing rules and variables to transform the problem back into an integer form, rather than relying solely on AMPL’s pre-compiler. Guided by these considerations, we present a redesigned model. This model has undergone continuous refinement throughout the project’s development, ensuring it is not only mathematically robust but also thoroughly optimized. The final representation of our optimized model is provided below: 35 1# #################### 2## Parameters 3# #################### 4set V; 5set E; 6 7param M = card (E); 8 9set X {i in E} within V; # Tail set 10 set Y {i in E} within V; # Head set 11 12 set uninvertibles within E; # set of edges that cannot be inverted 13 set forced_internals within V; # set of nodes that must be sinks 14 set forced_externals within V; # set of nodes that must be sources 15 16 # #################### 17 ## Variables 18 # #################### 19 var inverted {E} binary ;# from X[i] to Y[i] 20 var has_outgoing {V} binary ; 21 var has_incoming {V} binary ; 22 var is_internal {V} binary; 23 24 # #################### 25 ## Rules 26 # #################### 27 maximize internal : sum {j in V} is_internal[j]; 28 29 subject to is_internal_1 {i in V}: 30 is_internal[i] * 2 <= has_incoming[i] + has_outgoing [i]; 31 32 subject to outgoing_implies_has_outgoing {j in V}: 33 sum {i in E: j in X[i]} (1inverted [i]) + 34 sum {i in E: j in Y[i]} inverted [i] 35 >= has_outgoing [j]; 36 37 subject to has_outgoing_implies_outgoing {j in V}: 38 sum {i in E: j in X[i]} (1inverted [i]) + 39 sum {i in E: j in Y[i]} inverted [i] 40 <= M * has_outgoing [j]; 41 42 subject to incoming_implies_has_incoming {j in V}: 43 sum {i in E: j in X[i]} inverted [i] + 44 sum {i in E: j in Y[i]} (1inverted [i]) 45 >= has_incoming [j]; 46 47 subject to has_incoming_implies_incoming {j in V}: 48 sum {i in E: j in X[i]} inverted [i] + 49 sum {i in E: j in Y[i]} (1inverted [i]) 50 <= M * has_incoming [j]; 51 52 # #################### 53 ## Extra Restrictions 54 # #################### 55 56 subject to forced_externals_rule {i in forced_externals }: 57 has_incoming [i] + has_outgoing [i] <= 1; 58 59 subject to forced_internals_rule {i in forced_internals }: 60 has_incoming [i] + has_outgoing [i] = 2; 61 62 subject to respect_invertability {i in uninvertibles }: 63 inverted [i] = 0; Figure 8: Serret’s DualImply Model (with extra restrictions) This model is designed to handle extra constraints that were not initially part of the original problem definition but are expected to be biologically relevant and extend the problem’s scope. These additional constraints, termed ’extra restrictions,’ offer the following functionalities: 1. The ability to designate certain vertices (or biological compounds) as internal or external. 2. The capability to prevent the inversion of specific hyper-edges (or biological reactions), ensuring the preservation of their original orientation. 36 8.6 Mathematical proof of the final model In this section, we aim to provide a formal mathematical proof to substantiate the logical foundation of our proposed model, ensuring its accurate representation of the problem at hand. To facilitate this proof, we introduce specific predicates and functions that will help demonstrate the correspondence. 8.6.1 Introduction of Predicates and Functions: We introduce the following predicates: is internali: True when the vertex i is internal has outgoingi: True when the vertex i acts a substrate in at least one hyperedge has incomingi: True when the vertex i acts a product in at least one hyperedge Additionally, we define the following functions: isOne(x): Returns True if and only if x == 1, otherwise returns False toNum(x): Returns 1 if and only if predicate x is True, otherwise returns 0 These functions serve to establish the equivalence between the mathematical model and the ILP model. 8.6.2 Obtaining is internal from has outgoing and has incoming The objective of our model is to find an orientation that maximizes the number of internal vertices. Thus, we formulate our maximizing function: to maximize =sum({toNum(is internali)| ∀i∈V}) Now, we mathematically define when a node is internal, building upon the definition provided in Section 1.1.3: is internali≡has incomingi∧has outgoingi(1) We would like to prove that this alternative definition is equivalent: is internali≡inequation 1i∧inequation 2i(2) Where inequation 1iis defined as toNum(is internali)∗2<=toNum(has incomingi)+toNum(has outgoingi) (3) and inequation 2iis defined as toNum(is internali)>=toNum(has incomingi)+toNum(has outgoingi)−1 (4) To do so we will use the Table 9to prove that, for every value of has incoming i , has outgoing i and is internali, the equivalence (1) is the same as the equivalence (2): 37 is internal i has incoming i has incoming iinequation 1i(3) inequation 2i(4) equivalence (2) equivalence (1) F F F T T T T F F T T T T T F T F T T T T F T T T F F F T F F F T F F T F T F T F F T T F F T F F T T T T T T T Table 9: Truth table of the equivalence of is internal and the system of inequations 38 Given what we just showed, we can create the following set of AMPL rules that create the interdependence of has incomingi, has outgoingiand is internalibased the equivalence 2. 1subject to is_internal_1 {i in V}: 2is_internal[i] * 2 <= has_incoming [i] + has_outgoing [i]; 3 4subject to is_internal_2 {i in V}: 5is_internal[i] >= has_incoming[i] + has_outgoing[i] - 1; Figure 9: Strong AMPL rules used to define has internali Optimization : The maximizing function aims to maximize the number of internal vertices, as defined in the problem statement. Given that the variable is internaliis solely used in the maximizing function and no other rules apart from those used to define is internal, we can make the following assumption: When the solver is presented with a is internal variable that can either be set to True or to False, the solver will always set it to True. Based on this assumption, we observe that the second inequality in (4) becomes redundant. Table 10 demonstrates that we achieve identical results by utilizing only the first rule. has incomingihas outgoingi values of is internali satisfying inequation 1 i(3) values of is internali satisfying inequation 2 i(4) values of is internali allowed by definition (2) F F F {F, T }F F T F {F, T }F T F F {F, T }F T T {F, T }T T has incomingihas outgoingi values of is internalisatisfying inequation 1i(3) value of is internalichosen by the solver based solely on inequation 1 (3) F F F F F T F F T F F F T T {F, T }T Table 10: Optimizing is internal by removing a redundant inequation Optimization Impact: Through extensive testing, implementing this optimization resulted in a noteworthy speedup of up to 1.14 with respect to the original method. This enhancement was particularly pronounced when applied to the largest model within our dataset. 39 8.6.3 Obtaining has outgoing from the X and Y sets For this section, we need to introduce some new predicates and functions: invertedj: True if the solution inverts the hyperedge j. inTailSet(i): returns the set of hyperedges that have the vertex i in their tail set. inHeadSet(i): returns the set of hyperedges that have the vertex i in their head set. We begin with the following statement: has outgoingi⇐⇒ (∃j∈inTailSet(i):¬invertedj)∨(∃j∈inHeadSet(i):invertedj) (5) Through this statement, we are saying that for a vertex to be considered to have an outgoing hyperedge in the solution, it must appear in the tail set of an uninverted hyperedge or in the head set of an inverted hyperedge in the problem input. Using the rule p⇐⇒ q≡(¬p∨q)∧(p∨¬q), we can break down the statement above into : (¬has outgoingi∨(∃j∈inTailSet(i):¬invertedj)∨(∃j∈inHeadSet(i):invertedj)) ∧ (has outgoingi∨ ¬((∃j∈inTailSet(i):¬invertedj)∨(∃j∈inHeadSet(i):invertedj))) (6) As we can see from the last statement, we have two parts that are combined with an ∧ . We will deal with each part individually by separating them into two parts. First Part: ¬has outgoingi∨(∃j∈inTailSet(i):¬invertedj)∨(∃j∈inHeadSet(i):invertedj) (7) ≡¬has outgoingi∨(X j∈inTailSet(i) (1−toNum(invertedj))>=1) ∨(X j∈inHeadSet(i) toNum(invertedj)>=1) (8) ≡¬has outgoingi∨(X j∈inTailSet(i) (1−toNum(invertedj)) +X j∈inHeadSet(i) toNum(invertedj)>=1) (9) ≡(1−has outgoingi=1) ∨(X j∈inTailSet(i) (1−toNum(invertedj)) +X j∈inHeadSet(i) toNum(invertedj)>=1) (10) ≡(has outgoingi=0) ∨(X j∈inTailSet(i) (1−toNum(invertedj)) +X j∈inHeadSet(i) toNum(invertedj)>=1) (11) ≡X j∈inTailSet(i) (1−toNum(invertedj)) +X j∈inHeadSet(i) toNum(invertedj)>=toNum(has outgoingi) (12) The first step is made using the following consideration: ∃i∈S:i≡(PtoNum(i)∈Si)>=1 The last step can be made using the following considerations : when has outgoingi is 1, it is trivial to see that the equivalence holds. When it is zero, the last statement will always be true since (Pj∈inTailSet(i)(1−toNum(invertedj))+Pj∈inHeadSet(i)toNum(invertedj)) ∈N0. 40 9 Database Integration 9.1 Acknowledgment of Attempted Integration using bioservices In the course of our research, we explored the possibility of integrating the KEGG database using the bioservices library to fetch reaction data. Regrettably, this approach encountered significant challenges, and we would like to provide an overview of the issues encountered during the integration attempt. The bioservices library was initially considered as a means to retrieve reactions from the KEGG database. However, this approach proved to be impractical for several reasons. Firstly, the method of fetching all reactions using bioservices proved to be extremely slow, making it infeasible to acquire the data in a reasonable time frame. This approach was not scalable for large-scale data retrieval, which is essential for comprehensive analysis. Furthermore, due to the extensive number of requests sent to the KEGG server in a short period of time, the server interpreted our actions as a potential denial of service attack. As a result, our IP address was temporarily blocked, rendering us unable to access the KEGG database for several hours. Given these limitations, it became evident that alternative strategies for data integration were necessary to overcome these challenges. The attempt to integrate the KEGG database using the bioservices library is documented in Figure 11, which shows the code used in this effort. 1from bioservices import KEGG 2k = KEGG () 3reactions = k.reactionIds 4for reaction in reactions: 5data = k.parse(k.get(reaction )) 6if ’ PATHWAY ’ not in data.keys(): 7continue 8for pathway in sorted(data[’PATHWAY ’].keys ()): 9print("{}: {}: {}".format( 10 reaction , 11 pathway , 12 data[’EQUATION’])) Figure 11: Integration attempt using bioservices This experience has been valuable in highlighting the complexities and limitations of real-world data integration in scientific research, as well as the need for robust, efficient, and responsible data retrieval methods. 9.2 REST API Data Mapping: Needs and Retrievals To effectively gather information from KEGG’s REST API, we must retrieve the following: 1. Comprehensive pathways, including their identifiers (IDs) and user-friendly descriptions. 2. Reaction identifiers associated with each pathway. 3. Compound identifiers serving as substrates or products for each reaction. 47 Regrettably, the REST API lacks specific calls to fulfill all our requirements directly. Instead, we employ a strategic approach by utilizing multiple endpoints and amalgamating their outcomes to obtain the necessary data. Here is the list of endpoints that we use: 1. https://rest.kegg.jp/list/pathway Returns the list of all pathway ids and a human readable description. Extract from output: map01100 Metabolic pathways map01110 Biosynthesis of secondary metabolites map01120 Microbial metabolism in diverse environments 2. https://rest.kegg.jp/link/reaction/pathway Returns the list of all pathway ids and the reaction ids which belong to them. Extract from output: path:map00010 rn:R00014 path:rn00010 rn:R00014 path:map00010 rn:R00199 3. https://rest.kegg.jp/list/compound Returns the list of all compound ids and names used to refer to them Extract from output: C00001 H2O; Water C00002 ATP; Adenosine 5’-triphosphate C00003 NAD+; NAD; Nicotinamide adenine dinucleotide; DPN; Diphosphopyridine nucleotide; Nadide; beta-NAD+ 4. https://rest.kegg.jp/link/compound/reaction Returns the list of all reactions ids and all commpounds ids that belong to that reaction Extract from output: rn:R00001 cpd:C00001 rn:R00002 cpd:C00001 rn:R00004 cpd:C00001 5. https://rest.kegg.jp/list/reaction Returns the list of all reaction ids and a textual representation of their equation. Extract from output: R00001 polyphosphate polyphosphohydrolase; Polyphosphate + n H2O <=> (n+1) Oligophosphate R00002 reduced ferredoxin:dinitrogen oxidoreductase (ATP48 hydrolysing); 16 ATP + 16 H2O + 8 Reduced ferredoxin <=> 8 e- + 16 Orthophosphate + 16 ADP + 8 Oxidized ferredoxin R00004 diphosphate phosphohydrolase; pyrophosphate phosphohydrolase; Diphosphate + H2O <=> 2 Orthophosphate 6. https://rest.kegg.jp/get/[Reaction id] Returns the entry for a specific reaction, including the ids of the pathways it belongs to and the equation in both identifier and human readable form. Note : You can at most query 10 different reactions at once. Extract from output: ENTRY R00014 Reaction NAME pyruvate:thiamin diphosphate acetaldehydetransferase (decarboxylating) DEFINITION Pyruvate + Thiamin diphosphate <=> 2-(alphaHydroxyethyl)thiamine diphosphate + CO2 EQUATION C00022 + C00068 <=> C05125 + C00011 PATHWAY rn00010 Glycolysis / Gluconeogenesis rn00020 Citrate cycle (TCA cycle) rn00620 Pyruvate metabolism rn00785 Lipoic acid metabolism As evident, the fulfillment of the first and second requirements is straightforward through the utilization of the first and second endpoints, respectively. However, addressing the third and final requirement—acquiring the list of compound identifiers for each reaction—poses a more intricate challenge. To achieve this efficiently, we must leverage all available endpoints, strategically combining their outputs. This comprehensive approach ensures a thorough extraction of the necessary data. 9.3 Equation Discovery: Unveiling Reaction Formulas and Compound IDs Across Varied Endpoints We aim to establish a mapping between reaction IDs and two distinct lists of compound IDs, one for substrates and the other for products. Throughout this section, compounds are typically presented either as compound IDs or by one of their various names (e.g., ”Nicotinamide adenine dinucleotide”). It’s essential to note that most compounds have multiple names. To underscore the fact that each compound is associated with several names, we choose to use the term synonym instead of name throughout the rest of this section. By leveraging the capabilities of the third endpoint, we can generate a mapping from synonyms to a list of compounds that share the same synonym. It’s important to acknowledge that certain synonyms may refer to multiple distinct compounds, although the majority pertain to only one. Example. 49 ”Quinone”: [”C00472”1, ”C15602”2] ”Ethanol”: [”C00469”3] Using the fourth endpoint, we can obtain a mapping of reaction IDs to a list of compound IDs, although we cannot determine if the compound acts as a substrate or product in the reaction. Example. ”R00001”: [”C00001”, ”C00404”, ”C02174”] ”R00002”: [”C00001”, ”C00002”, ”C00008”, ”C00009”, ”C00138”, ”C00139”, ”C05359”] By utilizing the fifth endpoint, we can acquire a mapping of reaction IDs to an equation where the substrates and products are represented in the form of synonyms. Example. ”R00001”: ”polyphosphate polyphosphohydrolase; Polyphosphate +n H2O < = > (n+1) Oligophosphate” ”R00002”: ”reduced ferredoxin:dinitrogen oxidoreductase (ATP-hydrolysing); 16 ATP +16 H2O +8 Reduced ferredoxin <=>8 e- +16 Orthophosphate +16 ADP +8 Oxidized ferredoxin” The subsequent step involves using the three previously obtained mappings to establish a new mapping from reaction IDs to the substrates’ compound IDs and products’ compound IDs. Starting from the mapping of reaction IDs to an equation where the substrates and products are in their synonym form, we proceed to discard the equation’s name by removing everything that precedes the last appearance of the ”; ” substring. If the ”; ” substring doesn’t appear, then we retain everything. Next, we separate the substrates and products using the substring ”<=>”. From this point, we extract each individual compound by splitting them using the ”+” character. At this stage, we are left with synonyms prefixed by a quantifier, such as a number or some expression with ’n’ (for example, n+1). To remove this quantifier, we subtract any matches to the following regular expression: ˆ\d+n? |ˆ\(n\+\ d+\) |ˆn ˆmatches with the start of a string. \dmatches with any digit (equivalent to [1-9]). +is a quantifier that matches to one or more instances. ?is a quantifier that matches to one or no instances. \+matches with the char ’+’. |signifies alternate options. In this case, we can match any of the three options. This leaves us with one of the synonyms for each compound in the equation. By utilizing the mapping synonym to list of compound IDs, we can generate a list of candidate compound IDs. We filter out every candidate that does not appear in the list obtained through the mapping reaction ID to list of compound IDs. At this stage, if we have more than one or no candidates, we mark this reaction as a broken reaction. If we have exactly one candidate left, 1https://rest.kegg.jp/get/C00472 2https://rest.kegg.jp/get/C15602 3https://rest.kegg.jp/get/C00469 50 it indicates that we have identified the correct compound, and we can add it to our final mapping of reaction ID to substrates and products accordingly. Below is a Python extract that demonstrates this procedure. 51 1def compound_verbose_and_reaction_to_id(self , compound_verbose , reaction_id): 2""" 3Returns the compound id that matches the verbose compound name 4 5Parameters: 6compound_verbose: a verbose compound name 7reaction_id: the reaction id that the compound belongs to 8 9Returns: 10 a single compound id , or None if no match 11 """ 12 13 synonym = re.sub(r’ˆ\d+n? |ˆ\(n\+\d+\) |ˆn ’,’’, compound_verbose) 14 15 if synonym not in self.map_synonym_to_compound_id: 16 print("Couldn ’t find the synonym :", synonym) 17 return None 18 candidates = [ 19 candidate # compound id 20 for candidate in self. map_synonym_to_compound_id[synonym] 21 if candidate in self.map_reaction_id_to_list_compound_id.get(reaction_id , []) 22 ] 23 if len(candidates) > 1: 24 print("compound: ", synonym , " has multiple candidates: ", candidates , 25 " for reaction: ", reaction_id , ", marking as broken") 26 return None 27 if len(candidates) < 1: 28 print("compound: ", synonym , "has no candidates in reaction", reaction_id , ", marking as broken") 29 return None 30 print("compound: ", synonym , " has id: ", candidates[0], " for reaction: ", reaction_id) 31 return candidates[0] 32 33 34 def fetch_reaction_substrates_products_ids (self): 35 """ 36 Fetches the list of reactions and creates the map reaction_id to substrate_ids and product_ids: 37 Uses the result from the KEGG api as well as : 38 - self.map_reaction_id_to_list_compound_id 39 - self.map_synonym_to_compound_id 40 """ 41 for reaction in REST.kegg_list("reaction").read ().split(’\n’)[:-1]: 42 broken = False 43 reaction_id , reaction_equation_verbose = reaction.split(’\t’) 44 reaction_equation_verbose = reaction_equation_verbose.split("; ")[-1] # remove the name of the equation 45 self.map_reaction_id_to_substrates_products_ids [reaction_id] = {"substrates": [], "products": []} 46 substrates_verbose , product_verbose = reaction_equation_verbose.split(’ <=> ’) 47 for substrate_verbose in substrates_verbose.split(’ + ’): 48 substrate_id = self. __compound_verbose_and_reaction_to_id( substrate_verbose , reaction_id) 49 if substrate_id is not None: 50 self. map_reaction_id_to_substrates_products_ids [ reaction_id ]\ 51 ["substrates"].append(substrate_id) 52 else: 53 self.broken_reaction_ids. append(reaction_id ) 54 broken = True 55 break 56 if broken: 57 continue 58 for product_verbose in product_verbose .split(’ + ’): 59 product_id = self. __compound_verbose_and_reaction_to_id( product_verbose , reaction_id) 60 if product_id is not None: 61 self. map_reaction_id_to_substrates_products_ids [ reaction_id ]\ 62 ["products"].append(product_id) 63 else: 64 self.broken_reaction_ids. append(reaction_id ) 65 break Figure 12: Obtaining compound ids from the human readable equation 52 Applying this procedure allows us to successfully retrieve the IDs for every substrate and product in an impressive 95.5% of the reactions, precisely 11,456 out of 11,991, with just 5 requests to the KEGG REST API server. For the remaining 535 reactions marked as broken, we initiate GET requests using the sixth endpoint to retrieve compound IDs directly from the API results. Given our ability to request up to 10 reactions at a time, we accomplish this in 54 requests, bringing the total number of requests for the complete database creation needed to run our program to 59. Remarkably, this efficient process enables us to construct the entire dataset in approximately 1 minute and 30 seconds, eliminating the risk of IP bans since we are making just a few requests. We store the final database as a JSON file, weighing in at 3.22 MB, enabling our program to run seamlessly without requiring an internet connection. 10 Navigating the Design and User Experience of our Python GUI Throughout our project, a key aspect of our development journey involved creating a straightforward Python GUI program. This application empowers users to effortlessly experiment with various models and seamlessly obtain insightful visualizations of hypergraphs. Additionally, users can leverage the GUI to benchmark different models, providing a user-friendly interface for comprehensive exploration. Features at a Glance: Optimize Real Pathways: Easily try out optimization models on real pathways, enabling users to gain a deeper understanding of the underlying concepts. Pathway Visualization: Gain valuable insights through simple and intuitive visualizations of oriented hypergraphs. Benchmarking Capabilities: Evaluate model performance efficiently by benchmarking against diverse datasets, aiding in the assessment and selection of the most suitable models. In the following sections, we will delve into the design principles and functionalities of our Python GUI, offering guidance on its usage and showcasing its potential for enhancing your modeling experience. 10.1 Installing and Running the GUI To kickstart your exploration of oriented hypergraphs with our Python GUI, follow these simple steps to install and run the program: Step 1: Get the Code Visit our GitHub repository at https://github.com/ZephyrSV/tfg_python/ and clone or download the code to your local machine. Step 2: Install python Ensure that you have Python installed on your system. If not, download and install it from the official Python website: https://www.python.org/downloads/ 53 Step 3: Install AMPL Make sure you have at least the free community version of AMPL installed on your device. You can download it from the AMPL website: https://ampl.com/start-free-now/ Step 4: Set up the virtual environment Next, create a virtual environment (venv) to isolate dependencies for the GUI. Open your terminal or command prompt and navigate to the directory containing the program files. Execute the following commands: # Create a virtual environment python -m venv venv # Activate the virtual environment # On Windows venv\Scripts\activate # On Unix or MacOS source venv/bin/activate This creates and activates the virtual environment. Note: Depending on your terminal app, you may need to use a different activation script (e.g., ‘activate.ps1‘ on Windows Powershell). Step 5: Install Dependencies While the virtual environment is active, install the required libraries using the following command: pip install -r requirements.txt This command installs the necessary dependencies for the GUI within the virtual environment. Step 6: Run the GUI With the virtual environment still active and AMPL installed, navigate to the directory containing the program files and run the following command: python3 App.py This command launches the Python GUI application. 10.2 Pathway Selector The ”Pathway Selector” serves as the central hub for navigating and interacting with our program. Below, we show 2 screenshots. The first one (Figure 13) is of the main page as it is shown to the user. The second (Figure 14) shows the same image except that we have included labels for each feature present on the main page. We will then refer to these labels in the rest of the section. Figure 13: Pathway Selector - User view Figure 14: Pathway Selector - Labeled Features 54 Let’s explore the features available on this main page: Pathway Selection Options: 1. Select by ID: Utilize the dropdown menu to choose a pathway based on its unique identifier (ID). The user can also type in a search string in the field and pressing enter. The dropdown will then filter out all entries that do not contain the search string. 2. Select by Description: Alternatively, you can opt for pathway selection by choosing a human-readable description from the dropdown menu. In the same way as before, the user can also type in a search string in the field and pressing enter. The dropdown will then filter out all entries that do not contain the search string. Buttons and Actions: 3. Show Image: Clicking this button will fetch and display the image of the selected pathway from the KEGG database, providing a visual representation of its structure. See Figure 15 for an example. 4. Update Dataset: This button allows the user to rebuild the dataset used to create the models of the pathways. 5. Select: Access the solver/visualizer tool by clicking this button, enabling in-depth exploration and analysis of the chosen pathway. 6. Benchmark: Evaluate and compare model performances on 25 models, facilitating comprehensive assessments. Figure 15: Show Image - Image corresponding to the entry ’map00010’ 55 Note: Tooltips are available for each feature. Hover your mouse over any feature to view a brief explanation of its functionality. View Figure 16 for an example. Figure 16: Feature tooltips - tooltip of the show image button Upon pressing the Update Dataset button, a crucial warning message promptly emerges to alert the user about the potential duration of the operation, as depicted in Figure 17. Figure 17: Warning Message on Updating Dataset The warning message reads as follows: This operation is very time-consuming. It is possible that this operation may cause you to become IP-banned for a few minutes/hours from the KEGG REST API. If that is the case, you will have to wait until you are unbanned from the REST API before resuming. This will close the app, and the dataset will be downloaded upon re-launching.” This cautionary message aims to ensure that users are fully aware of the potential consequences and the time commitment associated with updating the dataset. It emphasizes the possibility of temporary IP-banning and provides guidance on the necessary steps if such an event occurs. 10.3 Pathway Solver/Visualizer The ”Solver/Visualizer” view provides a comprehensive environment for in-depth exploration and analysis of the selected pathway. This view offers tools and features that empower users to interact with the oriented hypergraph representation and derive meaningful insights. 56 However, should the user opt for extra restrictions, we pivot to utilizing the model ’Serret DualImply extra restrictions’ (refer to Section 8.5). As expounded in Section 8.6, this model is specifically designed to accommodate the additional constraints, as the mathematical robustness of the other model is insufficient for supporting these extra restrictions. 10.4 Benchmark View Upon initiating the ”Benchmark View,” users encounter a sleek and user-friendly interface, as showcased in Figure 28. Key components of this interface include a dropdown menu, enabling users to choose from solvers such as CBC, Gurobi, or CPLEX, and a prominent ”Start Benchmark” button. The purpose of this thoughtful design is to simplify the benchmarking process, ensuring a seamless experience for users evaluating solver performance across a spectrum of optimization scenarios. Figure 28: Benchmark View - User Interface Upon triggering the ”Start Benchmark” button, the benchmarking procedure commences. Each model, namely ’Model A,’ ’Model B,’ ’First Prototype,’ ’Serret UniImply,’ and ’Serret DualImply,’ undergoes 25 optimizations. Subsequently, the results are presented in a Tk.TreeView below, offering users a comprehensive overview of solver performance across various models and optimizations. The benchmarking process may take up to 4 minutes. Figure 29 illustrates the view after the completion of 2 benchmarks, each providing information on the date and time of completion, the utilized solver, and the average time taken by each model to solve individual optimization problems. Figure 29: Benchmark View - Completed Benchmarks For a more detailed analysis, users have the option to expand the benchmark report and delve into the completion details of each of the 25 entries, as demonstrated in Figure 30. 63 Figure 30: Benchmark View - Expanded Benchmarks 11 Program architecture and Data Structures In this section, we will discuss the program structure and data structure used in our project. The program structure refers to the organization and arrangement of the code, while the data structure refers to the way data is stored and manipulated within the program. 11.1 Design Choices and Development Approach When developing our application, we made deliberate design choices to ensure efficiency, readability, and maintainability. Here are the key aspects of our approach: • Choice of Programming Language: We opted for Python as our programming language due to its rapid development capabilities. Python allows us to iterate quickly and efficiently during the development process. •AMPL for Optimization: Our project involves solving optimization problems using AMPL. By leveraging the AMPL library, we can delegate complex optimization tasks to a powerful solver, focusing our efforts on the overall structure and logic of the program. • Readability over Efficiency: While efficiency is important, we prioritize code readability. A clear and readable codebase is essential for collaboration and future maintenance. Given that AMPL handles the heavy computational tasks, our Python code emphasizes clarity. • Utilization of Libraries: We make extensive use of libraries and frameworks to simplify development. Leveraging existing libraries allows us to benefit from established solutions and focus on the unique aspects of our application. • Modularity and Code Reusability: Our code is structured to be modular, with each component serving a specific purpose. This approach enhances code reusability and facilitates easier updates or modifications. These design choices collectively contribute to the effectiveness and maintainability of our application. Our development philosophy revolves around delivering a solution that is not only functional but also comprehensible for future enhancements or collaborations. 64 11.2 File Organization In our project, we follow a structured approach to organize our files. We have divided our code into multiple files based on their functionality and purpose. This modular approach helps in better code management and improves code reusability. 11.2.1 Entry Point of the Application The main file of our project is the App.py file, which serves as the entry point for our application. It creates an instance of Pathway selector Pathway selector(tk.Tk) from views/pathway selector.py and calls its mainloop() method to start the application. 11.2.2 Views The views folder contains all the files related to the user interface of our application. It contains the following files: pathway selector.py This file contains the code for the pathway selector window, which is the first window that appears when the application is launched and serves as the application’s home screen. It allows the user to select a pathway from the list of available pathways and click on the Select button to proceed to the next window, among other things. pathway view.py This file contains the code for the pathway view window. This window allows the user to solve a pathway problem using the selected pathway. It also allows the user to view a representation of the pathway and its reactions hence the name pathway view. benchmark view.py This file contains the code for the benchmark view window. This window allows the user to benchmark the performance of our AMPL models and compare the performance of various solvers. 11.2.3 Models The models folder contains all the files related to the AMPL models used in our project. model A.mod As described in Section 8.3.2. This model is used both in the benchmarking process and when solving a pathway in the pathway view when the user doesn’t select the Extra restrictions option. model B.mod As described in Section 8.3.2. This model is only used during the benchmarking process. serret dual imply extra restrictions.mod As described in Section 8.5. This model is use when solving a pathway in the pathway view when the user selects the Extra restrictions option. serret dual imply.mod A varient of the model described in Section 8.5 without the extra restrictions. This model is only used during the benchmarking process. serret old.mod This is the first prototype of our model as seen in Section 8.3.1. serret uni imply.mod As described in Section 8.7. This model is only used during the benchmarking process. 11.2.4 Utils The utils folder contains all the files related to the utility functions used in our project. ui utils.py This file contains utility functions related to the user interface of our application. Namely the pad function which is used to add padding to the user interface and the 65 GridUtils class which is used to simplify the process of adding widgets to the user interface when using the grid geometry manager from Tkinter. KEGGIntegration.py This file contains a singleton class, KEGGIntegration , that handles all the communication to the KEGG API as well as storing the results locally to avoid making additional calls upon relaunching. The class provides methods to retrieve data from the KEGG database and also has the ability to recover the stored data. 11.2.5 Dynamically Generated Files Several files are generated dynamically by our application. These files are stored in the following directories: dats/ This directory contains the files all the ’.dat’ files generated by our application. These files are used as input to the AMPL models. persitent data/ This directory contains the data retrieved from the KEGG API. A single file inhabits this directory, data.json , which, when created by our application, contains all the data retrieved from the KEGG API. This file is used to avoid making additional calls to the KEGG API upon relaunching our application. output/ This directory is the default output directory when a user chooses to save the output of a pathway problem. It also contains the output of the benchmarking process. 11.3 Classes and Data Structures In this section, we will discuss the classes and data structures used in our project. 11.3.1 KEGGIntegration The KEGGIntegration class serves as a central hub for interacting with the KEGG API and managing locally stored results to enhance efficiency. It follows the singleton pattern, ensuring only one instance of the class exists at a time. This is advantageous as a single instance effectively handles all communication with the KEGG API. During initialization, the class checks for existing data in the data.json file within the persistent data directory. If the file is absent, the class initiates the retrieval of data from the KEGG API, subsequently storing it in the data.json file for future reference. This approach optimizes performance by avoiding redundant API calls upon subsequent launches. Attributes: •data loc: A string variable that represents the location of the data.json file. It’s value is not edited throughout the execution of the program. (Data Structure: String) • map reaction id to substrates products ids: A dictionary that maps reaction IDs to lists of substrate and product compound IDs. (Data Structure: Dictionary) • map synonym to compound id: A dictionary that maps compound synonyms to compound IDs. (Data Structure: Dictionary) • broken reaction ids: A list that stores the IDs of broken reactions. (Data Structure: List) •fetched breaking reaction ids: A list that stores the IDs of fetched breaking reactions. (Data Structure: List) •map reaction id to list compound id: A dictionary that maps reaction IDs to lists of compound IDs. (Data Structure: Dictionary) 66 •map pathway id to list reaction id: A dictionary that maps pathway IDs to lists of reaction IDs. (Data Structure: Dictionary) • map pathway id to description: A dictionary that maps pathway IDs to pathway descriptions. (Data Structure: Dictionary) The KEGGIntegration class has the following methods: Private methods: •new (cls): This is a special method that is automatically called when creating a new instance of the class. It ensures that only one instance of the class can be created. • get remaining breaking reaction ids(self): This method retrieves the remaining breaking reaction IDs that have not been fetched yet. •dump data(self): This method saves the data of the class to the data.json file. •load data(self): This method loads the data from the data.json file. • compound verbose and reaction to id(self, compound verbose, reaction id): Given a compound verbose and reaction ID, finds a compound ID. •fetch broken reactions(self): This method fetches the IDs of broken reactions. •query for reactions(self, reactions: list): This method queries the KEGG database (GET of REST) for the reactions (by groups of 10) and adds them to the reactions list. •fetch reaction substrates products ids(self): Creates the map reaction id to substrate ids and product ids. Uses the result from the KEGG API endpoint /list/reaction, as well as self.map reaction id to list compound id and self.map synonym to compound id. • generate dat(self, pathway id: str): This private auxillary method generates the ’.dat’ file for the specified pathway ID. Public methods: • fetch map reaction id to list compound id(): This method fetches the KEGG REST API endpoint /link/compound/reaction and returns a dictionary that maps reaction IDs to lists of compound IDs. • fetch map synonym to compound id(): This method fetches the KEGG REST API endpoint /list/compound and returns a dictionary that maps compound synonyms to compound IDs. • fetch map pathway id to list reaction id(): This method fetches the KEGG REST API endpoint /link/reaction/pathway and returns a dictionary that maps pathway IDs to lists of reaction IDs. • fetch map pathway id to description(organism=None): This method fetches the KEGG REST API endpoint /list/pathway and returns a dictionary that maps pathway IDs to pathway descriptions. The optional organism parameter can be used to filter the pathways by organism. •generate dats(self, entries: list, overwrite: bool =False): This method generates the ’.dat’ files for the specified entries. The entries parameter is a list of pathway IDs, and the overwrite parameter determines whether to overwrite existing ’.dat’ files. 11.3.2 GridUtil The GridUtil class provides utility methods for managing the grid layout in a Tkinter-based GUI. This class facilitates the dynamic adjustment of row and column configurations to enhance 67 responsiveness during resizing. Here’s an overview of its functionalities: Attributes: •current row: An integer representing the current row index. •current column: An integer representing the current column index. Constructor: •init (self, row=0, column=0) : Initializes the GridUtil object with optional parameters for the initial row and column indices. It also initializes lists for rows and columns that should not be resized. Methods: •set row(self, row): Sets the current row index to the specified value. •set column(self, column): Sets the current column index to the specified value. •next row(self) : Increments the current row index and resets the current column index to zero. Returns the updated row index. •generate on resize(self) : Returns a function that will be called on window resize. This function dynamically configures row and column weights based on the current state. •do not resize col(self) : Adds the current column index to the list of columns that will not be resized. •do not resize row(self) : Adds the current row index to the list of rows that will not be resized. •place(self, rs=1, cs=1, sticky="we"): Returns a dictionary with grid parameters for placing Tkinter widgets. Advances the current column index by cs. This class is particularly useful for managing the grid layout and ensuring flexibility during GUI development. 11.3.3 Pathway selector The Pathway selector class provides a graphical user interface for selecting and exploring biochemical pathways. It utilizes the KEGGIntegration class to fetch pathway data and display relevant information. See Section 10.2 for a description of the graphical interface. Attributes: • executor: A class attribute representing the ThreadPoolExecutor for concurrent operations. • kegg integration: A class attribute representing the instance of the KEGGIntegration class. • search pool: A class attribute representing the list of pathways for the user to select from. Public methods: • init (): Initializes the Pathway selector instance, setting up the graphical interface and necessary attributes. • dropdown enter action(): Handles the dropdown’s enter action to select pathways based on descriptions. •dropdown id enter action(): Handles the dropdown’s enter action to select pathways based on IDs. 68 •set image(): Sets the image in the image label to the selected pathway. •show image button click(): Handles the click event for the ”Show Image” button. •select pathway button click(): Opens a new window with the selected pathway. •benchmark button click(): Opens a new window for benchmarking. •update data button click(): Gives a warning to the user and updates the dataset. •on dropdown select(event): Called when an option is selected in the dropdown for descriptions. • on dropdown id select(event): Called when an option is selected in the dropdown for IDs. •clear description label(event): Clears the description label. • set description label func(text): Returns a function that sets the description label to the given text. •dropdown set values(): Sets the values of the dropdown. The Pathway selector class’ graphical interface provides various functionalities such as selecting pathways, showing images, opening pathway windows, benchmarking, and updating the dataset. The class maintains integration with the KEGGIntegration class for seamless data retrieval and updates. 11.3.4 Pathway view The Pathway view class provides a graphical user interface for solving biochemical pathways. It utilizes the KEGGIntegration class to fetch pathway data and generate ’.dat’ files for solving. See Section 10.3 for a description of the graphical interface. Attributes: • save result to file var: An integer variable representing the state of the ”Save Result to File” checkbox. •save result to file: A checkbox indicating whether to save the result to a file. • visualize result var: An integer variable representing the state of the ”Visualize Result” checkbox. •visualize result: A checkbox indicating whether to visualize the solved pathway. • use extra restrictions var: A boolean variable representing the state of the ”Use Extra Restrictions” checkbox. •use extra restrictions: A checkbox indicating whether to use extra restrictions in the pathway model. •solve 5s count: A counter for managing the display duration of the ”Solved!” message. •solvers: A dictionary mapping solver names to their corresponding identifiers. These attributes include counters, settings for solving and visualizing options, and variables related to saving results and using extra restrictions. Methods: • create extra restrictions frame(self, parent): Creates the frame for managing extra restrictions, including labels and modifiers for uninvertibles, forced externals, and forced internals. 69 • create tickboxes(self, parent): Creates tickboxes for options like saving results to a file, visualizing results, and using extra restrictions. • init (self, master, entry, mainloop=True): Initializes the ‘PathwayView‘ instance. It sets up the UI elements, including labels, solver selection, tickboxes, extra restrictions frame, and buttons for solving the pathway. • solve(): Solves the pathway using AMPL, handling various solve outcomes and displaying results. •five secs after solve(): Removes the ”Solved!” message after 5 seconds. •build save to file printer(self, file path): Returns a printer function for saving results to a specified file. •print result(self, ampl, execution time, printers=None): Prints the computed results, including execution time, internal vertices, and detailed reaction information. • get ampl variables(self, ampl): Retrieves AMPL variables and sets necessary for pathway analysis. •build graph(self): Builds a graph representation of the pathway using NetworkX. •build figure(self, G, pos, include labels=True): Builds and returns a figure for visualization, including nodes, edges, and labels. • draw canvas frame(self): Draws and updates the canvas frame for visualizing the pathway graph. It includes functionality to toggle labels and a button for that purpose. • hide show extra restrictions(self): Hides or shows the extra restrictions frame based on the state of the ”Use Extra Restrictions” checkbox. • get data from dat(self): Parses data from the DAT file, including reactions, compounds, uninvertibles, forced externals, and forced internals. • rewrite extra restrictions in dat(self): Rewrites extra restrictions in the DAT file based on current data. Inner classes: • ExtraRestrictionsModifier: An inner class for modifying extra restrictions. It provides methods for adding and removing elements from the list. • Printer: An inner class representing a printer for handling file output. It initializes a file for writing, has a ‘ call ‘ method for writing data to the file, and a ‘ del ‘ method to close the file. 11.3.5 Benchmark view The Benchmark view class provides a graphical user interface for running benchmarks using various solvers and models. It interacts with the KEGGIntegration class to fetch data and generate ’.dat’ files for benchmarking. See Section 10.4 for a description of the graphical interface. Attributes: •solvers: A dictionary mapping solver names to their corresponding identifiers. •models: A dictionary mapping model names to their file paths. •dats: A dictionary to store ’.dat’ files for benchmark entries. 70 •result count: An integer representing the count of benchmark results. •current test id: A string representing the current test identifier. •file: A file object for writing benchmark results. Public methods: •init (self, master): Initializes the Benchmark view instance, setting up the graphical interface and necessary attributes. •start button click(): Starts the benchmark in a separate thread, creating a new entry in the Treeview and initiating the benchmarking process. • run benchmark(): Runs the benchmark process, handling the entire workflow from data preparation to solving entries. •prepare dats(): Prepares the ’.dat’ files for benchmark entries. •solve all entries(): Solves all benchmark entries using the selected solver and models, updating the graphical interface and writing results to a file. •set benchmark average(entry, solver id, valid duration lists): Sets the benchmark average for a specific entry and solver. •get last entry treeview id(): Retrieves the last entry ID from the Treeview. • insert to treeview(parent, text, *values): Inserts a new entry into the Treeview component of the graphical interface. • create tickboxes(parent): Creates tickboxes in the graphical interface for specific options. 12 Conclusions and final thoughts 12.1 Summary of Contributions In this thesis, we have presented a comprehensive study on orienting hyperedges in the context of metabolistic pathways. Our investigation focused on the elaboration of a AMPL model that would allow the a researcher to obtain a good solution by using ILP optimization. The major contributions of our work include: • The creation of a logically robust model that can be used to solve the problem of orienting hyperedges in a metabolistic pathway. • The introduction of additional constraints believed to have some significance in the field of metabolistic pathways. These include: 1. Preventing the inversion of certain reactions. 2. Marking certain vertices as internal. 3. Marking certain vertices as external. • We have benchmarked the model with respect to alternative models, established its strengths and weaknesses and discussed when it is most appropriate to apply it. 71 12.2 Limitations and Challenges While our research has provided valuable insights, it is important to acknowledge the limitations and challenges encountered during the study. These limitations include: •Currently, there is no proof that the problem is P or NP. Although we strongly suspect that the problem is NP, if it is discovered that it is P, there may exist a polynomial-time algorithm that finds the optimal set of solutions. • As mentioned in Section 1.3, there currently isn’t a consensus on whether our results bear any biological significance. 12.3 Future Research Directions Building on the findings of this thesis, there are several promising avenues for future research. These may include: •To determine whether the results of our model can be used to predict the direction of reactions in a metabolistic pathway. •The creation of a tool to better way to visualize hyper-graphs. •To analyse the problem of maximizing the number of internal vertices of a hyper-graph to determine whether it is NP-hard. 12.4 Final Thoughts In concluding this thesis, we have embarked on a journey to tackle the complex challenge of orienting hyperedges in metabolic pathways. Our endeavor has yielded a robust AMPL model that stands as a valuable tool for researchers grappling with the intricacies of metabolic network analysis. The quest to understand the biological significance of our results remains an ongoing endeavor. The ambiguity surrounding the P or NP nature of the problem underscores the intricate nature of metabolic pathway orientation. This uncertainty fuels our curiosity and motivates us to delve deeper into the underlying complexities. I would like to express my sincere gratitude to Professor Gabriel Valiente Feruglio for offering me the invaluable opportunity to study this fascinating topic. Their guidance, encouragement, and unwavering support have played a pivotal role in shaping my academic journey. As we close this chapter, it is our hope that this work sparks curiosity and inspires future researchers to continue unraveling the mysteries within metabolic networks. 72