Experimentos e métodos de otimização combinatória para o problema de subconjuntos tropicais em grafos

• Processo: 21/07080-6
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Vigência: 01 de outubro de 2021 - 30 de setembro de 2024
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Karla Roberta Pereira Sampaio Lima
• Beneficiário: Karla Roberta Pereira Sampaio Lima
• Instituição Sede: Escola de Artes, Ciências e Humanidades (EACH). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Otimização combinatória Programação linear inteira Grafos Biologia computacional Algoritmos
• Palavra(s)-Chave do Pesquisador: grafos | Otimização Combinatória | programação linear inteira | Otimização Combinatória e Grafos

Resumo

O desenvolvimento de ferramentas baseadas em modelos matemáticos robustos para lidar com problemas reais e computacionalmente intratáveis tem se alinhado cada vez mais às técnicas de otimização combinatória e à programação linear inteira devido ao enorme avanço tecnológico e a real necessidade de tratar grandes volumes de dados. Esses problemas intratáveis emergem da medicina, da bioinformática, da indústria, da logística e naturalmente recorrem à ciência da computação como meio para solucionar problemas de alta complexidade. A maioria dos problemas computacionais envolvidos na análise de dados biológicos, por exemplo, são de difícil resolução, conhecidos como problemas NP-difíceis, o que a priori fazem com que os pesquisadores se sintam desmotivados e limitados na busca por resultados satisfatórios. Em contrapartida, o uso das técnicas de Otimização Combinatória na análise de tais dados com a finalidade de reconhecer determinados padrões estruturais, tem proporcionado grandes conquistas no campo da bioinformática. Neste projeto, será investigado o problema de busca por padrões estruturais específicos em redes que podem representar interações biológicas, tais como redes metabólicas, neurológicas, de interação entre proteínas (PPI), dentre outras. Os objetivos consistem em desenvolver modelos matemáticos bem delimitados, implementar cada modelo proposto com a associação de técnicas algorítmicas da combinatória poliédrica e avaliar a qualidade de cada modelo tanto do ponto de vista teórico, com o desenvolvimento de algoritmos de aproximação, algoritmos exatos, construção de provas da corretude do modelo, quanto do ponto de vista prático com a implementação dos modelos e algoritmos propostos com intuito de obter soluções ótimas para instâncias reais de grande porte. O alcance final do projeto consiste em entregar uma ferramenta baseada em programação linear inteira e incorporada de técnicas e algoritmos da otimização combinatória que possa ser interpretada e viabilizada para o uso de problemas reais da bioinformática. O projeto será desenvolvido com o apoio de colaboradores nacionais e internacionais, e alunos de mestrado da proponente. (AU)