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).

There are several variants of the motif search problem in the literature, with many applications in bioinformatics. In the variant called motif search in graphs, proposed in 2006, we are given a colored graph G, a multiset of colors M (called motif ) and we seek for a connected induced subgraph of G which contains the colors of M. When the given motif cannot be found in G, we seek for an approximate match of it, considering some approximation criteria. In the mentioned work, it was proved that the problem is NP-hard even though G is restricted to trees and an exact enumeration algorithm was proposed, which enumerates only small-size motifs (containing at most 4 vertices). In 2018, an integer programming approach was proposed for the special case where G is restricted to trees. In the present work, we present integer programming models for this problem and propose a branch-and-cut approach for the general case of it (when G is an arbitrary graph). The solution connectivity constraints are added to the model as cutting planes. With a small adaptation of this approach, we get an enumeration algorithm. The presented approach was able to solve instances from protein-protein interaction networks containing, after pre-processing, approximately 3,000 proteins (vertices) and 4,100 interactions between them (edges)