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
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
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://teses.usp.br/teses/disponiveis/100/100131/tde-24082022-162352/. Acesso em: 09 abr. 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://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 abr. 09 ] Available from: https://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 abr. 09 ] Available from: https://teses.usp.br/teses/disponiveis/100/100131/tde-24082022-162352/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
