Modelos de programação inteira para o problema de busca de motivos em redes biológicas (2022)
- Authors:
- Autor USP: PRAZERES, RICARDO MOLINARI DOS - EACH
- Unidade: EACH
- DOI: 10.11606/D.100.2022.tde-24082022-162352
- Subjects: BIOINFORMÁTICA; TEORIA DOS GRAFOS; ALGORITMOS
- Keywords: Branch-and-cut; Busca de motivos; Graph motif; Integer programming; Motif search; Motivo em grafos; Programação inteira; Protein-protein interaction networks; Redes de interação proteína-proteína
- Language: Português
- Abstract: Existem diversas variantes do problema de busca de motivos na literatura, com muitas aplicações em bioinformática. Na variante denominada busca de motivos em grafos, proposta em 2006, dado grafo colorido G, um multiconjunto de cores M (chamado motivo), buscamos um subgrafo conexo induzido de G que contém as cores de M. Quando o motivo não pode ser encontrado em G, buscamos uma ocorrência aproximada dele, considerando alguns critérios de aproximação. No trabalho mencionado, provou-se que o problema é NP-difícil mesmo que G esteja restrito a árvores e foi proposto um algoritmo exato de enumeração, que enumera apenas motivos pequenos (contendo no máximo 4 vértices). Em 2018, foi proposta uma abordagem baseada em programação inteira para o caso especial em que G está restrito a árvores. No presente trabalho, apresentamos modelos de programação inteira para o referido problema e propomos uma abordagem branch-and-cut para o caso geral do problema (quando G é um grafo arbitrário). As restrições de conexidade da solução são adicionadas ao modelo como planos de corte. Com uma pequena adaptação dessa abordagem, obtemos um algoritmo de enumeração. A abordagem apresentada conseguiu resolver instâncias provenientes de redes de interação proteína-proteína contendo, após pré-processamento, aproximadamente 3.000 proteínas (vértices) e 4.100 interações entre elas (arestas)
- Imprenta:
- Data da defesa: 30.06.2022
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
PRAZERES, Ricardo Molinari dos. Modelos de programação inteira para o problema de busca de motivos em redes biológicas. 2022. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2022. Disponível em: https://www.teses.usp.br/teses/disponiveis/100/100131/tde-24082022-162352/. Acesso em: 01 jan. 2026. -
APA
Prazeres, R. M. dos. (2022). Modelos de programação inteira para o problema de busca de motivos em redes biológicas (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/100/100131/tde-24082022-162352/ -
NLM
Prazeres RM dos. Modelos de programação inteira para o problema de busca de motivos em redes biológicas [Internet]. 2022 ;[citado 2026 jan. 01 ] Available from: https://www.teses.usp.br/teses/disponiveis/100/100131/tde-24082022-162352/ -
Vancouver
Prazeres RM dos. Modelos de programação inteira para o problema de busca de motivos em redes biológicas [Internet]. 2022 ;[citado 2026 jan. 01 ] Available from: https://www.teses.usp.br/teses/disponiveis/100/100131/tde-24082022-162352/
Informações sobre o DOI: 10.11606/D.100.2022.tde-24082022-162352 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
