Efficient computation of clustered-clumps in degenerate strings

Costas Iliopoulos; Ritu Kundu; Manal Mohamed

doi:10.1007/978-3-319-44944-9_45

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 proceeding › Conference paper › peer-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 language	English
Title of host publication	IFIP Advances in Information and Communication Technology
Publisher	Springer New York LLC
Pages	510-519
Number of pages	10
Volume	475
ISBN (Print)	9783319449432
DOIs	https://doi.org/10.1007/978-3-319-44944-9_45
Publication status	Published - 2 Sept 2016
Event	12th IFIP WG 12.5 International Conference and Workshops on Artificial Intelligence Applications and Innovations, AIAI 2016 - Thessaloniki, Greece Duration: 16 Sept 2016 → 18 Sept 2016

Publication series

Name	IFIP Advances in Information and Communication Technology
Volume	475
ISSN (Print)	18684238

Conference

Conference	12th IFIP WG 12.5 International Conference and Workshops on Artificial Intelligence Applications and Innovations, AIAI 2016
Country/Territory	Greece
City	Thessaloniki
Period	16/09/2016 → 18/09/2016

Keywords

Clustered-clump
Conservative degenerate string
Overlapping occurrences
Pattern

Access to Document

10.1007/978-3-319-44944-9_45

Cite this

@inbook{490f8d5dbdce496e83c04287fecb9a04,

title = "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 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.",

keywords = "Clustered-clump, Conservative degenerate string, Overlapping occurrences, Pattern",

author = "Costas Iliopoulos and Ritu Kundu and Manal Mohamed",

year = "2016",

month = sep,

day = "2",

doi = "10.1007/978-3-319-44944-9_45",

language = "English",

isbn = "9783319449432",

volume = "475",

series = "IFIP Advances in Information and Communication Technology",

publisher = "Springer New York LLC",

pages = "510--519",

booktitle = "IFIP Advances in Information and Communication Technology",

note = "12th IFIP WG 12.5 International Conference and Workshops on Artificial Intelligence Applications and Innovations, AIAI 2016 ; Conference date: 16-09-2016 Through 18-09-2016",

}

Iliopoulos, C , Kundu, R & Mohamed, M 2016, Efficient computation of clustered-clumps in degenerate strings. in IFIP Advances in Information and Communication Technology. vol. 475, IFIP Advances in Information and Communication Technology, vol. 475, Springer New York LLC, pp. 510-519, 12th IFIP WG 12.5 International Conference and Workshops on Artificial Intelligence Applications and Innovations, AIAI 2016, Thessaloniki, Greece, 16/09/2016. https://doi.org/10.1007/978-3-319-44944-9_45

Efficient computation of clustered-clumps in degenerate strings. / Iliopoulos, Costas ; Kundu, Ritu ; Mohamed, Manal.
IFIP Advances in Information and Communication Technology. Vol. 475 Springer New York LLC, 2016. p. 510-519 (IFIP Advances in Information and Communication Technology; Vol. 475).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

TY - CHAP

T1 - Efficient computation of clustered-clumps in degenerate strings

AU - Iliopoulos, Costas

AU - Kundu, Ritu

AU - Mohamed, Manal

PY - 2016/9/2

Y1 - 2016/9/2

N2 - 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.

AB - 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.

KW - Clustered-clump

KW - Conservative degenerate string

KW - Overlapping occurrences

KW - Pattern

UR - http://www.scopus.com/inward/record.url?scp=84988521326&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-44944-9_45

DO - 10.1007/978-3-319-44944-9_45

M3 - Conference paper

AN - SCOPUS:84988521326

SN - 9783319449432

VL - 475

T3 - IFIP Advances in Information and Communication Technology

SP - 510

EP - 519

BT - IFIP Advances in Information and Communication Technology

PB - Springer New York LLC

T2 - 12th IFIP WG 12.5 International Conference and Workshops on Artificial Intelligence Applications and Innovations, AIAI 2016

Y2 - 16 September 2016 through 18 September 2016

ER -

Efficient computation of clustered-clumps in degenerate strings

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this