Complexidade de algoritmos e problemas de isomorfismo em grafos

• Processo: 24/18244-8
• Modalidade de apoio: Bolsas no Brasil - Programa Estímulo a Vocações Científicas
• Data de Início da vigência: 01 de julho de 2025
• Data de Término da vigência: 10 de agosto de 2025
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Ana Shirley Ferreira da Silva
• Beneficiário: Carlos Daniel Marques Santos Simões
• Instituição Sede: Centro de Ciências. Universidade Federal do Ceará (UFC). Ministério da Educação (Brasil). Fortaleza , SP, Brasil
• Assunto(s): Teoria dos grafos Isomorfismo Algoritmos
• Palavra(s)-Chave do Pesquisador: Grafos rotulados | Isomorfismos de grafos | Técnicas de construção de algoritmos | teoria dos grafos | Teoria dos grafos

Resumo

O início do estágio do aluno na Universidade Federal do Ceará deverá ocorrer em julho de 2025. Até lá, o aluno bolsista estará envolvido em um projeto cujo objetivo é identificar a reatividade cruzada de receptores de células T (TCRs) por meio da análise estrutural de peptídeos antigênicos. A reatividade cruzada ocorre quando um TCR é capaz de reconhecer múltiplos peptídeos diferentes, resultando em respostas imunes diversificadas. Entretanto, a previsão dessa reatividade é complexa devido à natureza intricada das interações entre TCRs e antígenos.No projeto sendo desenvolvido atualmente pelo aluno, tanto os peptídeos antigênicos quanto os TCRs são modelados como grafos, em que os nós representam resíduos de aminoácidos e as arestas descrevem as interações espaciais e químicas. O isomorfismo de grafos é utilizado para identificar similaridades estruturais entre peptídeos distintos e prever possíveis interações cruzadas com os mesmos receptores. Métodos eficientes de correspondência de subgrafos e busca de padrões são aplicados para detectar regiões estruturais compartilhadas, sugerindo potenciais casos de reatividade cruzada.Como o aluno tem utilizado a teoria dos grafos de maneira prática e aplicada, este projeto busca aprofundar seu conhecimento teórico, com foco especial no problema de isomorfismo em grafos. Pretendemos promover uma troca rica entre teoria e prática, proporcionando aprendizado mútuo. Essa abordagem permitirá identificar com precisão o problema teórico subjacente ao desafio prático, viabilizando a busca por algoritmos gerais já existentes ou a adaptação de métodos propostos para o problema específico durante a iniciação científica do aluno. Considerando que, na prática, a eficiência do algoritmo é um fator crucial, também nos propomos a realizar um estudo teórico da complexidade dos algoritmos e de métodos básicos de construção.A primeira fase do projeto será dedicada a discussões sobre o trabalho que o aluno desenvolveu ao longo do ano anterior. O objetivo é extrair dessa troca uma formulação matemática baseada na teoria dos grafos que descreva o problema prático. Chamemos este de Problema P. Estimamos que essa etapa dure até dois dias. Em seguida, o aluno irá simultaneamente pesquisar algoritmos existentes para o problema teórico identificado (Problema P) ou para problemas correlatos, enquanto estuda os fundamentos da teoria dos grafos, complexidade de algoritmos e técnicas de construção. Esta fase deverá durar aproximadamente 10 dias. A fase de estudo será acompanhada pela orientadora, com encontros para tira dúvidas.Após isso, escolheremos ao menos um artigo relevante que resolva o Problema P, ou algum problema correlato, para um estudo mais aprofundado das técnicas envolvidas. Como é pouco provável que existam algoritmos específicos para o problema identificado, acreditamos que o estudo poderá esclarecer: 1. a viabilidade de empregar ao Problema P técnicas que são atualmente empregadas em problemas correlatos; ou 2. a aplicabilidade ao(s) problema(s) correlato(s) dos métodos utilizados pelo aluno no problema prático durante sua iniciação científica. Esperamos que essa etapa dure 13 dias. Por fim, iniciaremos a aplicação da abordagem escolhida (passo 1 ou 2) de acordo com os achados na literatura. Esta fase ocupará o restante do período do estágio, que, se as etapas anteriores forem concluídas dentro do prazo previsto, corresponderá aos últimos 15 dias. (AU)