Protein structure analysis through Hough transform and range tree

The Generalized Hough Transform (GHT) allows to recognize general patterns once defined a model to be recognized, a reference point (RP) rigid with the model, and a mapping rule. This rule establishes the contributions in the parameters space; this space, generally speaking, is given by the parameters of a rigid motion leading to overlap a model item with an equal item detected on the unknown pattern. In this paper we introduce the GHT applied to motifs, domains and entire proteins retrieval into a protein data base. The spatial attitude of a single protein secondary structure (SS) constitutes the item supporting the contributions. If the unknown pattern contains a block of N SS of the model to be recognized, the N corresponding votes will have a common point, so accumulating N contributions. An analysis of the neighborhoods around the areas with high contributions density is necessary. It is not sufficient and often inaccurate to limit the analysis to the peaks even if the number of contribution is closed to the expected one. Both convenient data structures for effectively operating in the neighborhoods (a range tree data structure) and suitable decision criteria have been introduced. Preliminary results of comparative analysis are given.