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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01557641
Contributor : Hal Ifip <>
Submitted on : Thursday, July 6, 2017 - 1:55:36 PM
Last modification on : Thursday, April 19, 2018 - 2:24:03 PM
Long-term archiving on : Wednesday, January 24, 2018 - 2:43:35 AM

File

430537_1_En_45_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Costas Iliopoulos, Ritu Kundu, Manal Mohamed. Efficient Computation of Clustered-Clumps in Degenerate Strings. 12th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2016, Thessaloniki, Greece. pp.510-519, ⟨10.1007/978-3-319-44944-9_45⟩. ⟨hal-01557641⟩

Share

Metrics

Record views

88

Files downloads

100