Estoy (lentamente) escribiendo una reseña del Manual de Algoritmos de Quimioinformática para SIGACT News. Un capítulo analiza las implementaciones de software actuales, y las búsquedas en la base de datos (y otras aplicaciones) no parecen aprovechar tanta información sobre los gráficos como podrían. Por otro lado, quizás los algoritmos más teóricos serían demasiado difíciles de implementar. Sin embargo, parece un área abierta potencial.
Así que aquí está mi pregunta:
¿Existe una visión general (o un pequeño puñado de referencias) que discuta la teoría y la implementación (con suerte) de algoritmos de bases de datos de gráficos con información métrica? (Cada borde es una distancia y cada vértice tiene un volumen). Una descripción libre de químicos de un problema de ejemplo sería: dada una base de datos de gráficos, encuentre todos los que contengan un subgrafo particular.
fuente
Respuestas:
Esto parece estar relacionado con el problema de isomorfismo del subgrafo, que en general es NP completo, incluso sin ningún peso. Sin embargo, el artículo de Wikipedia correspondiente afirma que se puede resolver de manera eficiente en ciertos casos.
Si la quimioterapia se parece a la bioinformática, probablemente le interesen los algoritmos de aproximación para lidiar con el ruido, de todos modos. Además, dada la búsqueda en la base de datos como aplicación, puede haber ideas inteligentes para el preprocesamiento que le brinden buenos tiempos de ejecución amortizados.
Encontrado (no leído) esos:
http://www.springerlink.com/content/4751121q3575v041/
http://bioinformatics.oxfordjournals.org/content/23/2/232.full
http://portal.acm.org/citation.cfm?id=1368898
Descargo de responsabilidad : de nuevo, perdón por la respuesta al estilo de comentario; Todavía no tengo permiso para comentar.
fuente