(Powoli) piszę recenzję Podręcznika algorytmów chemoinformatycznych dla SIGACT News. Jeden rozdział omawia bieżące implementacje oprogramowania, a wyszukiwania w bazie danych (i inne aplikacje) wydają się nie wykorzystywać tak dużej ilości informacji o wykresach, jak mogłyby. Z drugiej strony być może bardziej teoretyczne algorytmy byłyby zbyt trudne do wdrożenia. Wygląda jednak na potencjalnie otwarty teren.
Oto moje pytanie:
Czy istnieje przegląd (lub garstka odniesień) omawiający teorię i implementację (miejmy nadzieję) algorytmów baz danych wykresów z informacjami metrycznymi? (Każda krawędź jest odległością, a każdy wierzchołek ma objętość.) Bezchemiczny opis przykładowego problemu brzmiałby: biorąc pod uwagę bazę danych grafów, znajdź wszystkie, które zawierają określony podgraf.
źródło
Odpowiedzi:
Wydaje się, że jest to związane z problemem izomorfizmu subgrafu, który ogólnie jest NP-kompletny, nawet bez żadnych obciążników. Odpowiedni artykuł w Wikipedii twierdzi jednak, że w niektórych przypadkach można go skutecznie rozwiązać.
Jeśli chemo jest czymś w rodzaju bioinformatyki, prawdopodobnie i tak będziesz zainteresowany algorytmami aproksymacji w celu radzenia sobie z hałasem. Ponadto, biorąc pod uwagę wyszukiwanie bazy danych jako aplikację, mogą istnieć sprytne pomysły na wstępne przetwarzanie, które zapewnią dobre zamortyzowane środowiska wykonawcze.
Znaleziono (nie przeczytano) te:
http://www.springerlink.com/content/4751121q3575v041/
http://bioinformatics.oxfordjournals.org/content/23/2/232.full
http://portal.acm.org/citation.cfm?id=1368898
Uwaga : Ponownie przepraszam za odpowiedź w stylu komentarza; Nie mogę jeszcze komentować.
źródło