Ring detection

From Open Babel
Revision as of 14:54, 25 February 2006 by Joerg Kurt Wegner (Talk | contribs) (typo)

Jump to: navigation, search

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},
}