Algoritmos de pesquisa de banco de dados da teoria dos gráficos

9

Estou (lentamente) escrevendo uma resenha do Handbook of Chemoinformatics Algorithms for SIGACT News. Um capítulo discute as implementações atuais de software, e as pesquisas no banco de dados (e outros aplicativos) não parecem tirar o máximo proveito possível das informações sobre os gráficos. Por outro lado, talvez mais algoritmos teóricos sejam muito difíceis de implementar. Parece uma área potencial aberta, no entanto.

Então aqui está a minha pergunta:

Existe uma visão geral (ou um pequeno punhado de referências) que discuta teoria e implementação (espero) de algoritmos de bancos de dados de gráficos com informações métricas? (Cada aresta está a uma distância e cada vértice tem um volume.) Uma descrição sem química de um exemplo de problema seria: dado um banco de dados de gráficos, encontre todos eles que contenham um subgráfico específico.

Aaron Sterling
fonte
Quão importante é que o banco de dados tenha informações métricas? há toneladas de trabalho em busca de dados de gráficos, mesmo no reino bio, mas eu não sei sobre a questão rótulo de volume / distância
Suresh Venkat
Eu saberei a resposta para sua pergunta em uma semana ou duas. As semelhanças e diferenças com os problemas de bioinformática ainda não estão claras para mim.
Aaron Sterling

Respostas:

2

Isso parece estar relacionado ao problema de isomorfismo do subgráfico, que geralmente é NP completo, mesmo sem pesos. O artigo correspondente da Wikipedia afirma que ele pode ser resolvido com eficiência em certos casos.

Se a quimio- é algo como bioinformática, você provavelmente estará interessado em algoritmos de aproximação para lidar com o ruído. Além disso, dada a pesquisa no banco de dados como aplicativo, pode haver idéias inteligentes para pré-processamento que oferecem bons tempos de execução amortizados.

Encontrados (não lidos) aqueles:

http://www.springerlink.com/content/4751121q3575v041/

http://bioinformatics.oxfordjournals.org/content/23/2/232.full

http://portal.acm.org/citation.cfm?id=1368898

Disclaimer : Mais uma vez, desculpe pela resposta no estilo de comentário; Ainda não tenho permissão para comentar.

Rafael
fonte