Abstract
In this paper we define a new class of problems that generalizes that of finding repeated motifs. The novelty lies in the addition of constraints on the motifs in terms of relations that must hold between pairs of elements of the motifs. For this class of problems we give an algorithm that is a suitable extension of the KMR [3] paradigm and, in particular, of the KMRC [7] as it uses a degenerate alphabet. The algorithm contains several improvements with respect to [7] that result especially useful when – as it is required for relational motifs – the inference is made by partially overlapping shorter motifs. The efficiency, correctness and completeness of the algorithm is assured by several non-trivial properties. Finally, we list some possible applications and we focus on one of them: the study of 3D structures of proteins.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
El-Zant, N., Soldano, H.: Finding repeated flexible relational words in sequences. Journal of Systemics, Cybernetics and Informatics 2(4) (2004)
Jones, N.C., Pevzner, P.A.: An Introduction to Bioinformatics Algorithms. The MIT Press, Cambridge (2004)
Karp, R., Miller, R., Rosenberg, A.: Rapid identification of repated patterns in strings, trees and arrays. In: Fourth ACM Symposium on Theory of Computing, pp. 125–136 (1972)
Lothaire, M.: Applied Combinatorics on words. Cambridge University Press, Cambridge (2005)
Marsan, L., Sagot, M.-F.: Algorithms for extracting structured motifs using a suffix tree with application to promoter and regulatory consensus identification. Journal of Computational Biology 7, 345–360 (2001)
Pisanti, N., Crochemore, M., Grossi, R., Sagot, M.-F.: A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 622–631. Springer, Heidelberg (2003)
Soldano, H., Viari, A., Champesme, M.: Searching for flexible repeated patterns using a non-transitive similarity relation. Pattern Recognition Letters 16, 243–246 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pisanti, N., Soldano, H., Carpentier, M. (2005). Incremental Inference of Relational Motifs with a Degenerate Alphabet. In: Apostolico, A., Crochemore, M., Park, K. (eds) Combinatorial Pattern Matching. CPM 2005. Lecture Notes in Computer Science, vol 3537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496656_20
Download citation
DOI: https://doi.org/10.1007/11496656_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26201-5
Online ISBN: 978-3-540-31562-9
eBook Packages: Computer ScienceComputer Science (R0)