Finding flexible patterns in a
text: an application to three-dimensional molecular
matching
Marie-France Sagot, Alain Viari, Joël Pothier and Henri Soldano
Computer Applied to the Biosciences (CABIOS)
11:59-70,
1995
Finding certain regularities in a text is an important problem in many
areas, e.g. 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 three-dimensional structures, and
the regularities then correspond to lexical or structural motifs
common to two, or more, proteins. We first recall an earlier algorithm
that found these regularities in a flexible way. Then we introduce a
generalized version of this algorithm designed for the particular case
of protein three-dimensional 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.
key words: cliques, multiple alignment, protein structural
matching
Paper in postscript format
Back to the Publications page