Motif patterns consisting of sequences of intermixed solid and don't-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms.

Apostolico, A., Parida, L., Rombo, S.E. (2008). Motif Patterns in 2D. THEORETICAL COMPUTER SCIENCE, 390(1), 40-55 [http://www.sciencedirect.com/science/article/pii/S0304397507007645].

Motif Patterns in 2D

ROMBO, Simona Ester
2008-01-01

Abstract

Motif patterns consisting of sequences of intermixed solid and don't-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms.
Apostolico, A., Parida, L., Rombo, S.E. (2008). Motif Patterns in 2D. THEORETICAL COMPUTER SCIENCE, 390(1), 40-55 [http://www.sciencedirect.com/science/article/pii/S0304397507007645].
File in questo prodotto:
File Dimensione Formato  
tcs08.pdf

Solo gestori archvio

Dimensione 652.17 kB
Formato Adobe PDF
652.17 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/64852
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 11
social impact