Ich schreibe (langsam) eine Rezension des Handbuchs der Chemoinformatik-Algorithmen für SIGACT News. In einem Kapitel werden aktuelle Software-Implementierungen erläutert, und die Datenbanksuchen (und andere Anwendungen) scheinen nicht so viele Informationen über die Diagramme zu nutzen, wie sie könnten. Andererseits wären theoretischere Algorithmen möglicherweise zu schwer zu implementieren. Es scheint jedoch ein potenzieller offener Bereich zu sein.
Hier ist meine Frage:
Gibt es eine Übersicht (oder eine kleine Handvoll Referenzen), die Theorie und Implementierung (hoffentlich) von Algorithmen von Datenbanken von Graphen mit metrischen Informationen diskutiert ? (Jede Kante ist ein Abstand, und jeder Scheitelpunkt hat ein Volumen.) Eine chemiefreie Beschreibung eines Beispielproblems wäre: Suchen Sie in einer Datenbank mit Diagrammen alle, die einen bestimmten Untergraphen enthalten.
quelle
Antworten:
Dies scheint mit dem Subgraph-Isomorphismus-Problem in Zusammenhang zu stehen, das im Allgemeinen auch ohne Gewichte NP-vollständig ist. Der entsprechende Wikipedia-Artikel behauptet jedoch, dass er in bestimmten Fällen effizient gelöst werden kann.
Wenn Chemie etwas mit Bioinformatik zu tun hat, werden Sie wahrscheinlich an Approximationsalgorithmen interessiert sein, um mit Rauschen umzugehen. Bei der Suche nach Datenbanken als Anwendung gibt es möglicherweise clevere Ideen für die Vorverarbeitung, die Ihnen gute amortisierte Laufzeiten bieten.
Gefunden (nicht gelesen) diese:
http://www.springerlink.com/content/4751121q3575v041/
http://bioinformatics.oxfordjournals.org/content/23/2/232.full
http://portal.acm.org/citation.cfm?id=1368898
Haftungsausschluss : Nochmals, entschuldigen Sie die Antwort im Kommentarstil. Ich darf noch keinen Kommentar abgeben.
quelle