Efficient Computation of Clustered-Clumps in Degenerate Strings

Abstract : Given a finite set of patterns, a clustered-clump is a maximal overlapping set of occurrences of such patterns. Several solutions have been presented for identifying clustered-clumps based on statistical, probabilistic, and most recently, formal language theory techniques. Here, motivated by applications in molecular biology and computer vision, we present efficient algorithms, using String Algorithm techniques, to identify clustered-clumps in a given text. The proposed algorithms compute in $$\mathcal {O}(n+m)$$ time the occurrences of all clustered-clumps for a given set of degenerate patterns $$\tilde{\mathcal {P}}$$ and/or degenerate text $$\tilde{T}$$ of total lengths m and n, respectively; such that the total number of non-solid symbols in $$\tilde{\mathcal {P}}$$ and $$\tilde{T}$$ is bounded by a fixed positive integer d.
Type de document :
Communication dans un congrès
Lazaros Iliadis; Ilias Maglogiannis. 12th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2016, Thessaloniki, Greece. IFIP Advances in Information and Communication Technology, AICT-475, pp.510-519, 2016, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-319-44944-9_45〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01557641
Contributeur : Hal Ifip <>
Soumis le : jeudi 6 juillet 2017 - 13:55:36
Dernière modification le : jeudi 19 avril 2018 - 14:24:03
Document(s) archivé(s) le : mercredi 24 janvier 2018 - 02:43:35

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Costas Iliopoulos, Ritu Kundu, Manal Mohamed. Efficient Computation of Clustered-Clumps in Degenerate Strings. Lazaros Iliadis; Ilias Maglogiannis. 12th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2016, Thessaloniki, Greece. IFIP Advances in Information and Communication Technology, AICT-475, pp.510-519, 2016, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-319-44944-9_45〉. 〈hal-01557641〉

Partager

Métriques

Consultations de la notice

40