FINDING FLEXIBLE PATTERNS IN A TEXT - AN APPLICATION TO 3D MOLECULAR MATCHING
Marie-France Sagot, Alain Viari, Joël Pothier, Henry Soldano · 2005
: Finding certain regularities in a text is an important problem in many areas, for instance in the analysis of biological molecules such as nucleic acids or proteins. In the latter case, the text may be sequences of amino acids or a linear coding of 3D structures, and the regularities then correspond to lexical or structural motifs common to two, or more, proteins. We first recall an earlier algorithm allowing to find these regularities in a flexible way. Then we introduce a generalized version of this algorithm designed for the particular case of protein 3D structures, since these structures present a few peculiarities that make them computationally harder to process. Finally, we give some applications of our new algorithm on concrete examples. keywords : cliques, multiple alignment, protein structural matching. Introduction The main motivation for the new algorithm presented in this paper is that of finding the patterns common to a set of protein structures. This algorithm is a...