Algorithms for computing evolutionary chains in molecular and musical sequences
Maxime Crochemore, Costas S. Iliopoulos, Hiafeng Yu · HAL (Le Centre pour la Communication Scientifique Directe) · 1998
Abstract. The problem of nding evolutionary chains is de ned as follows: given a string t (\\the text") and a pattern p ( the \\motif"), nd whether there exists a sequence u1 = p; u2; : : : ; ul occurring in the text t such that ui+1 occurs to the right of ui in t and ui and ui+1 are \\similar" (i.e. the di er by a certain number of symbols). Here we consider several variants of the evolutionary chain problem and we present e cient algorithms for solving them.