FINDING FLEXIBLE PATTERNS IN A TEXT - AN APPLICATION TO 3-DIMENSIONALMOLECULAR MATCHING

Finding certain regularities in a text is an important problem in many areas, e.g. in the analysis of biological molecules such as nucleic a cids or proteins. In the latter case, the text may be sequences of ami no acids or a linear coding of three-dimensional structures, and the r egularities then correspond to lexical or structural motifs common to two, or more, proteins. We first recall an earlier algorithm that foun d these regularities in a flexible way. Then we introduce a generalize d version of this algorithm designed for the particular case of protei n three-dimensional structures, since these structures present a few p eculiarities that make them computationally harder to process. Finally , we give some applications of our new algorithm on concrete examples.