Algoritmos de búsqueda de bases de datos de teoría de gráficos métricos

9

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.

reference-request Aaron Sterling
fuente
¿Qué tan importante es que la base de datos tenga información métrica? hay toneladas de trabajo en la búsqueda de bases de datos de gráficos, incluso en el ámbito bio, pero no sé sobre el tema de la etiqueta de volumen / distancia
Suresh Venkat
Conoceré la respuesta a tu pregunta en una o dos semanas. Las similitudes y diferencias con los problemas de bioinformática aún no están claras para mí.
Aaron Sterling

Respuestas:

2

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.

Rafael
fuente