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.
fonte
Respostas:
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.
fonte