Searching for Repeated Words in a Text Allowing for Mismatches and Gaps
M-F. Sagot, VINCENT ESCALIER, Alain Viari, Henri Soldano, Atelier De Bioinformatique · 1995
We present in this paper an algorithm that locates similar words common to a set of strings defined over an alphabet \\Sigma, where the similarity is stated in terms of a Levenshtein edit distance. The comparison of the words in the strings is realized by using a reference object called a model which is a word over \\Sigma. This allows us to perform a multiple comparison of the strings as opposed to pairwise comparisons, and the algorithm is particularly appropriate for the analysis of DNA/RNA sequences. keywords : multiple comparison, Levenshtein edit distance, model 1 Introduction A lot has been written on the subject of finding a pattern in a text, whether strictly or flexibly, and efficient algorithms have been elaborated to treat that problem ([1] [2] [3] [5] [10] [11] [12] [14] [13] for some of the references). However, there are situations where we do not have any idea of what must be looked for in a text. Such a situation arises in biology, when we wish to find the similarities...