Searching for Regularities in Weighted Sequences.pdf

VSP International Lecture Series on Computer Science Publishers and Computational Sciences P.O. Box 346, 3700 AH Zeist Volume X, 2004, pp. 1-4 The Netherlands Searching for Regularities in Weighted Sequences M. Christodoulakis, C. Iliopoulos, K. Tsichlas Department of Computer Science, King’s College, Strand, London WC2R 2LS, England {manolis,csi,kostas}@dcs.kcl.ac.uk K. Perdikuri Department of Computer Engineering and Informatics, University of Patras, 26500 Patras, Greece perdikur@ceid.upatras.gr Abstract: In this paper we describe algorithms for finding regularities in weighted se- quences. A weighted sequence is a sequence of symbols drawn from an alphabet Σ that have a prespecified probability of occurrence. We show that known algorithms for find- ing repeats in solid sequences may fail to do so for weighted sequences. In particular, we show that Crochemore’s algorithm for finding repetitions cannot be applied in the case of weighted sequences. However, one can use Karp’s algorithm to identify repeats of spe- cific length. We also extend this algorithm to identify the covers of a weighted sequence. Finally, the implementation of Karp’s algorithm brings up some very interesting issues. 1 Introduction Weighted sequences are used for representing relatively short sequences such as binding sites as well as long sequences such as profiles of protein families (see [2], 14.3). In addition, they are al