Efficient computation of clustered-clumps in degenerate strings

Costas Iliopoulos, Ritu Kundu, Manal Mohamed*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

1 Citation (Scopus)

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 O(n + m) time the occurrences of all clusteredclumps for a given set of degenerate patterns P and/or degenerate text T of total lengths m and n, respectively; such that the total number of non-solid symbols in P and T is bounded by a fixed positive integer d.

Original languageEnglish
Title of host publicationIFIP Advances in Information and Communication Technology
PublisherSpringer New York LLC
Pages510-519
Number of pages10
Volume475
ISBN (Print)9783319449432
DOIs
Publication statusPublished - 2 Sept 2016
Event12th IFIP WG 12.5 International Conference and Workshops on Artificial Intelligence Applications and Innovations, AIAI 2016 - Thessaloniki, Greece
Duration: 16 Sept 201618 Sept 2016

Publication series

NameIFIP Advances in Information and Communication Technology
Volume475
ISSN (Print)18684238

Conference

Conference12th IFIP WG 12.5 International Conference and Workshops on Artificial Intelligence Applications and Innovations, AIAI 2016
Country/TerritoryGreece
CityThessaloniki
Period16/09/201618/09/2016

Keywords

  • Clustered-clump
  • Conservative degenerate string
  • Overlapping occurrences
  • Pattern

Fingerprint

Dive into the research topics of 'Efficient computation of clustered-clumps in degenerate strings'. Together they form a unique fingerprint.

Cite this