# Difference between revisions of "Ring detection"

From Open Babel

(Initial page) |
m (typo) |
||

Line 1: | Line 1: | ||

Extensive reviews about ring detection algorithms can be found in the work of Lynch et al. [dghl89], Gleiss [gle01], and Downs [dow03]. | Extensive reviews about ring detection algorithms can be found in the work of Lynch et al. [dghl89], Gleiss [gle01], and Downs [dow03]. | ||

− | One of the most often used ring sets in | + | One of the most often used ring sets in Cheminformatics application is the Smallest Set of Smallest Rings (SSSR) [fig96]. This algorithms is a combination of the breadth first search (BFS) of Balducci [bp94] and the node elimination procedure of Doucet [fpdb93]. |

== References == | == References == |

## Revision as of 14:54, 25 February 2006

Extensive reviews about ring detection algorithms can be found in the work of Lynch et al. [dghl89], Gleiss [gle01], and Downs [dow03].

One of the most often used ring sets in Cheminformatics application is the Smallest Set of Smallest Rings (SSSR) [fig96]. This algorithms is a combination of the breadth first search (BFS) of Balducci [bp94] and the node elimination procedure of Doucet [fpdb93].

## References

@Article{bp94, author = {R. Balducci and R. S. Pearlman}, title = {{E}fficient {E}xact {S}olution of the {R}ing {P}erception {P}roblem}, journal = {J. Chem. Inf. Comput. Sci.}, year = {1994}, volume = {34}, pages = {822-831}, }

@Article{dghl89a, author = {G. M. Downs and V. J. Gillet and J. D. Holliday and M. F. Lynch}, title = {{R}eview of {R}ing {P}erception {A}lgorithms for {C}hemical {G}raphs}, journal = {J. Chem. Inf. Comput. Sci.}, year = {1989}, volume = {29}, pages = {172-187}, }

@Article{dghl89b, author = {G. M. Downs and V. J. Gillet and J. D. Holliday and M. F. Lynch}, title = {{T}heoretical {A}spects of {R}ing {P}erception and {D}evelopment of the {E}xtended {S}et of {S}mallest {R}ings {C}oncept}, journal = {J. Chem. Inf. Comput. Sci.}, year = {1989}, volume = {29}, pages = {187-206}, abstract = {There are many unresolved issues concerning the definition of an optimum ring set for retrieval purposes. This paper considers the problems associated with processing planar (two-dimensional) representations of three-dimensional structures. To overcome the ambiguity of such representations, a new ring set is defined in terms of simple faces and cut faces. The concept of a cut-vertex graph is introduced to explain the combinatorial relationship between the number of simple faces and the number of planar embedments.}, }

@PhdThesis{gle01, author = {P. M. Gleiss}, title = {{S}hort {C}ycles -- {M}inimum {C}ycle {B}ases of {G}raphs from {C}hemistry and {B}iochemistry}, school = {University of Wien}, year = {2001}, address = {Wien}, }

@InProceedings{dow03, author = {G. M. Downs}, title = {{R}ing {P}erception}, booktitle = {{H}andbook of {C}hemoinformatics}, year = {2003}, editor = {J. Gasteiger}, volume = {1}, pages = {161--177}, address = {Weinheim, Germany}, publisher = {Wiley--VCH}, chapter = {II.5.2}, isbn = {3--527--30680--3}, }

@Article{fig96, author = {J. Figueras}, title = {{R}ing {P}erception {U}sing {B}readth--{F}irst {S}earch}, journal = {J. Chem. Inf. Comput. Sci.}, year = {1996}, volume = {36}, pages = {986-991}, abstract = {Combining breadth-first search with new ideas for uncovering embedded rings in complex systems 1 yields a very fast routine for ring perception. With large structures, the new routine is orders of magnitude faster than depth-first ring detection, a result expected on the basis of recent work that establishes polynomial order for BFS.2}, contents = {Smallest Set of Smallest Ring (SSSR), Bread First Search (BFS), Binary Edge Encoded Path (BEEP), message passing algorithm}, topics = {Smallest Set of Smallest Ring (SSSR), Bread First Search (BFS), Binary Edge Encoded Path (BEEP), message passing algorithm}, }

@Article{fpdb93, author = {B. T. Fan and A. Panaye and J.-P. Doucet and A. Barbu}, title = {{R}ing {P}erception. {A} {N}ew {A}lgorithm for {D}irectly {F}inding the {S}mallest {S}et of {S}mallest {R}ings from a {C}onnection {T}able}, journal = {J. Chem. Inf. Comput. Sci.}, year = {1993}, volume = {33}, pages = {657-662}, }