IDENTIFYING PERIODIC OCCURRENCES OF A TEMPLATE WITH APPLICATIONS TO PROTEIN-STRUCTURE

Consider a template P of size m in which each character matches many different characters with various degrees of perfection. Given a text T of size n, we present a simple and practical algorithm that finds the substring of T, which best matches some substring of P(n) (P(n) is the concatenation of an arbitrary number of copies of P). The algorithm produces the matched pair and their alignment in O(mn) time.