Algorithm complexity and isomorphism problems on graphs

• Grant number: 24/18244-8
• Support Opportunities: Scholarships in Brazil - Program to Stimulate Scientific Vocations
• Start date: July 01, 2025
• End date: August 10, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Ana Shirley Ferreira da Silva
• Grantee: Carlos Daniel Marques Santos Simões
• Host Institution: Centro de Ciências. Universidade Federal do Ceará (UFC). Ministério da Educação (Brasil). Fortaleza , SP, Brazil

Abstract

The student's internship at the Federal University of Ceará is expected to begin in July 2025. Until then, the scholarship student will be involved in a project aimed at identifying the cross-reactivity of T-cell receptors (TCRs) through the structural analysis of antigenic peptides. Cross-reactivity occurs when a TCR is capable of recognizing multiple different peptides, leading to diverse immune responses. However, predicting this cross-reactivity is challenging due to the complex nature of interactions between TCRs and antigens.In the project currently being developed by the student, both the antigenic peptides and the TCRs are modeled as graphs, where the nodes represent amino acid residues and the edges describe spatial and chemical interactions. Graph isomorphism is used to identify structural similarities between different peptides and predict possible cross-reactive interactions with the same receptors. Efficient subgraph matching methods and pattern search algorithms are applied to detect shared structural regions between antigenic peptides, suggesting potential cases of cross-reactivity.As the student has been using graph theory in a practical and applied way, this project aims to deepen their theoretical knowledge, with a special focus on the problem of graph isomorphism. We intend to foster a rich exchange between theory and practice, providing mutual learning. This approach will allow us to accurately identify the theoretical problem underlying the practical challenge, enabling the search for existing general algorithms or the adaptation of methods proposed for the specific problem during the student's research initiation. Considering that, in practice, the efficiency of the algorithm is a crucial factor, we also propose to conduct a theoretical study of algorithm complexity and basic construction methods.The first phase of the project will be dedicated to discussions about the work the student developed over the previous year. The goal is to derive from these discussions a mathematical formulation based on graph theory that describes the practical problem. Let us call this Problem P. We estimate that this phase will last up to two days. Then, the student will simultaneously research existing algorithms for the identified theoretical problem (Problem P) or related problems while studying the fundamentals of graph theory, algorithm complexity, and construction techniques. This phase is expected to last approximately 10 days. The study phase will be supervised by the advisor, with regular meetings for clarification.After that, we will choose at least one relevant article that addresses Problem P, or a related problem, for a more in-depth study of the techniques involved. Since it is unlikely that specific algorithms exist for the identified problem, we believe that the study will clarify: 1. the feasibility of applying to Problem P techniques that are currently used in related problems; or 2. the applicability of the methods used by the student in the practical problem during their research initiation to the related problem(s). We expect this stage to last 13 days. Finally, we will begin applying the chosen approach (step 1 or 2) according to the findings in the literature. This phase will occupy the remainder of the internship period, which, if the previous stages are completed within the expected time, will consist of the final 15 days of the internship. (AU)